Algorithmic Approaches to Computational Biology

Instructor: Dr. Manikandan Narayanan

Description

Invite students to tour algorithms on strings, trees and graphs that have transformed the field of biology and medicine in modern times. Importantly, offer students an interesting perspective of how algorithmic/statistical research is done in the field of computational biology and bioinformatics, and thereby inspire them to formulate their own fresh computational problems to address intriguing biological questions.

Course Content

• Where in the Genome Does DNA Replication Begin? - Algorithmic warmup (frequent exact/inexact k-mers in a string)
• Which DNA Patterns Play the Role of Molecular Clocks? - Randomized Algorithms (randomized motif search, Gibbs sampling)
• How Do We Assemble Genomes? - Graph Algorithms (Eulerian paths, de Bruijn graphs)
• How Do We Compare Biological Sequences? - Dynamic Programming (edit distance, single/multiple sequence alignment)
• Which Animal Gave Us SARS? - Evolutionary Tree Reconstruction (distance-based phylogeny, neighbor-joining algorithm)
• How Did Yeast Become a Wine Maker? - Clustering Algorithms (hard and soft k-means)
• How Do We Locate Disease-Causing Mutations? - Combinatorial Pattern Matching (suffix trees/arrays, Burrows-Wheeler transform)
• Why Have Biologists Still Not Developed an HIV Vaccine? - Hidden Markov Models (Viterbi and forward-backward algorithms)
• Was T. rex Just a Big Chicken? - Computational Proteomics (peptide identification and spectral match)
• Which Motifs Are Hidden in a Biological Network? - Randomized Algorithms (color coding for long paths in graphs)

The course content above is based on the book “Bioinformatics Algorithms: An Active Learning Approach” by Compeau and Pevzner.