BEGIN:VCALENDAR VERSION:2.0 PRODID:-//wp-events-plugin.com//7.2.3.1//EN TZID:Asia/Kolkata X-WR-TIMEZONE:Asia/Kolkata BEGIN:VEVENT UID:95@cds.iisc.ac.in DTSTART;TZID=Asia/Kolkata:20250103T140000 DTEND;TZID=Asia/Kolkata:20250103T150000 DTSTAMP:20241226T071212Z URL:https://cds.iisc.ac.in/events/ph-d-thesis-colloquium-102-cds-3-january -2025-algorithmic-approaches-to-pangenome-graph-problems/ SUMMARY:Ph.D: Thesis Colloquium: 102 : CDS: 3\, January 2025 "Algorithmic a pproaches to pangenome graph problems" DESCRIPTION:DEPARTMENT OF COMPUTATIONAL AND DATA SCIENCES\nPh.D. Thesis Col loquium\n\n\n\nSpeaker : Mr. Ghanshyam Chandra\nS.R. Number : 06-18-01-10- 12-20-1-18380\nTitle : Algorithmic approaches to pangenome graph problems\ nResearch Supervisor : Dr. Chirag Jain\nDate &\; Time : January 3\, 202 5 (Friday)\, 02:00 PM\nVenue : # 102 CDS Seminar Hall\n\n\n\nABSTRACT\nThe human reference genome serves as a foundational baseline for comparing ot her 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. B y capturing genetic variation of diverse individuals\, pangenome reference promises to improve equity in human genetics and genomics. An efficient w ay to represent a pangenome reference is a graph data structure where the vertices are labelled with sequences and the edges connect two sequences t hat appear consecutively in a genome.\n\nExisting works have discussed the construction and the benefits of a pangenome reference but most methods u se ad-hoc heuristics that lack strong theoretical foundations. In this the sis\, we introduce novel problem formulations and algorithms to address th e 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 pan genome graph construction?\n\nThe 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 l abels\, chaining refers to identifying an ordered subset of matches that b e combined together to form an alignment. Previous methods ignore distance s between matches because computing distances quickly on graphs is non-tri vial. We propose the first formulations and efficient algorithms that acco unt for distances between adjacent matches. The time complexity of our alg orithms is parameterized in the size of minimum path cover\, which is know n to be small for pangenome graphs. We empirically demonstrate improved ac curacy in aligning long reads to graphs.\n\nIn the second part\, we furthe r enhance the optimization criteria for sequence-to-graph alignment by pen alizing recombinations\, where a recombination refer to switching between genomes in a pangenome graph. This feature helps in improving the alignmen t quality\, as most paths in a pangenome graph represent biologically unli kely recombinations. We develop efficient dynamic programming algorithms f or chaining and alignment. We also give fine-grained reductions to prove t hat significantly faster algorithms are impossible under the strong expone ntial time hypothesis (SETH).\n\nThe third part of the thesis introduces a novel problem formulation for inferring an individual's genome sequence a s a path in a pangenome graph. This task is useful for variant discovery a nd genotyping applications. We give a proof of NP-hardness and design effi cient integer programming algorithms. Using publicly available sequencing datasets\, we show that our algorithm accurately infers major histocompati bility complex (MHC) sequences using low-coverage sequencing data\, outper forming existing heuristic algorithms.\nIn the final part\, we propose par allel algorithms to accelerate whole-genome alignment\, a fundamental prob lem in bioinformatics. We implement a fine-grained parallel chaining algor ithm and a fast mechanism for differentiating primary and secondary chains . These optimizations yield speedups ranging from 1.6x to 7.2x over a comm only used parallel alignment algorithm\, minimap2. We discuss the generali zation of our techniques for fast pangenome graph construction.\n\n\n\nALL ARE WELCOME CATEGORIES:Events,Ph.D. Thesis Colloquium END:VEVENT BEGIN:VTIMEZONE TZID:Asia/Kolkata X-LIC-LOCATION:Asia/Kolkata BEGIN:STANDARD DTSTART:20240104T140000 TZOFFSETFROM:+0530 TZOFFSETTO:+0530 TZNAME:IST END:STANDARD END:VTIMEZONE END:VCALENDAR