{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-11838"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-11838","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"High-Performance Computing in Next-Generation Sequencing Read Alignment","abstract":"Advancements in Next-Generation Sequencing (NGS) have dramatically reduced the cost and increased the speed of DNA sequencing. However, this rapid influx of data necessitates efficient and robust analysis tools, particularly for the complex task of aligning short NGS reads to reference genomes such as the human genome. We explore groundbreaking computational strategies and hardware acceleration to optimize this critical alignment process. This dissertation is structured around three innovative studies. First, we introduce a novel approach to dynamic memory allocation tailored for massively parallel systems, particularly Graphical Processing Units (GPUs), to support NGS alignment and other applications. Unlike traditional memory allocators that rely on global data structures which can bottleneck parallel processing, our approach widely distributes memory information and employs thread-level random search procedures for memory allocation. Our design consistently outperformed the current state-of-the-art by up to two orders of magnitude. Second, we present a pioneering implementation of BWA-MEM, one of the gold-standard NGS aligners, on GPUs. Our research addresses and resolves significant challenges in translating BWA-MEM’s CPU-based operations to GPU architecture, achieving a remarkable speedup -- up to 5.8 times faster than the original BWA-MEM and 3.2 times faster than its newer CPU-optimized version, BWA-MEM2. Finally, we discuss a novel Machine Learning-based approach for NGS alignment, marking a transformative shift from the traditional seed-and-extend approach. By encoding NGS sequences as learned latent vectors using machine learning models, we design advanced vector-database indexing techniques to efficiently identify alignment locations. An implementation of this new approach on CPUs has comparable accuracy and throughput to BWA-MEM2 for short reads and is more than twenty times faster for long reads.","abstract_html":"Advancements in Next-Generation Sequencing (NGS) have dramatically reduced the cost and increased the speed of DNA sequencing. However, this rapid influx of data necessitates efficient and robust analysis tools, particularly for the complex task of aligning short NGS reads to reference genomes such as the human genome. We explore groundbreaking computational strategies and hardware acceleration to optimize this critical alignment process. This dissertation is structured around three innovative studies. First, we introduce a novel approach to dynamic memory allocation tailored for massively parallel systems, particularly Graphical Processing Units (GPUs), to support NGS alignment and other applications. Unlike traditional memory allocators that rely on global data structures which can bottleneck parallel processing, our approach widely distributes memory information and employs thread-level random search procedures for memory allocation. Our design consistently outperformed the current state-of-the-art by up to two orders of magnitude. Second, we present a pioneering implementation of BWA-MEM, one of the gold-standard NGS aligners, on GPUs. Our research addresses and resolves significant challenges in translating BWA-MEM’s CPU-based operations to GPU architecture, achieving a remarkable speedup -- up to 5.8 times faster than the original BWA-MEM and 3.2 times faster than its newer CPU-optimized version, BWA-MEM2. Finally, we discuss a novel Machine Learning-based approach for NGS alignment, marking a transformative shift from the traditional seed-and-extend approach. By encoding NGS sequences as learned latent vectors using machine learning models, we design advanced vector-database indexing techniques to efficiently identify alignment locations. An implementation of this new approach on CPUs has comparable accuracy and throughput to BWA-MEM2 for short reads and is more than twenty times faster for long reads.","abstract_has_math":false,"creators":["Pham, Minh H."],"institution":"University of South Florida","degree_name":"Doctor of Philosophy (Ph.D.)","degree_level":"Dissertation","degree_discipline":"Computer Science and Engineering","degree_department":null,"school":null,"contributors":["Yicheng Tu, Ph.D.","Hao Zheng, Ph.D.","Robert Karam, Ph.D.","Rays Jiang, Ph.D.","Ashwin Parthasarathy, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-06-13T07:00:00Z","date_published":"2024-06-13T07:00:00Z","updated_at":"2026-11-19T08:50:14Z","subjects":["Parallel Algorithms","General-Purpose Graphics Processing Unit","Vector Database","Supercomputing","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/10551","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/10551","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-11838","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yicheng Tu, Ph.D.","Hao Zheng, Ph.D.","Robert Karam, Ph.D.","Rays Jiang, Ph.D.","Ashwin Parthasarathy, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Pham, Minh H."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-06-13T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation","Ph.D."]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (Ph.D.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Parallel Algorithms","General-Purpose Graphics Processing Unit","Vector Database","Supercomputing","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/10551"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Advancements in Next-Generation Sequencing (NGS) have dramatically reduced the cost and increased the speed of DNA sequencing. However, this rapid influx of data necessitates efficient and robust analysis tools, particularly for the complex task of aligning short NGS reads to reference genomes such as the human genome. We explore groundbreaking computational strategies and hardware acceleration to optimize this critical alignment process. This dissertation is structured around three innovative studies. First, we introduce a novel approach to dynamic memory allocation tailored for massively parallel systems, particularly Graphical Processing Units (GPUs), to support NGS alignment and other applications. Unlike traditional memory allocators that rely on global data structures which can bottleneck parallel processing, our approach widely distributes memory information and employs thread-level random search procedures for memory allocation. Our design consistently outperformed the current state-of-the-art by up to two orders of magnitude. Second, we present a pioneering implementation of BWA-MEM, one of the gold-standard NGS aligners, on GPUs. Our research addresses and resolves significant challenges in translating BWA-MEM’s CPU-based operations to GPU architecture, achieving a remarkable speedup -- up to 5.8 times faster than the original BWA-MEM and 3.2 times faster than its newer CPU-optimized version, BWA-MEM2. Finally, we discuss a novel Machine Learning-based approach for NGS alignment, marking a transformative shift from the traditional seed-and-extend approach. By encoding NGS sequences as learned latent vectors using machine learning models, we design advanced vector-database indexing techniques to efficiently identify alignment locations. An implementation of this new approach on CPUs has comparable accuracy and throughput to BWA-MEM2 for short reads and is more than twenty times faster for long reads."]},{"key":"dc:title","label":"Title","values":["High-Performance Computing in Next-Generation Sequencing Read Alignment"]}]}],"canonical_facts":{"dc:contributor":["Yicheng Tu, Ph.D.","Hao Zheng, Ph.D.","Robert Karam, Ph.D.","Rays Jiang, Ph.D.","Ashwin Parthasarathy, Ph.D."],"dc:creator":["Pham, Minh H."],"dc:date":["2024-06-13T07:00:00Z"],"dc:description":["Advancements in Next-Generation Sequencing (NGS) have dramatically reduced the cost and increased the speed of DNA sequencing. However, this rapid influx of data necessitates efficient and robust analysis tools, particularly for the complex task of aligning short NGS reads to reference genomes such as the human genome. We explore groundbreaking computational strategies and hardware acceleration to optimize this critical alignment process. This dissertation is structured around three innovative studies. First, we introduce a novel approach to dynamic memory allocation tailored for massively parallel systems, particularly Graphical Processing Units (GPUs), to support NGS alignment and other applications. Unlike traditional memory allocators that rely on global data structures which can bottleneck parallel processing, our approach widely distributes memory information and employs thread-level random search procedures for memory allocation. Our design consistently outperformed the current state-of-the-art by up to two orders of magnitude. Second, we present a pioneering implementation of BWA-MEM, one of the gold-standard NGS aligners, on GPUs. Our research addresses and resolves significant challenges in translating BWA-MEM’s CPU-based operations to GPU architecture, achieving a remarkable speedup -- up to 5.8 times faster than the original BWA-MEM and 3.2 times faster than its newer CPU-optimized version, BWA-MEM2. Finally, we discuss a novel Machine Learning-based approach for NGS alignment, marking a transformative shift from the traditional seed-and-extend approach. By encoding NGS sequences as learned latent vectors using machine learning models, we design advanced vector-database indexing techniques to efficiently identify alignment locations. An implementation of this new approach on CPUs has comparable accuracy and throughput to BWA-MEM2 for short reads and is more than twenty times faster for long reads."],"dc:identifier":["https://digitalcommons.usf.edu/etd/10551"],"dc:subject":["Parallel Algorithms","General-Purpose Graphics Processing Unit","Vector Database","Supercomputing","Computer Sciences"],"dc:title":["High-Performance Computing in Next-Generation Sequencing Read Alignment"],"thesis:degree_discipline":["Computer Science and Engineering"],"thesis:degree_level":["Dissertation","Ph.D."],"thesis:degree_name":["Doctor of Philosophy (Ph.D.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:50:14Z"}