Back to search

University of South Florida

High-Performance Computing in Next-Generation Sequencing Read Alignment

Abstract

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (Ph.D.)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science and Engineering
Grantor
University of South Florida
Year dc:date
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pham, Minh H.
Contributors dc:contributor
  • Yicheng Tu, Ph.D.
  • Hao Zheng, Ph.D.
  • Robert Karam, Ph.D.
  • Rays Jiang, Ph.D.
  • Ashwin Parthasarathy, Ph.D.

Subjects

dc:subject × 5

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/10551

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pham, Minh H.. High-Performance Computing in Next-Generation Sequencing Read Alignment. Dissertation thesis, University of South Florida, 2024. https://digitalcommons.usf.edu/etd/10551