Die Vorlesung gehört zum Grundkanon des Bioinformatikstudiums (4. Fachsemester) und behandelt algorithmische Ansätze der Bioinformatik. Grundlegende Techniken des Algorithmenentwurfs, der Algorithmik, der Graphentheorie, der mathematischen Optimierung und Datenanalyse, sowie probabilistische Modelle und maschinelles Lernen werden eingeführt und auf Bioinformatikprobleme angewendet.
Die Vorlesung ist der erste Teil eines zweisemestrigen Zyklus.
Teil I konzentriert sich auf Algorithmenanalyse sowie diskrete und kombinatorische Techniken,
Teil II auf speziellere Methoden der kombinatorischen Optimierung und probabilistische Verfahren.
Der Zyklus kann dann im 6. FS oder Master durch unabhängige, weiterführende Spezialvorlesungen der algorithmischen Bioinformatik ergänzt werden:
Teil III Netzwerk-Theorie und Graphalgorithmen, Teil IV Algorithmische Systembiologie, Teil V Algorithmen auf Sequenzen, Teil VI: Bäume und Graphen.
Themen der Vorlesung Algorithmische Bioinformatik I sind:
- Analyse von Algorithmen: Asymptotisches Verhalten, Rekurrenzgleichungen
- Entwurfsmethoden für Algorithmen: Rekursion, Divide-and Conquer, Dynamische Programmierung, Greedy- Algorithmen, Branch-and-Bound
- Suchen in Texten: Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin, Aho-Corsasik, Z-Algorithmus
- Suffix-Trees/Tries/Arrays: Konstruktion (Ukkonens Algorithmus) und Anwendungen
- Fragment Assembly, Partial (PDP) und double (DDP) digest problems
- Sequenzanalyse: Paarweises Sequenzalignment (Needleman-Wunsch, Smith-Waterman, Gotoh) und Scoring (edit-Distanz, Distanz- und Ähnlichkeitsmaße), Motivsuche
- Multiples Alignment (n-dim. DP; heuristische Verfahren; approximative Methoden; Baum-, Consensus-, Profil- und Center-Star-Verfahren; DiAlign; ClustalW)
- NP-Vollständigkeit: Reduzierbarkeit, NP-vollständige Probleme in der Bioinformatik
Das Modul besteht aus einer Vorlesung sowie Übungen in kleinen Gruppen. Die in der Vorlesung besprochenen Inhalte werden im Übungsteil anhand von praktischen Anwendungen eingeübt.