**Combinatorial and computational aspects of bioinformatics**
*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.