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
- NP-Vollständigkeit: Reduzierbarkeit, NP-vollständige Probleme in der Bioinformatik
- Fragment Assembly, Partial (PDP) und double (DDP) digest problems
- Suchen in Texten: Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin, Aho-Corsasik, Z-Algorithmus
- Suffix-Trees/Tries/Arrays: Konstruktion (Ukkonens Algorithmus) und Anwendungen
- 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)
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.
The lecture is part of the basic canon of the bioinformatics course (4th semester) and covers algorithmic approaches in bioinformatics.
Basic techniques of algorithm design, algorithmics, graph theory, mathematical optimization and data analysis, as well as
probabilistic models and machine learning are introduced and applied to bioinformatics problems.
The course is the first part of a two-semester cycle.
Part I focuses on algorithm analysis and discrete and combinatorial techniques,
Part II on more specialized combinatorial optimization methods and probabilistic techniques.
The cycle can then be complemented in the 6th FS or Master by independent, more advanced special lectures in algorithmic bioinformatics: Part III Network Theory and Graph Algorithms, Part IV Algorithmic Systems Biology, Part V Algorithms on Sequences, Part VI: Trees and Graphs.
Topics of the Algorithmic Bioinformatics I lecture are:
- Analysis of Algorithms: Asymptotic behavior, recurrence equations.
- Design methods for algorithms: Recursion, divide-and-conquer, dynamic programming, greedy algorithms, branch-and-bound.
- NP-completeness: reducibility, NP-complete problems in bioinformatics.
- Fragment assembly, partial (PDP) and double (DDP) digest problems
- Searching in texts: Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin, Aho-Corsasik, Z-algorithm
- Suffix Trees/Tries/Arrays: Construction (Ukkonen's algorithm) and applications.
- Sequence analysis: pairwise sequence alignment (Needleman-Wunsch, Smith-Waterman, Gotoh) and scoring (edit distance, distance and similarity measures), motif search
- Multiple alignment (n-dim. DP; heuristic methods; approximate methods; tree, consensus, profile and center-star methods; DiAlign; ClustalW).
The module consists of a lecture and exercises in small groups. The content discussed in the lecture will be practiced in the exercise part using practical applications.
