DEPARTMENT OF COMPUTATIONAL AND DATA SCIENCES
Ph.D. Thesis Colloquium
Speaker : Mr. Ghanshyam Chandra
S.R. Number : 06-18-01-10-12-20-1-18380
Title : Algorithmic approaches to pangenome graph problems
Research Supervisor : Dr. Chirag Jain
Date & Time : January 3, 2025 (Friday), 02:00 PM
Venue : # 102 CDS Seminar Hall
ABSTRACT
The human reference genome serves as a foundational baseline for comparing other human genomes. With the growing availability of reference-grade human genome assemblies, there is now an opportunity to modernize the reference genome by incorporating genome sequences from thousands of individuals. By capturing genetic variation of diverse individuals, pangenome reference promises to improve equity in human genetics and genomics. An efficient way to represent a pangenome reference is a graph data structure where the vertices are labelled with sequences and the edges connect two sequences that appear consecutively in a genome.
Existing works have discussed the construction and the benefits of a pangenome reference but most methods use ad-hoc heuristics that lack strong theoretical foundations. In this thesis, we introduce novel problem formulations and algorithms to address the following questions: (1) How to align sequences to a pangenome graph?, (2) How to infer a newly sequenced genome by using a pangenome reference?, and (3) How to accelerate whole-genome alignment, a crucial step in pangenome graph construction?
The first two parts of this thesis focus on rigorously solving the problem of aligning sequencing reads to a pangenome graph. Given a set of exact substring matches between a read and vertex labels, chaining refers to identifying an ordered subset of matches that be combined together to form an alignment. Previous methods ignore distances between matches because computing distances quickly on graphs is non-trivial. We propose the first formulations and efficient algorithms that account for distances between adjacent matches. The time complexity of our algorithms is parameterized in the size of minimum path cover, which is known to be small for pangenome graphs. We empirically demonstrate improved accuracy in aligning long reads to graphs.
In the second part, we further enhance the optimization criteria for sequence-to-graph alignment by penalizing recombinations, where a recombination refer to switching between genomes in a pangenome graph. This feature helps in improving the alignment quality, as most paths in a pangenome graph represent biologically unlikely recombinations. We develop efficient dynamic programming algorithms for chaining and alignment. We also give fine-grained reductions to prove that significantly faster algorithms are impossible under the strong exponential time hypothesis (SETH).
The third part of the thesis introduces a novel problem formulation for inferring an individual’s genome sequence as a path in a pangenome graph. This task is useful for variant discovery and genotyping applications. We give a proof of NP-hardness and design efficient integer programming algorithms. Using publicly available sequencing datasets, we show that our algorithm accurately infers major histocompatibility complex (MHC) sequences using low-coverage sequencing data, outperforming existing heuristic algorithms.
In the final part, we propose parallel algorithms to accelerate whole-genome alignment, a fundamental problem in bioinformatics. We implement a fine-grained parallel chaining algorithm and a fast mechanism for differentiating primary and secondary chains. These optimizations yield speedups ranging from 1.6x to 7.2x over a commonly used parallel alignment algorithm, minimap2. We discuss the generalization of our techniques for fast pangenome graph construction.
ALL ARE WELCOME
