Accelerating Sequence Alignment Algorithms on Heterogeneous Processors

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis 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 
thesis, we parallelize three 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. Third, we introduce a GPU-accelerated partial order 
alignment algorithm. We propose to avoid dynamic memory allocation by 
designing the GAL (Genome Adjacency List) graph representation, and 
increase parallelism through intra-sequence parallelization.


Date:			Wednesday, 8 June 2022

Time:			2:00pm - 4:00pm

Zoom Meeting: 
https://hkust.zoom.us/j/94844027182?pwd=eFNLWEk1NytKNHB3cms0SGpaY3Bndz09

Chairperson:		Prof. Ying ZHAO (MARK)

Committee Members:	Prof. Qiong LUO (Supervisor)
 			Prof. Raymond WONG
 			Prof. Ke YI
 			Prof. Weichuan YU (ECE)
 			Prof. Cho-Li WANG (HKU)


**** ALL are Welcome ****