title: BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm.
abstract: BACKGROUND
  Mapping of high-throughput sequencing data and other bulk sequence comparison applications have motivated a search for high-efficiency sequence alignment algorithms. The bit-parallel approach represents individual cells in an alignment scoring matrix as bits in computer words and emulates the calculation of scores by a series of logic operations composed of AND, OR, XOR, complement, shift and addition. Bit-parallelism has been successfully applied to the longest common subsequence (LCS) and edit-distance problems, producing fast algorithms in practice.
  
  
  RESULTS
  We have developed BitPAl, a bit-parallel algorithm for general, integer-scoring global alignment. Integer-scoring schemes assign integer weights for match, mismatch and insertion/deletion. The BitPAl method uses structural properties in the relationship between adjacent scores in the scoring matrix to construct classes of efficient algorithms, each designed for a particular set of weights. In timed tests, we show that BitPAl runs 7-25 times faster than a standard iterative algorithm.
  
  
  METHODS
  Source code is freely available for download at http://lobstah.bu.edu/BitPAl/BitPAl.html. BitPAl is implemented in C and runs on all major operating systems.
  
  
  BACKGROUND
  jloving@bu.edu or yhernand@bu.edu or gbenson@bu.edu
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors: Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA.
authors: Joshua
authors: J
authors: Loving
authors: Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA.
authors: Yozen
authors: Y
authors: Hernandez
authors: Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, and Department of Computer Science, Boston University, Boston, MA 02215, USA.
authors: Gary
authors: G
authors: Benson
mesh_terms: D000465:Algorithms; D059014:High-Throughput Nucleotide Sequencing; D016415:Sequence Alignment / Q000379:methods*; D012984:Software