L11: String reconstruction as a hamiltonian vs eulerian path problem

Welcome to Lecture 11 of the course "Algorithmic Thinking in Bioinformatics" by Associate Prof. Manikandan Narayanan. Full Course: https://study.iitm.ac.in/ds/course_pages/BSBT4001.html Video Overview This lecture explores the challenge of genome reconstruction from k mers using concepts from graph theory. We begin by formulating the problem in two distinct ways as a Hamiltonian Path problem and as an Eulerian Path problem. By representing the genome as a path through a graph we can apply efficient graph algorithms to assemble the genome from its fragments. The lecture explains how to build both a k mer composition graph and a De Bruijn graph and highlights the computational advantages of using the Eulerian Path approach. This method plays a key role in modern genome sequencing and demonstrates the power of algorithmic thinking in bioinformatics. About IIT Madras' online Bachelor of Science programme IIT Madras offers four-year BS programmes that aim to provide quality education to all, irrespective of age, educational background, or location. The BS programme has multiple levels, which provide flexibility to students to exit at any of these levels. Depending on the courses completed and credits earned, the learner can receive a Foundation Certificate from IITM CODE (Centre for Outreach and Digital Education), Diploma(s) from IIT Madras, or BSc/BS Degrees from IIT Madras. For more details, Visit: https://www.iitm.ac.in/academics/study-at-iitm/non-campus-bs-programmes #genome #sequencing #assembly #bioinformatics #graphTheory #HamiltonianPath #EulerianPath #DeBruijnGraph #kmer #algorithm #computationalBiology #genomeassembly #genomicdata #sequenceanalysis #bioinformaticsalgorithms #computationalgenomics #DNAsequencing #NGS #genomeinformatics #graphalgorithms #biologicaldata #molecularbiology