Files in this item



application/pdfECE499-Sp2019-li-.pdf (573kB)
(no description provided)PDF


Title:Exploration of GPU acceleration for pair-HMM algorithm and its application in the DNA alignment problem
Author(s):Li, Enliang
Contributor(s):Chen, Deming
Subject(s):Hardware Acceleration
DNA Alignment
Forward Algorithm
CUDA Implementation
Abstract:The hidden Markov model, known as HMM, is an important type of statistical model with extensive application in estimating hidden parameters and decoding observed Markov chains. On top of the HMM, the Pair-HMM Algorithm with Halotype-Caller is developed as a popular solution for the DNA alignment problem. For two aligned sequences of DNA observations, one named as reference, and the other one named as read, there are only three possible hidden states, i.e. match (A , A), insertion (- , A), and deletion (A , -). However, what we could observe by DNA sequencing in real-life is the summation of the possibilities for match, insertion, and deletion as macrostates. In order to determine the alignment with maximum probability, we need to score each possible pairwise alignment and which leads to a computationally intensive problem that usually contributes to the most latency in a variant calling with the GATK HaplotypeCaller. In the CPU implementation of a proper Pair-HMM forward algorithm, there are 7 multiply-accumulate operations for each ( i , j ) location on the read-reference matrix. Moreover, since transitions and emission matrices are fixed throughout a single alignment process, a CUDA implementation with single-precision floating-point is proposed to accelerate the Pair-HMM forward algorithm. CUDA implementation with minibatch and states-parallelization, along with the use of float32, gives us an around 22.6x speedup compared to the CPU implementation. While it comes with a price, using single-precision instead of double-precision floating-point introduces a more serious under flow problem at the beginning of the alignment scoring process. A normalization technique is used to help fix this problem.
Issue Date:2019-05
Date Available in IDEALS:2019-06-14

This item appears in the following Collection(s)

Item Statistics