Algorithms in Computational Biology and Sequence Analysis

• Brief review of the fundamentals of molecular biology and genetics. 
• Examples of widely used software, algorithms, databases.

• Z-algorithm, suffix arrays, suffix array construction

• Suffix trees, suffix tree construction, applications of suffix trees

• Burrows-Wheeler Transformation, BWT index, Generalised rank operations, succinct suffix arrays
• Classic dynamic programming ideas for pairwise sequence alignment. 
• Edit distance, global alignment

• Local alignment, Incorporating gaps in alignments
• Statistical measures of alignment significance.

• Mathematical ideas underlying heuristic sequence aligners.
• Maximal unique matches, co-linear chaining

• Incorporating gaps into the chaining algorithm
• Applications of sequence alignment for mutation finding and disease diagnosis.
• Shortest common superstring formulation for genome reconstruction

• Greedy approach to genome reconstruction
• de Bruijn Graphs, Overlap graphs

• Multiple sequence alignment – formulations, optimal and approximation algorithms
• Classical and contemporary algorithms for inferring evolutionary trees.

• Gene finding. Hidden Markov models
• Large language models for biological sequences

• Overview of pangenome representations
• Aligning sequences to a pangenome

There is no textbook required for the course.

For further reading after lectures, the following books can be used: 

• Genome-Scale Algorithm Design (Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, Alexandru I. Tomescu)
• Algorithms on Strings, Trees, and Sequences (Dan Gusfield)
• Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids (Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison)
• Handbook of computational molecular biology (Srinivas Aluru)