Algorithmische Bioinformatik
Professor Ulf Leser
Der Halbkurs "Algorithmische Bioinformatik" behandelt Algorithmen zur Lösung grundlegender Fragestellungen moderner Molekularbiologie. Nach einer ausführlichen 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 zugrundeliegenden biologischen Fragestellung erklärt, wie z.B. Patternsuche in DNA- und Proteinsequenzen, Assembly von Teilsequenzen, Homologiesuche in Sequenzdatenbanken, und Berechnung evolutionärer Stammbäume.
Voraussetzungen
Voraussetzung für den Besuch sind grundlegende Kenntnisse in Algorithmen. Kenntnisse in der Molekularbiologie werden nicht vorausgesetzt, sondern vermittelt.
Prüfungen
Prüfungen sind mündlich. Die Vorlesung ist als Halbkurs der praktischen Informatik anrechenbar.
Ort / Zeit:
- Donnerstag, 9.00 - 11.00, RUD26, Raum 1'303
- Freitag, 13.00 - 15.00, RUD26, Raum 1'303
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).- Administratives, Einleitung und Überblick
- Einführung in die Molekularbiologie, Prof. Thomas Börner, Institut für Biologie, Lehrstuhl für Genetik
- Sequenzierung, cDNA Clustering, Funktionsvorhersage; Strings und Stringvergleiche
- Z-Box Algorithmus (Korrigiert, Stand 11.11.)
- Boyer-Moore Algorithmus; Apostolico-Giancarlo Variante (Korrigiert, Stand 17.11.)
- Knuth-Morris-Pratt Algorithmus
- Keyword Trees I: Motivation, Konstruktion, Failure Links
- Keyword Trees II: Aho Corasick Algorithmus; Suche mit Wildcards (Korrigierte Version, 25.11.2005)
- Suche mit regulären Ausdrücken; Suche mit Suffix-Bäumen /Stand 1.12.2005)
- Ukkonen's Algorithmus zur Konstruktion von Suffixbäumen
- Konstruktion grosser Suffixbäume; MUMmer
- Suffixarrays
- Einführung in das approximative Stringmatching; Editabstand und Alignments
- Dynamische Programmierung zur Berechnung des Editabstands
- Weihnachten
- End-Free Alignment; Lokales Alignment; Alignment mit Gaps (Korrigierte Version, 11.1.2006)
- Gastvorlesung, Dr. Piepenbrock, CIO Epigenomics AG, Berlin: "Bioinformatik bei Epigenmics"
- Alignment mit linearem Platzbedarf; k-Band Alignment
- Gastvorlesung, Dr. Klein, Metanomics GmbH Berlin: "Bioinformatik in der Pflanzengenomik"
- Substitutionsmatrizen: PAM und BLOSUM
- Alignment mit k Unterschieden (BYP); Heuristiken zum Alignment: BLAST und Gapped BLAST
- FASTA und BLAT
- Quasar; Celera-Assembler
- Multiples Sequenzalignment, Sum-of-Pairs Score
- Progressives und iteratives MSA; Profilalignment, Center-Star Algorithmus; Clustal W
- Einführung in die Phylogenie
- Ultrametriken, UPGMA, additive Bäume, Neighbor Joining
- Perfect Phylogeny und Maximum Parsimony
- Abschluss: DNA Computing
Weitere Materialien
- Erläuterungen zu Suffixbäumen (J, Kleffe, FU Berlin)
- Sehr schöne und umfassende Erläuterungen von Stringalgorithmen inklusive Demonstration und Visualisierung (Charras & Lecroq, Université de Rouen)
- Java-Script Animation zur Berechnung des Editabstandes zweier Zeichenketten
- 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
- Lesk: "Bioinformatik - Eine Einführung", Spektrum Akademischer Verlag.
- 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
- Attwood, Parry-Smith, "Introduction to Bioinformatics", Prentice Hall