Halbkurs Algorithmische Bioinformatik
Professor Ulf Leser
Der Halbkurs "Algorithmische Bioinformatik" behandelt Algorithmen zur Lösung grundlegender Fragestellungen moderner Molekularbiologie. Nach einer Einführung in die Grundlagen der Molekularbiologie (Gene und Genome, Expression, Proteine, Regulation und Transkription) werden die folgenden algorithmischen Probleme behandelt: Exaktes Stringmatching, Stringmatching mit mehreren Pattern, approximatives Matching, Indexstrukturen für Sequenzdatenbanken, Editabstand und Alignment, Multiples Alignment, Phylogenetische Bäume. Die Algorithmen werden jeweils anhand der zugrunde liegenden biologischen Fragestellung erklärt, wie z.B. Patternsuche in DNA- und Proteinsequenzen, Assembly von Teilsequenzen, Homologiesuche in Sequenzdatenbanken, und Berechnung evolutionärer Stammbäume. Die Vorlesung wird durch eine Übung begleitet.
Erste Vorlesung ist am Donnerstag, den 18.10.2018.
Voraussetzungen
Voraussetzung für den Besuch sind gute Kenntnisse in Algorithmen (z.B. Modul Algorithmen & Datenstrukturen). Kenntnisse in der Molekularbiologie werden nicht vorausgesetzt, sondern vermittelt.
Prüfungen
Prüfungen sind mündlich oder schriftlich. Die Vorlesung ist anrechenbar für:
- Master Informatik, 10 SP
- Masterstudiengang Biophysik, Vertiefungsrichtung Bioinformatik, 10 SP
Voraussetzung für die Zulassung zur Prüfung ist das Bestehen der Übung.
Literatur zur Vorlesung
Dan Gusfield: "Algorithms on Strings, Trees, and Sequences", Cambrige University Press.
Die Vorlesung folgt in grossen Teilen diesem Buch. Zusätzliche Literatur wird in den jeweiligen Stunden angegeben.
Themen und Termine im Einzelnen
(Folien sind hier jeweils vor der Vorlesung als PDF verfügbar. Änderungen möglich).
- Einleitung und Überblick
- Raik Otto, Molekularbiologie Part1: The Cell
- Raik Otto, Molekularbiologie Part2: The Gene
- Raik Otto, Molekularbiologie Part3: Homology
- Raik Otto, Molekularbiologie Part4: Cancer NGS
- Strings und Moleküle
- Z-Box und Average Case Analysen
- Boyer Moore
- Knuth-Morris-Pratt Algorithmus; Automaten zum Stringmatching
- Aho-Corasick: Suche nach mehreren Pattern; mit Wildcards; mit regulären Ausdrücken
- Suffixbäume
- Suffix Tree Konstruktion in linearer Zeit
- Suffixarrays und Enhanced Suffixarrays
- Sequenzalignment
- End-Free und lokales Alignement; Gap-Score Modelle
- Alignment in linearem Platz; k-Band Alignment
- Jukes-Cantor Modell und Substitutionsmatrizen
- Datenbanksuchheuristiken: BYP, BLAST, BLAT
- Referentielle Komprimierung und Suche
- Genstruktur und Markov-Modelle
- Hidden Markov Modelle / Viterbi
- Evaluation und Lernen von HMMs
- Multiple Sequence Alignment
- Profil-HMMs und CLUSTAL-W
- Einführung in die Phylogenie
- Distanzbasierte phylogenetische Algorithmen
- Character-basierte phylogenetische Algorithmen
- Abschluss
Weitere Materialien
- Ausführliche Ableitung des Jukes-Cantor-Modells
- Sehr schöne und umfassende Erläuterungen von Stringalgorithmen inklusive Demonstration und Visualisierung (Charras & Lecroq, Université de Rouen)
- Algorithmische Bioinformatik I/II. Sehr ausführliches und umfassendes Skript. (Volker Heun, TU München)
- Ein sehr kompaktes Glossar vieler molekularbiologischer Begriffe (John Kimball)
- Liste aller sequenzierten Organismen
Ergänzende Literatur
- Ohlebusch: "Bioinformatics Algorithms", Verlag Enno Ohlebusch.
- Böckenhauer, Bongartz: "Algorithmische Grundlagen der Bioinformatik", Teubner Verlag.
- Koolman, Röhm, Wirth: "Taschenatlas der Biochemie", Thieme Verlag. Für die molekularbiologischen Grundlagen.
- Mount, "Bioinformatics: Sequence and Genome Analysis", Cold Spring Harbor Laboratory Press
- Merkl, Waack, "Bioinformatik Interaktiv - Algorithmen und Praxis", Wiley-Ch