Hardware acceleration of the pair-HMM algorithm for DNA variant calling

Sitao Huang, Gowthami Jayashri Manikandan, Anand Ramachandran, Kyle Rupnow, Wen-Mei W Hwu, Deming Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

With the advent of several accurate and sophisticated statistical algorithms and pipelines for DNA sequence analysis, it is becoming increasingly possible to translate raw sequencing data into biologically meaningful information for further clinical analysis and processing. However, given the large volume of the data involved, even modestly complex algorithms would require a prohibitively long time to complete. Hence it is the need of the hour to explore non-conventional implementation platforms to accelerate genomics research. In this work, we present an FPGA-accelerated implementation of the Pair HMM forward algorithm, the performance bottleneck in the HaplotypeCaller, a critical function in the popular GATK variant calling tool. We introduce the PE ring structure which, thanks to the fine-grained parallelism allowed by the FPGA, can be built into various configurations striking a trade-off between instruction-level parallelism (ILP) and data parallelism. We investigate the resource utilization and performance of different configurations. Our solution can achieve a speed-up of up to 487x compared to the C++ baseline implementation on CPU and 1.56? compared to the best published hardware implementation.

Original languageEnglish (US)
Title of host publicationFPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays
PublisherAssociation for Computing Machinery, Inc
Pages275-284
Number of pages10
ISBN (Electronic)9781450343541
DOIs
StatePublished - Feb 22 2017
Event2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA 2017 - Monterey, United States
Duration: Feb 22 2017Feb 24 2017

Publication series

NameFPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

Other

Other2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA 2017
CountryUnited States
CityMonterey
Period2/22/172/24/17

Fingerprint

DNA
Hardware
Field programmable gate arrays (FPGA)
DNA sequences
Program processors
Pipelines
Processing
Genomics

Keywords

  • Computational genomics
  • FPGA
  • Forward algorithm
  • Hardware acceleration
  • PE ring
  • Pair-HMM

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Huang, S., Manikandan, G. J., Ramachandran, A., Rupnow, K., Hwu, W-M. W., & Chen, D. (2017). Hardware acceleration of the pair-HMM algorithm for DNA variant calling. In FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (pp. 275-284). (FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays). Association for Computing Machinery, Inc. https://doi.org/10.1145/3020078.3021749

Hardware acceleration of the pair-HMM algorithm for DNA variant calling. / Huang, Sitao; Manikandan, Gowthami Jayashri; Ramachandran, Anand; Rupnow, Kyle; Hwu, Wen-Mei W; Chen, Deming.

FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. Association for Computing Machinery, Inc, 2017. p. 275-284 (FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Huang, S, Manikandan, GJ, Ramachandran, A, Rupnow, K, Hwu, W-MW & Chen, D 2017, Hardware acceleration of the pair-HMM algorithm for DNA variant calling. in FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Association for Computing Machinery, Inc, pp. 275-284, 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA 2017, Monterey, United States, 2/22/17. https://doi.org/10.1145/3020078.3021749
Huang S, Manikandan GJ, Ramachandran A, Rupnow K, Hwu W-MW, Chen D. Hardware acceleration of the pair-HMM algorithm for DNA variant calling. In FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. Association for Computing Machinery, Inc. 2017. p. 275-284. (FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays). https://doi.org/10.1145/3020078.3021749
Huang, Sitao ; Manikandan, Gowthami Jayashri ; Ramachandran, Anand ; Rupnow, Kyle ; Hwu, Wen-Mei W ; Chen, Deming. / Hardware acceleration of the pair-HMM algorithm for DNA variant calling. FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. Association for Computing Machinery, Inc, 2017. pp. 275-284 (FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays).
@inproceedings{019b98ae88f143c290eb006d1233d678,
title = "Hardware acceleration of the pair-HMM algorithm for DNA variant calling",
abstract = "With the advent of several accurate and sophisticated statistical algorithms and pipelines for DNA sequence analysis, it is becoming increasingly possible to translate raw sequencing data into biologically meaningful information for further clinical analysis and processing. However, given the large volume of the data involved, even modestly complex algorithms would require a prohibitively long time to complete. Hence it is the need of the hour to explore non-conventional implementation platforms to accelerate genomics research. In this work, we present an FPGA-accelerated implementation of the Pair HMM forward algorithm, the performance bottleneck in the HaplotypeCaller, a critical function in the popular GATK variant calling tool. We introduce the PE ring structure which, thanks to the fine-grained parallelism allowed by the FPGA, can be built into various configurations striking a trade-off between instruction-level parallelism (ILP) and data parallelism. We investigate the resource utilization and performance of different configurations. Our solution can achieve a speed-up of up to 487x compared to the C++ baseline implementation on CPU and 1.56? compared to the best published hardware implementation.",
keywords = "Computational genomics, FPGA, Forward algorithm, Hardware acceleration, PE ring, Pair-HMM",
author = "Sitao Huang and Manikandan, {Gowthami Jayashri} and Anand Ramachandran and Kyle Rupnow and Hwu, {Wen-Mei W} and Deming Chen",
year = "2017",
month = "2",
day = "22",
doi = "10.1145/3020078.3021749",
language = "English (US)",
series = "FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays",
publisher = "Association for Computing Machinery, Inc",
pages = "275--284",
booktitle = "FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays",

}

TY - GEN

T1 - Hardware acceleration of the pair-HMM algorithm for DNA variant calling

AU - Huang, Sitao

AU - Manikandan, Gowthami Jayashri

AU - Ramachandran, Anand

AU - Rupnow, Kyle

AU - Hwu, Wen-Mei W

AU - Chen, Deming

PY - 2017/2/22

Y1 - 2017/2/22

N2 - With the advent of several accurate and sophisticated statistical algorithms and pipelines for DNA sequence analysis, it is becoming increasingly possible to translate raw sequencing data into biologically meaningful information for further clinical analysis and processing. However, given the large volume of the data involved, even modestly complex algorithms would require a prohibitively long time to complete. Hence it is the need of the hour to explore non-conventional implementation platforms to accelerate genomics research. In this work, we present an FPGA-accelerated implementation of the Pair HMM forward algorithm, the performance bottleneck in the HaplotypeCaller, a critical function in the popular GATK variant calling tool. We introduce the PE ring structure which, thanks to the fine-grained parallelism allowed by the FPGA, can be built into various configurations striking a trade-off between instruction-level parallelism (ILP) and data parallelism. We investigate the resource utilization and performance of different configurations. Our solution can achieve a speed-up of up to 487x compared to the C++ baseline implementation on CPU and 1.56? compared to the best published hardware implementation.

AB - With the advent of several accurate and sophisticated statistical algorithms and pipelines for DNA sequence analysis, it is becoming increasingly possible to translate raw sequencing data into biologically meaningful information for further clinical analysis and processing. However, given the large volume of the data involved, even modestly complex algorithms would require a prohibitively long time to complete. Hence it is the need of the hour to explore non-conventional implementation platforms to accelerate genomics research. In this work, we present an FPGA-accelerated implementation of the Pair HMM forward algorithm, the performance bottleneck in the HaplotypeCaller, a critical function in the popular GATK variant calling tool. We introduce the PE ring structure which, thanks to the fine-grained parallelism allowed by the FPGA, can be built into various configurations striking a trade-off between instruction-level parallelism (ILP) and data parallelism. We investigate the resource utilization and performance of different configurations. Our solution can achieve a speed-up of up to 487x compared to the C++ baseline implementation on CPU and 1.56? compared to the best published hardware implementation.

KW - Computational genomics

KW - FPGA

KW - Forward algorithm

KW - Hardware acceleration

KW - PE ring

KW - Pair-HMM

UR - http://www.scopus.com/inward/record.url?scp=85016014373&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016014373&partnerID=8YFLogxK

U2 - 10.1145/3020078.3021749

DO - 10.1145/3020078.3021749

M3 - Conference contribution

AN - SCOPUS:85016014373

T3 - FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

SP - 275

EP - 284

BT - FPGA 2017 - Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

PB - Association for Computing Machinery, Inc

ER -