BIO

Text: handouts and classnotes

Prerequisite: none

Topics:

Genome rearrangment Hannenhalli-Pevzner theorem: graph of desire and reality, the overlap graph and sorting signed permutations by reversals. Other computationally easy problems: sorting by block-interchanges, sorting by double cut and join operations. 1.5-approximation for sorting by transpositions.

Dynamic programming Parsing algorithms for parsing regular and context-free grammars. Predicting protein and RNA structures with regular and context-free grammars. Aligning biological sequences. Dynamic programming algorithms on evolutionary trees: the small parsimony algorithm, Felsenstein's algorithm for calculating the likelihood of a tree, the Noah's ark problem.

Algebraic dynamic programming: a unified view of dynamic programming algorithms.

Towards statistical methods: Stochastic transformational grammars. Markov chain Monte Carlo.