{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/110760"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/110760","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Improved GPU implementations of the Pair-HMM forward algorithm for DNA sequence alignment","abstract":"The student, Enliang Li, accepted the attached license on 2021-04-30 at 13:30.","abstract_html":"The student, Enliang Li, accepted the attached license on 2021-04-30 at 13:30.","abstract_has_math":false,"creators":["Li, Enliang"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Chen, Deming"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-09-17T02:34:51Z","date_published":"2021-09-17T02:34:51Z","updated_at":"2026-07-22T22:24:52Z","subjects":["GPU","Hardware Acceleration","Pair-HMM","CUDA implementation","Computational Genomics"],"languages":["en"],"rights":["Copyright 2021 Enliang Li"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/110760","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chen, Deming"]},{"key":"dc:creator","label":"Author","values":["Li, Enliang"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-09-17T02:34:51Z","2023-09-17T02:34:57Z","2021-04-30","2021-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["GPU","Hardware Acceleration","Pair-HMM","CUDA implementation","Computational Genomics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Enliang Li"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/110760"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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","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"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Improved GPU implementations of the Pair-HMM forward algorithm for DNA sequence alignment"]}]}],"canonical_facts":{"dc:contributor":["Chen, Deming"],"dc:creator":["Li, Enliang"],"dc:date":["2021-09-17T02:34:51Z","2023-09-17T02:34:57Z","2021-04-30","2021-05"],"dc:description":["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","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"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/110760"],"dc:language":["en"],"dc:rights":["Copyright 2021 Enliang Li"],"dc:subject":["GPU","Hardware Acceleration","Pair-HMM","CUDA implementation","Computational Genomics"],"dc:title":["Improved GPU implementations of the Pair-HMM forward algorithm for DNA sequence alignment"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}