Re: [Seqan-dev] Appr. BNDM algorithm

["Holtgrewe, Manuel" <manuel.holtgrewe@fu-berlin.de>]

Hi Alp,

the score is the negative edit distance (i.e. 3 edit distance errors -> score of -3).

The algorithm was not invented by any SeqAn people but rather is described in Navarro's book:

Navarro, Gonzalo, and Matthieu Raffinot. Flexible pattern matching in strings: practical on-line search algorithms for texts and biological sequences. Cambridge University Press, 2002.

Cheers,

Manuel

---

From: F M [flying.madden@gmail.com]
Sent: Monday, July 15, 2013 4:11 PM
To: seqan-dev@lists.fu-berlin.de
Subject: [Seqan-dev] Appr. BNDM algorithm

Hello, as a phd student curious to learn string matching algorithm implementations, I have been checking seqan tutorials since this morning :)

my question is how is Approximate Backward Nondeterministic Dawg Matching implemented? How does scoring work? What kind of metric is this? Is there a research paper that explains the inner details? Thank you.

Best Regards,

Alp

http://docs.seqan.de/seqan/dev/SPEC_Abndm_Algo.html