Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Die 4-stündige Vorlesung (Halbkurs) 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, biotechnologische Verfahren) werden die folgenden algorithmischen Probleme behandelt: Exaktes Stringmatching, Stringmatching mit mehreren Pattern, approximatives Matching, 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.

Prüfungen

Prüfungen sind mündlich. Die Vorlesung ist als Halbkurs der praktischen Informatik anrechenbar.

Ort / Zeit:

• Dienstag, 13.00 - 15.00, RUD25 3.101
• Mittwoch, 11.00 - 13.00, RUD25 3.101

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).

• 19.10.2004 Administratives, Einleitung und Überblick
• 20.10.2004 Einführung in die Molekularbiologie: Leben, Wasser, Peptidbindung (Gastdozent Prof. Frömmel)
• 26.10.2004 Einführung in die Molekularbiologie II (Gastdozent Prof. Frömmel)
• 27.10.2004 Proteinstrukturen und enzymatische Reaktionen (Gastdozent Prof. Frömmel)
• 02.11.2004 Proteinstrukturen und enzymatische Reaktionen II (Gastdozent Prof. Frömmel)
• 03.11.2004 DNA, Nukleinsäuren, Erbinformation (Gastdozent Prof. Frömmel)
• 09.11.2004 Strings und Stringvergleiche, Sequenzierung
• 10.11.2004: Z-Box Algorithmus
• 16.11.2004: Bioethik (Gastdozent Prof. Frömmel)
• 17.11.2004: Boyer-Moore Algorithmus (Korrigierte Fassung, 24.11.2004)
• 22.11.2004: Knuth-Morris-Pratt Algorithmus (Korrigierte Fassung, 23.11.2004)
• 23.11.2004: Keyword Trees I: Keyword Trees und Failure Links
• 30.11.2004: Keyword Trees II: Aho Corasick Algorithmus; Suche mit Wildcards; Suche mit regulären Ausdrücken
• 01.12.2004: Suffix-Bäume
• 07.12.2004: Ukkonen's lineare Algorithmus zur Suffixbaumkonstruktion
• 08.12.2004: Gastvorlesung "Einführung in die Systembiologie", Edda Klipp, Max-Planck-Institut für molekulare Genetik
• 14.12.2004: Suffixarrays und Algorithmen zur Konstruktion grosser Suffixbäume
• 15.12.2004, 11-13 Uhr: Einführung in das approximative Stringmatching; Edit-Abstand und Editgraphen
• 15.12.2004: 13-15 Uhr: Dynamische Programmierung
• 21.12.2004 Weihnachten
• 22.12.2004 Weihnachten
• 28.12.2004 Weihnachten
• 29.01.2005 Weihnachten
• 04.01.2005: Entfällt
• 05.01.2005: Entfällt -> Übung, Vorstellung der Aufgabe 9
• 11.01.2005: End-Free Alignment; Lokales Alignment; Alignment mit Gaps
• 12.01.2005: Alignment mit linearem Platzbedarf; k-Banded Alignment (Korrigierte Fassung; 12.1.2005)
• 18.01.2005: Scorematrizen: PAM und BLOSUM; Alignment mit k-Differences (Korrigierte Fassung; 18.1.2005)
• 19.01.2005: Heuristiken zum Alignment: BLAST, Gapped BLAST, FASTA
• 25.01.2005: Enfallen wegen Krankheit
• 26.01.2005: Gastvorlesung "Industrielle Bioinformatik", Bernd Drescher, RZPD
• 01.02.2005: BLAT und Quasar
• 02.02.2005: Multiples Sequenzalignment, Sum-of-Pairs; PSI-BLAST (Korrigierte Version, 6.2.2005)
• 08.02.2005: Progressives und iteratives MSA
• 09.02.2005: Phylogenie, Ultrametriken, Additive Bäume
• 15.02.2005: Perfect Phylogeny und Maximum Parsimony (Korrigierte Version, 16.2.2005)
• 16.02.2005: Abschluss

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