General Information
| Description | A bit-parallel, general integer-scoring sequence alignment algorithm |
| Homepage | http://lobstah.bu.edu/BitPAl/BitPAl.html |
Publications
BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm
Motivation:
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.
Availability and implementation:
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.
Contact
: jloving@bu.edu or yhernand@bu.edu or gbenson@bu.edu
Supplementary information
: Supplementary data are available at Bioinformatics online.
Related Tools
Probabilistic alignments with quality scores
Published October 2011
An application to short-read mapping toward accurate SNP/indel detection
NETAL
Published May 2013
A new graph-based method for global alignment of protein–protein interaction networks
slaMEM
Published December 2013
Efficient retrieval of maximal exact matches using a sampled LCP array
FAIR Evaluation
Sorry, you must be signed in to evaluate this object.
