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

Diese vierstündige Vorlesung behandelt grundlegende Algorithmen der Bioinformatik. Nach einer ausführlichen Einführung in die Grundlagen der Molekularbiologie (Gene und Genome, Expression, Proteine, biotechnologische Verfahren) werden die folgenden algorithmischen Probleme diskutiert: Stringmatching und Alignment, Multiples Alignment, Pattern Matching, Motifsuche und -erkennung, Hidden Markov Modelle, Phylogenetische Bäume, etc.

Voraussetzungen

Voraussetzung für den Besuch sind grundlegende Kenntnisse in Algorithmen. Kenntnisse in der Molekularbiologie werden nicht vorausgesetzt.

Prüfungen

Die Vorlesung kann als Halbkurs geprüft werden.

Die Prüfungstermine stehen nun fest:

Ort / Zeit:

• Mittwoch, 11.00 - 13.00, RUD26 1'306
• Freitag, 11.00 - 13.00, RUD26 1'305

Literatur zur Vorlesung

• Dan Gusfield, "Algorithms on Strings, Trees, and Sequences", Cambrige University Press. Die Vorlesung folgt in grossen Teilen diesem Buch.
• Böckenhauer, Bongartz, "Algorithmische Grundlagen der Bioinformatik", Teubner Verlag.
• Koolman, Röhm, Wirth, "Taschenatlas der Biochemie", Thieme Verlag. Für die molekularbiologischen Grundlagen.

Themen im Einzelnen

(Folien sind hier jeweils vor der Vorlesung als PDF verfügbar. Änderungen möglich):

• 22.10.2003 Entfällt
• 24.10.2003 Administratives, Einleitung und Überblick
• 29.10.2003 Einführung in die Molekularbiologie: Leben, Wasser, Peptidbindung(Gastdozent Prof. Frömmel)
• 31.10.2003 ... Proteine - Peptide - Aminosäuren
• 05.11.2003 ... Proteinstrukturen und enzymatische Reaktionen
• 07.11.2003 ... DNA, Nukleinsäuren, Erbinformation
• 12.11.2003 ... Enyzme, Biokatalyse
• 14.11.2003 ... Stoffwechsel, Evolution
• 19.11.2003: Motivation Stringvergleiche, Z-Algorithmus (Folien in korrigierter Version, 21.11.2003)
• 21.11.2003: Z-Algorithmus
• 26.11.2003: Entfallen wegen Streik
• 28.11.2003: Entfallen wegen Streik
• 03.12.2003: Entfallen wegen Streik
• 05.12.2003: Entfallen wegen Streik
• 10.12.2003: Boyer-Moore Algorithmus (Korrigierte Version, 18.2.2004)
• 12.12.2003: Knuth-Morris-Pratt Algorithmus (Korrigierte Version, 18.2.2004)
• 17.12.2003: Keyword Trees und Aho-Corasick Algorithmus I (Korrigierte Version, 20.12.2003)
• 19.12.2003: Keyword Trees und Aho-Corasick Algorithmus II
• 24.12.2003 Weihnachten
• 26.12.2003 Weihnachten
• 31.12.2003 Weihnachten
• 02.01.2004 Weihnachten
• 07.01.2004: Suffixbäume und Anwendungen (Korrigierte Version, 7.1.2004)
• 09.01.2004: Ukkonen's Algorithmus zur linearen Konstruktion von Suffixbäumen (Korrigierte Version, 10.1.2004)
• 14.01.2004: Suffixarrays; Suffixbäume auf Sekundärspeichern
• 16.01.2004: Approximativer Stringvergleich, EDIT-Abstand, Alignierung (Korrigierte Version, 20.1.2004)
• 21.01.2004: Dynamische Programmierung, Ähnlichkeit, Needlemann-Wunsch (Korrigierte Version, 21.1.2004)
• 23.01.2004: Lokales Alignment, Smith-Waterman, (Gapped alignment, Alignment mit linearem Platz) (Korrigierte Version, 4.2.2004)
• 28.01.2004: Gastvortrag: Bioethik (Dozentin: Dr. Himmelmann, Institut für Philosophie)
• 30.01.2004: Gapped alignment, Alignment mit linearem Platz
• 04.02.2004: Scoring Matrizen PAM, BLOSUM; Heuristiken BLAST, FASTA
• 06.02.2004: Heuristiken BLAST, FASTA
• 11.02.2004: Weitere Heuristiken: BLASTX, BLAT, Quasar (Korrigierte Version, 11.2.2004)
• 13.02.2004: Multiples Alignment I
• 18.02.2004: Gastvortrag: Industrielle Bioinformatik (Dozent: Dr. Bernd Drescher, RZPD)
• 20.02.2004: Zusammenfassung, Werbung, Feedback, 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

• David Mount, "Bioinformatics: Sequence and Genome Analysis", Cold Spring Harbor Laboratory Press
• R. Merkl, S. Waack, "Bioinformatik Interaktiv - Algorithmen und Praxis", Wiley-Ch
• T. Attwood, D. Parry-Smith, "Introduction to bioinformatics", Prentice Hall