Hardware acceleration of the pair HMM algorithm for DNA variant calling

Huang, Sitao

Permalink

https://hdl.handle.net/2142/97496 Copy

Description

Title

Hardware acceleration of the pair HMM algorithm for DNA variant calling

Author(s)

Huang, Sitao

Issue Date

2017-04-26

Director of Research (if dissertation) or Advisor (if thesis)

• Chen, Deming
• Hwu, Wen-Mei M

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Hardware acceleration
• Field-programmable gate array (FPGA)
• Forward algorithm
• Pair hidden Markov model (HMM)
• Computational genomics
• Processing element (PE) ring

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 urgent to explore non-conventional implementation platforms to accelerate genomics research. In this thesis, we present a Field-Programmable Gate Array (FPGA) accelerated implementation of the Pair Hidden Markov Model (Pair HMM) forward algorithm, the performance bottleneck in the HaplotypeCaller, a critical function in the popular Genome Analysis Toolkit (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.56x compared to the previous best hardware implementation.

Graduation Semester

2017-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/97496

Copyright and License Information

Copyright 2017 Sitao Huang

Owning Collections