2026-09-19T13:27:31Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/110760 2023-07-11 col_2142_5131 col_2142_8888 com_2142_5130 com_2142_8887 com_2142_234

The student, Enliang Li, accepted the attached license on 2021-04-30 at 13:30. The student, Enliang Li, submitted this Thesis for approval on 2021-04-30 at 13:48. This Thesis was approved for publication on 2021-04-30 at 13:58. DSpace SAF Submission Ingestion Package generated from Vireo submission #16629 on 2021-09-16 at 17:07:00 Made available in DSpace on 2021-09-17T02:34:51Z (GMT). No. of bitstreams: 2 LI-THESIS-2021.pdf: 1260213 bytes, checksum: 8f40b85342640c903796ee660abad561 (MD5) LICENSE.txt: 4204 bytes, checksum: e12b57abadd944dee37d4d1252367944 (MD5) Previous issue date: 2021-04-30 Embargo set by: Seth Robbins for item 118603 Lift date: 2023-09-17T02:34:57Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system Chen, Deming Li, Enliang 2021-09-17T02:34:51Z 2021-09-17T02:34:51Z 2023-09-17T02:34:57Z 2021-04-30 2021-05 With the rise of Next-Generation Sequencing (NGS), clinical sequencing services have become more accessible but also facing new challenges. As we discovered the closed connection between key DeoxyriboNucleic Acid (DNA) mutation spots and major diseases or conditions, the need for computational genomics has increased significantly. The surging demand motivates developments of more efficient algorithms for genome assembly, error correction, k-mer counting etc. In this thesis, we focus on DNA sequencing analysis, one of the fastest-growing markets in NGS, and its related alignment problems. In recent years, many new hardware technologies and algorithms have been researched for their potential applications in massive parallel sequencing. The emerging hardware includes GPU, FPGA and other ASICs providing parallel processing resources. In this thesis, we choose GPU as our computation platform for its massive parallel processing capabilities. The Forward Algorithm (FA) still remains one of the most commonly used methods in solving sequences alignment problems modeled as Pair-Hidden Markov Model (HMM). The Pair-HMM Forward Algorithm (FA) is not only a computation but data intensive algorithm. Multiple previous works have been done in efforts to accelerate the computation of the FA by applying massive parallelization on the workload, and in this thesis, we bring more optimizations not only by improving the computation concurrency of both initialization process and Pair-HMM FA but also by tackling the communications overhead between the host and devices. We will discuss the general principles of optimizing the Forward Algorithm on GPU and present an improved implementation of the Pair-HMM FA with native CUDA C++. Our design has shown a speedup of 25.10x over the C++ baseline on the GATK HaplotypeCaller Pair-HMM workload with a portion of the real dataset from human genome database, NA12878. This is a major improvement that beats the state-of-the-art implementation with a margin of 60%. Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2023-05-01 Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system U of I Only application/pdf http://hdl.handle.net/2142/110760 en Copyright 2021 Enliang Li GPU Hardware Acceleration Pair-HMM CUDA implementation Computational Genomics Improved GPU implementations of the Pair-HMM forward algorithm for DNA sequence alignment text Thesis Electrical & Computer Eng Electrical & Computer Engr University of Illinois at Urbana-Champaign Thesis M.S.