Instructor: Dr. István MIKLÓS
Text: handouts 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.