Accelerating Sequence Alignment Algorithms on Heterogeneous Processors

PhD Thesis Proposal Defence


Title: "Accelerating Sequence Alignment Algorithms on Heterogeneous Processors"

by

Mr. Zonghao FENG


Abstract:

Sequence alignment is an essential component in genome analysis pipelines. 
However, it is usually time-consuming due to the high algorithmic complexity 
and large data volumes. Furthermore, recent advances in sequencing technologies 
and biological research bring new challenges, such as aligning long reads and 
graph reference genomes. Therefore, in this proposal, we parallelize three new 
kinds of sequence alignment algorithms and optimize them on heterogeneous 
processors.

Specifically, we first propose a long read alignment algorithm on multi-core 
CPUs, Intel Xeon Phi Processors (KNL), and Graphics Processing Units (GPU). We 
redesign memory layouts of dynamic programming matrices on all three processors 
to eliminate data dependency and facilitate vectorization. We also exploit the 
full feature set of each processor to maximize the performance, such as high 
bandwidth memory of KNL and concurrent kernel execution of GPU. Second, we 
propose a parallel sequence-to-graph alignment algorithm on both the CPU and 
GPUs. We reduce the computational cost of aligning frequent structures in 
genome graphs, design the GCSR (Genome CSR) data structure for efficient genome 
graph processing on GPUs, and apply architecture-aware optimizations to 
increase memory throughput. To the best of our knowledge, we are the first to 
accelerate long read alignment and sequence-to-graph alignment on GPUs. Third, 
we discuss our ongoing work on accelerating partial order alignment. We propose 
to avoid dynamic memory allocation by designing adjacency lists based graph 
storage format, and increase parallelism through reduction. Finally, we plan to 
integrate all three algorithms into a versatile alignment toolkit and conduct a 
comparative performance study.


Date:			Tuesday, 25 January 2022

Time:			2:00pm - 4:00pm

Zoom Meeing: 
https://hkust.zoom.us/j/93253023814?pwd=SXo1dWRTWVE0bHhBNUJiOWFHdjlvUT09

Committee Members:	Prof. Qiong Luo (Supervisor)
 			Prof. Raymond Wong (Chairperson)
 			Prof. Ke Yi
 			Prof. Weichuan YU (ECE)


**** ALL are Welcome ****