Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

2 SEPs: Phylogenetische Bäume

Motivation: Bei der Berechnung phylogenetischer Bäume stellt sich die Aufgabe, ihre Qualität hinsichtlich ihrer Topologie zu evaluieren. Bei rechenaufwändigen Baumberechnungsverfahren sowie bei der Analyse sehr großer Stammbäume können konventionelle Methoden wie Bootstrapping nicht angewendet werden. Deshalb müssen effiziente Methoden entwickelt werden, die beispielsweise auf dem statistischen Vergleich bereits berechneter Bäume, sowie dem Aufbau von Konsensus-Bäumen beruhen.

In diesem SEP sollen effiziente Algorithmen für den Vergleich und die statistische Bewertung von binären Graphen, sowie für das Vereinigen mehrerer binärer Graphen mit z.T. unterschiedlicher Topologie zu einem n-verzweigten Graphen entwickelt und implementiert werden. Der Anwendungsbereich dieses SEP ist die Bioinformatik.

Die entwickelten Anwendungen sollen es ermöglichen, die Unterschiede von zwei oder mehreren zum Teil sehr großen, ungewurzelten Stammbäumen (binäre Graphen mit mehreren Tausend terminalen Knoten) zu ermitteln (Hamming-, oder Edit-Distanz). Zudem soll ein effizientes Verfahren entwickelt werden, um Stammbäume innerhalb einer Gruppe von Bäumen mit identischer bzw. sehr ähnlicher Ausstattung an terminalen Knoten bezüglich ihrer Topologie (eventuell der Distanz zwischen den terminalen Knoten) statistisch zu evaluieren. Dies soll zu einer Methode führen, aus mehreren Stammbäumen (binär) mit identischen terminalen Knoten einen, gegebenenfalls mehrfach verzweigten Konsensus-Baum zu berechnen.

Vorraussetzung: Engagement, Grundlegende Kenntnisse im Bereich der effizienten Algorithmen, sowie Erfahrungen in der Programmierung mit C/C++. Kenntnisse in und Interesse an der Bioinformatik sind begrüßenswert, aber nicht unbedingt erforderlich.

Interessenten melden sich bitte bei

Dr. Harald Meier, Raum 02.13.061, Tel. 089/289-19476
(Angewandte Bioinformatik, LRR - Prof. Dr. A. Bode);

Arno Buchner, Raum 03.13.059, 089/289-19428
(Lehrstuhl für Effiziente Algorithmen, Prof. Dr. E. Mayr);

Die Aufgabenstellung kann auch im Rahmen einer BACHELOR-ARBEIT bearbeitet werden.
Im Hauptstudium BIOINFORMATIK werden diese Arbeiten auch als Praktikum angerechnet.