Hardware Accelerated Alignment Algorithm for Optical Labeled Genomes

• Published in: ACM transactions on reconfigurable technology and systems 2016-09, Vol.9 (3), p.1-21
• Main Authors: Meng, Pingfan, Jacobsen, Matthew, Kimura, Motoki, Dergachev, Vladimir, Anantharaman, Thomas, Requa, Michael, Kastner, Ryan
• Format: Article
• Language: English
• Subjects: Algorithms; Alignment; Assembly; Central processing units; Design engineering; Devices; Field programmable gate arrays; Genomes
• ISSN: 1936-7406; 1936-7414
• DOI: 10.1145/2840811

De novo assembly is a widely used methodology in bioinformatics. However, the conventional short-read-based de novo assembly is incapable of reliably reconstructing the large-scale structures of human genomes. Recently, a novel optical label-based technology has enabled reliable large-scale de novo assembly. Despite its advantage in large-scale genome analysis, this new technology requires a more computationally intensive alignment algorithm than its conventional counterpart. For example, the runtime of reconstructing a human genome is on the order of 10,000 hours on a sequential CPU. Therefore, in order to practically apply this new technology in genome research, accelerated approaches are desirable. In this article, we present three different accelerated approaches, multicore CPU, GPU, and FPGA. Against the sequential software baseline, our multicore CPU design achieved an 8.4× speedup, while the GPU and FPGA designs achieved 13.6× and 115× speedups, respectively. We also discuss the details of the design space exploration of this new assembly algorithm on these three different devices. Finally, we compare these devices in performance, optimization techniques, prices, and design efforts.