Vorlesung Algorithmische Bioinformatik I

Ziel der Veranstaltung ist es den Studenten notwendige Kenntnisse für das Verständnis, die Analyse und den Entwurf von Algorithmen in der Bioinformatik zu vermitteln. Teilnehmer erhalten einen detaillierten Überblick über grundlegende algorithmische Ansätze und ihre Anwendungen anhand wichtiger Problemstellungen in der Bioinformatik (hier insbesondere: diskrete und kombinatorische Verfahren) Die Vorlesung gehört zum Grundkanon des Bioinformatikstudiums (4.+5.FS) und behandelt grundlegende algorithmische Ansätze und ihre Anwendungen in der Bioinformatik. Themenbereiche reichen von Genomsequenzierung (Mapping und Assembly), Sequenz- und Strukturanalyse (Genvorhersage und Genstruktur, Datenbanksuche, Proteinfunktion, Proteinstrukturvorhersage, Phylogenie) bis zu Netzwerken, Expression, Genomics und Proteomics. Grundlegende Techniken des Algorithmenentwurfs und -analyse, der Graphentheorie, der mathematischer Optimierung und Datenanalyse, sowie probabilistische Modelle und maschinelles Lernen werden eingeführt und auf Bioinformatikprobleme angewendet. Die Vorlesung ist der erste Teil eines zwei-semestrigen Zyklus, Teil I konzentriert sich auf diskrete und kombinatorische Techniken, Teil II auf probabilistische Verfahren und speziellere Methoden der kombinatorischen Optimierung 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 Literatur Gusfield D., Algorithms on Strings, Trees, and Sequences, Cambridge U. Press, 1997 Durbin et al., Biological Sequence Analysis, Cambridge U. Press, 1998 Cormen, et al., Introduction to Algorithms, MIT Press, 2001 Gusfield D., Algorithms on Strings, Trees, and Sequences, Cambridge U. Press, 1997 Durbin et al., Biological Sequence Analysis, Cambridge U. Press, 1998 Cormen, et al., Introduction to Algorithms, MIT Press, 2001 Department Institut für Informatik LMU München SoSe 2015 Prof.Dr. Zimmer Ralf