AnySeq: A High Performance Sequence Alignment Library based on Partial Evaluation

Sequence alignments are fundamental to bioinformatics which has resulted in a variety of optimized implementations. Unfortunately, the vast majority of them are hand-tuned and specific to certain architectures and execution models. This not only makes them challenging to understand and extend, but also difficult to port to other platforms. We present AnySeq - a novel library for computing different types of pairwise alignments of DNA sequences. Our approach combines high performance with an intuitively understandable implementation, which is achieved through the concept of partial evaluation. Using the AnyDSL compiler framework, AnySeq enables the compilation of algorithmic variants that are highly optimized for specific usage scenarios and hardware targets with a single, uniform codebase. The resulting domain-specific library thus allows the variation of alignment parameters (such as alignment type, scoring scheme, and traceback vs.~plain score) by simple function composition rather than metaprogramming techniques which are often hard to understand. Our implementation supports multithreading and SIMD vectorization on CPUs, CUDA-enabled GPUs, and FPGAs. AnySeq is at most 7% slower and in many cases faster (up to 12%) than state-of-the art manually optimized alignment libraries on CPUs (SeqAn) and on GPUs (NVBio).

BibTeX
@inproceedings{mueller2020anyseq,
  author          = {Müller, André and Schmidt, Bertil and Hildebrandt, Andreas and Membarth, Richard and Kruse, Matthis and Leißa, Roland and Hack, Sebastian},
  address         = {New Orleans, LA, USA},
  booktitle       = {Proceedings of the 34th IEEE International Parallel \& Distributed Processing Symposium (IPDPS)},
  title           = {{AnySeq}: A High Performance Sequence Alignment Library based on Partial Evaluation},
  pages           = {1--11},
  year            = 2020,
  month           = may,
  date            = {2020-05-18/2020-05-22},
  doi             = {},
  organization    = {IEEE}
}

Recent Publications

A. Müller B. Schmidt A. Hildebrandt R. Membarth R. Leißa M. Kruse S. Hack
AnySeq: A High Performance Sequence Alignment Library based on Partial Evaluation

Proceedings of the 34th IEEE International Parallel \& Distributed Processing Symposium (IPDPS), pp. 1-11, New Orleans, LA, USA, May 5-8, 2020

Read more
E. Sánchez Morales R. Membarth A. Gaull P. Slusallek T. Dirndorfer A. Kammenhuber C. Lauer M. Botsch
Parallel Multi-Hypothesis Algorithm for Criticality Estimation in Traffic and Collision Avoidance

Proceedings of the 30th IEEE Intelligent Vehicles Symposium (IV), pp. 2164-2171, Paris, France, June 9-12, 2019

Read more
R. Membarth H. Dutta F. Hannig J. Teich
Efficient Mapping of Streaming Applications for Image Processing on Graphics Cards

Transactions on High-Performance Embedded Architectures and Compilers (Transactions on HiPEAC), V: 1-20, 2019

Read more