Formale Sprachen und ihre Anwendung in der Bioinformatik und Linguistik (Modul 10-202-2208)


  • Topics (depending on time and interest)
    • linear and context-free languages
    • stochastic context-free languages
    • applications: alignment, folding, Hidden-Markov Models, Covariance Models
    • ensemble algorithms: e.g. base-pairing probabilities; general Inside/Outside applications
    • advanced topics ...
  • language: english or german depending on the audience
  • prior knowledge requirements: your should have seen dynamic programs before (Needleman-Wunsch sequence alignment; RNA secondary structure folding)
  • questions and topics requests: choener@bioinf
  • Added relevant literature, with extended topics.


Uhrzeit:Bitte der Tabelle unten entnehmen!
Vorlesung:   Raum 109, Härtelstr. 16-18
Prüfung:Modulprüfung 10-202-2208 schriftlich, Termin im Zeitraum: 20.07.15 - 31.07.15

VL 0129.05.15 15:00-18:00 Uhr
VL 0205.06.1515:00-18:00 Uhr
VL 0312.06.1515:00-18:00 Uhr


Discussions in the literature will go into more details / depth compared to lecture! Reading the book by Durbin in full is, however, a very good idea for anyone in computational biology / bioinformatics.

Durbin, Eddy, Krogh, Mitchison. Biological sequence analysis. Chapter: 3. Markov chains and hidden Markov models ; 5. Profile HMMs for sequence families ; 9. Transformational grammars ; 10. RNA structure analysis
Information on stochastic context-free grammars, Hidden-Markov models, covariance models, inside-outside algorithms

Hoener zu Siederdissen, Prohaska, Stadler. Algebraic dynamic programming over general data structures. Includes the mechanical derivation of outside grammars from inside grammars. (cf. Durbin et al. Chp. 9.6) link to paper
mechanical inside-outside

Infernal authors. The Infernal Users Guide. Infernal models from building blocks, from multiple alignments link to guide
p.59, Fig. 3: Infernal building blocks