Rxivist logo

Faster sequence alignment through GPU-accelerated restriction of the seed-and-extend search space

By Richard Wilton, Tamas Budavari, Ben Langmead, Sarah Wheelan, Steven L. Salzberg, Alex Szalay

Posted 01 Aug 2014
bioRxiv DOI: 10.1101/007641 (published DOI: 10.7717/peerj.808)

Motivation: In computing pairwise alignments of biological sequences, software implementations employ a variety of heuristics that decrease the computational effort involved in computing potential alignments. A key element in achieving high processing throughput is to identify and prioritize potential alignments where high-scoring mappings can be expected. These tasks involve list-processing operations that can be efficiently performed on GPU hardware. Results: We implemented a read aligner called A21 that exploits GPU-based parallel sort and reduction techniques to restrict the number of locations where potential alignments may be found. When compared with other high-throughput aligners, this approach finds more high-scoring mappings without sacrificing speed or accuracy. A21 running on a single GPU is about 10 times faster than comparable CPU-based tools; it is also faster and more sensitive in comparison with other recent GPU-based aligners.

Download data

  • Downloaded 1,288 times
  • Download rankings, all-time:
    • Site-wide: 7,509 out of 88,857
    • In bioinformatics: 1,320 out of 8,400
  • Year to date:
    • Site-wide: 59,442 out of 88,857
  • Since beginning of last month:
    • Site-wide: 43,792 out of 88,857

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)