This course covers algorithms for biological and biologically inspired problems. Most of these are algorithms on strings (a consequence of molecular biology); however, graph algorithms and other combinatorial/probabilistic optimization algorithms will be covered. The complexity of the algorithms will be studied, and in case of NP-hard problems, some approximation algorithms will be considered.
The general objective of the course is to appreciate biology as a source of many interesting abstractions in computer science; moreover, to understand how existing algorithms can be applied to solve problems in a biological context. The content of the course should provide a jump start into the field of computational biology and bioinformatics if someone is interested in pursuing research in that direction.
Here's a tentative list of topics: string matching (exact and approximate), FFTs and fingerprinting, suffix trees with applications to matchings and repeats, all pairs suffix-prefix matching, sequence alignments and dynamic programming, the four russian speedup, edits distances and gaps, alignments by chaining in 2D, multiple sequence alignments and approximation algorithms, string folding with loop energy model and the Boltzman distribution, RNA interaction, maps and superstrings, the turnpike problem, covering strings, signed permutations, applications of traveling salesman and Euler cycles, phylogenetic trees, perfect phylogeny and colored triangulations, maximum parsimony, probabilistic analysis of repeats in random strings, Markov models and the Viterbi algorithm, Expectation-Maximization and the Baum-Welsh algorithm.
There are no tests, only homework assignments (mostly algorithmic with some implementation) and a project.
Introduction to Computational Biology, Waterman
Computational Molecular Biology, Pevzner,
Algorithms on Strings, Trees, and Sequences, Gusfield
Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Durbin
Introduction to Computational Molecular Biology, Setubal and Meidanis
An Introduction to Bioinformatics Algorithms, Jones and Pevzner