Introduction

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.

Publications

  1. BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm.
    Cite this
    Loving J, Hernandez Y, Benson G, 2014-11-01 - Bioinformatics (Oxford, England)

Credits

  1. Joshua Loving
    Developer

    Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, United States of America

  2. Yozen Hernandez
    Developer

    Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, United States of America

  3. Gary Benson
    Investigator

    Laboratory for Biocomputing and Informatics, Graduate Program in Bioinformatics, United States of America

Community Ratings

UsabilityEfficiencyReliabilityRated By
0 user
Sign in to rate
Summary
AccessionBT006322
Tool TypeApplication
Category
PlatformsLinux/Unix
TechnologiesC
User InterfaceTerminal Command Line
Download Count0
Country/RegionUnited States of America
Submitted ByGary Benson