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:125@cds.iisc.ac.in
DTSTART;TZID=Asia/Kolkata:20250602T100000
DTEND;TZID=Asia/Kolkata:20250602T110000
DTSTAMP:20250526T073941Z
URL:https://cds.iisc.ac.in/events/ph-d-thesis-defense-cds-june-02-2025-alg
 orithmic-approaches-to-pangenome-graph-problems/
SUMMARY:Ph.D. Thesis Defense: CDS: June 02\, 2025 "Algorithmic Approaches t
 o Pangenome Graph Problems"
DESCRIPTION:DEPARTMENT OF COMPUTATIONAL AND DATA SCIENCES\nPh.D. Thesis Def
 ense\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"\n
 Research Supervisor : Dr. Chirag Jain\nThesis examiner : Prof. Khan\, Shah
 baz\, IIT Roorkee.\nDate &amp\; Time : June 02\, 2025 (Monday) at 10:00 AM
 \nVenue : The Thesis Defense will be held on HYBRID Mode\n\n# 102 CDS Semi
 nar Hall /MICROSOFT TEAMS.\n\nPlease click on the following link to join t
 he Thesis Defense\nMS Teams link\n\n\n\nABSTRACT\n\nThe human reference ge
 nome serves as a foundational baseline for comparing newly sequenced human
  genomes. With the growing availability of high-quality human genome assem
 blies\,\nthere is now an opportunity to modernize the reference genome by 
 incorporating genome sequences from thousands of individuals. By capturing
  genetic variation of diverse populations\, a pangenome reference promises
  to improve equity in human genetics and genomics.\nAn efficient way to re
 present a pangenome reference is a graph data structure where the vertices
  are labeled with sequences and the edges connect two sequences that appea
 r consecutively in a genome.\n\nExisting works have discussed the construc
 tion and the benefits of a pangenome reference\, but most methods use ad-h
 oc heuristics that lack strong theoretical foundations. In this thesis\, w
 e introduce novel problem formulations and algorithms to address the follo
 wing questions: (1) How to align sequences to a pangenome graph? (2) How t
 o infer a newly sequenced genome using a pangenome reference? and (3) How 
 to accelerate whole-genome alignment\, a crucial step in pangenome graph c
 onstruction?\n\nThe first two parts of this thesis focus on solving the pr
 oblem of aligning sequencing reads to a pangenome graph. Given a set of ex
 act substring matches between a read and the vertex labels\, chaining refe
 rs to identifying an ordered subset of matches that be combined together t
 o form an alignment. Previous methods ignore distances between match locat
 ions because computing distances quickly on graphs is non-trivial. We prop
 ose the first chaining formulations and efficient algorithms that account 
 for the pairwise distances between match locations. 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 imp
 roved accuracy in aligning long reads to graphs.\n\nIn the second part\, w
 e further enhance the optimization criteria for sequence-to-graph alignmen
 t by penalizing recombinations\, where a recombination refers to switching
  between genomes in a pangenome graph. This feature helps in improving the
  alignment quality\, as most paths in a pangenome graph represent biologic
 ally unlikely recombinations. We develop efficient dynamic programming alg
 orithms for chaining and alignment problems. We also give fine-grained red
 uctions to prove that significantly faster algorithms are impossible under
  the strong exponential time hypothesis (SETH).\n\nThe third part of the t
 hesis introduces a novel problem formulation for inferring an individual's
  genome sequence as a path in a pangenome graph. This task is useful for v
 ariant discovery and genotyping applications. We give a proof of NP-hardne
 ss and design efficient integer programming algorithms. Using publicly ava
 ilable sequencing datasets\, we show that our algorithm accurately infers 
 major histocompatibility complex (MHC) sequences using low-coverage sequen
 cing data\, outperforming existing heuristic algorithms.\n\nIn the final p
 art\, we propose parallel algorithms to accelerate whole-genome alignment\
 , a fundamental problem in bioinformatics. We implement a multi-core paral
 lel chaining algorithm and a fast mechanism for differentiating primary an
 d secondary chains. These optimizations lead to runtime gains over a commo
 nly used parallel alignment algorithm\, minimap2. We discuss the generaliz
 ation of our techniques for fast pangenome graph construction.\n\n\n\nALL 
 ARE WELCOME
CATEGORIES:Events,Thesis Defense
END:VEVENT
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
X-LIC-LOCATION:Asia/Kolkata
BEGIN:STANDARD
DTSTART:20240602T100000
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
END:STANDARD
END:VTIMEZONE
END:VCALENDAR