A BIT-PARALLEL DYNAMIC PROGRAMMING ALGORITHM SUITABLE FOR DNA SEQUENCE ALIGNMENT
Authors:
- 23 July 2012
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Journal of Bioinformatics and Computational Biology
- Vol. 10 (04) , 1250002
Abstract
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.Keywords
This publication has 17 references indexed in Scilit:
- CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractionsBMC Research Notes, 2010
- Fast and accurate long-read alignment with Burrows–Wheeler transformBioinformatics, 2010
- SOAP2: an improved ultrafast tool for short read alignmentBioinformatics, 2009
- Fast and accurate short read alignment with Burrows–Wheeler transformBioinformatics, 2009
- Ultrafast and memory-efficient alignment of short DNA sequences to the human genomeGenome Biology, 2009
- The new paradigm of flow cell sequencing: Table 1.Genome Research, 2008
- CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignmentBMC Bioinformatics, 2008
- 160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA)BMC Bioinformatics, 2007
- Striped Smith–Waterman speeds database searches six times over other SIMD implementationsBioinformatics, 2006
- A fast bit-vector algorithm for approximate string matching based on dynamic programmingJournal of the ACM, 1999