A bit-parallel dynamic programming algorithm suitable for DNA sequence alignment.
Myers' elegant and powerful bit-parallel dynamic programming algorithm for approximate string matching has a restriction that the query length should be within the word size of the computer, typically 64. We propose a modification of Myers' algorithm, in which the modification has a restriction not on the query length but on the maximum number of mismatches (substitutions, insertions, or deletions), which should be less than half of the word size. The time complexity is O(m  log  |Σ|), where m is the query length and |Σ| is the size of the alphabet Σ. Thus, it is particularly suited for sequences on a small alphabet such as DNA sequences. In particular, it is useful in quickly extending a large number of seed alignments against a reference genome for high-throughput short-read data produced by next-generation DNA sequencers.
Central Research Laboratory, Hitachi Ltd., 1-280 Higashi-Koigakubo, Kokubunji Tokyo, 185-8601, Japan. kouichi.kimura.hh@hitachi.com
Kouichi
K
Kimura
Asako
A
Koike
Kenta
K
Nakai
D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology; D004247:DNA / Q000737:chemistry*; D016678:Genome; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA
D004247:DNA