Accelerating phylogeny-aware short DNA read alignment with FPGAs

Nikolaos Alachiotis*, Simon A. Berger, Alexandros Stamatakis

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)

Abstract

Recent advances in molecular sequencing technology have given rise to novel algorithms for simultaneously aligning short sequence reads to reference sequence alignments and corresponding evolutionary reference trees. We present a complete hardware/software implementation for the acceleration of a program called PaPaRa, a newly introduced dynamic programming algorithm for this purpose. We verify the correctness of the proposed architecture on a real FPGA and introduce a straight-forward communication protocol(using gigabit ethernet) for seamless integration with the encapsulating steering software that is executed on a PC processor. The hardware description and the software implementation are freely available for download. When mapped to a Virtex 6 FPGA, our reconfigurable architecture can compute 133.4 billion cell updates per second for the novel, tree-based alignment kernel of PaPaRa. Compared to PaPaRa, running on a 3.2GHz Intel Core i5 CPU, we obtain speedups for the alignment kernel, that range between 170 and 471. For the entire application, that is, the alignment kernel and the trace-back step, we obtain speedups between 74 and 118.

Original languageEnglish
Title of host publicationProceedings - IEEE 19th Annual International Symposium on Field-Programmable Custom Computing Machines, FCCM 2011
Place of PublicationPiscataway, NJ
PublisherIEEE
Pages226-233
Number of pages8
ISBN (Electronic)978-0-7695-4301-7 (CD)
ISBN (Print)978-1-61284-277-6
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event19th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2011 - Salt Lake City, UT, United States
Duration: 1 May 20113 May 2011

Conference

Conference19th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2011
Country/TerritoryUnited States
CitySalt Lake City, UT
Period1/05/113/05/11

Keywords

  • Dynamic Programming (DP)
  • FPGA
  • Multiple alignment
  • Phylogenetic inference

Fingerprint

Dive into the research topics of 'Accelerating phylogeny-aware short DNA read alignment with FPGAs'. Together they form a unique fingerprint.

Cite this