Fortgeschrittene Methoden in der Bioinformatik (Vorlesung, Praktikum, Modul 10-INF-BIO4)
News
- Modulregistrierung
- Modulbeschreibungen
- Terminwuensche zur Klaerung von Fragen bitte an choener@bioinf. Koordinieren Sie sich bitte vorher innerhalb Ihrer Themengruppe.
-
Gruppen:
- byr-gui-2010: Felix, Franziska, Olli, Pascal
- wu-2004: Christian, Lukas, Basti, Verena
- sni-rao-2002: Elias, Michael, Jakob, Sandra
- taz-has-2013: Markus, Thomas, Antje, Lily
-
Aufgaben (mit Update vom 18.6.):
- Newick Parser (sollte einen pylogenetischen Baum erstellen); zurueckschreiben eines Baumes ins Newick Format
- Der Aho Build Algorithmus: (a) von Tripeln zu Aho (bzw. Ausgabe das die Tripel inkonsistent sind); (b) gegeben einen Baum (zB. via Newick eingeparsed) alle Tripel ausgeben
- Der jeweils ausgesuchte Algorithmus: jedes Paper beschreibst eine Heuristik um aus gegebenen Tripeln einen phylogenetischen Baum moeglichst gut zu rekonstruieren. Der Algorithmus soll implementiert werden.
- Suchen Sie sich Beispiele. Newick-Dateien aus dem Netz in verschiedener Groesse. Selbst geschriebene (auch sehr kleine!) Testdateien. Eventuell ein Generator fuer zufaellige Baeume.
- Konvertieren von Newick-Dateien in Tripel (sollte siehe oben!): die Liste der Tripel sollte dann mit Fehlern versehen werden. Loeschen von einzelnen Tripeln; Aenderungen in Tripeln (zB ab|c nach ac|b ; etc). Die Heuristiken haben die Aufgabe nun einen moeglichst guten Baum aus solchen fehlerbehafteten Tripel-Listen zu erzeugen.
- Welche Laufzeiten haben Ihre Heuristiken fuer Tripellisten mit k Zeilen, bzw. n Blaettern?
- Ende-Offen: Koennen Sie ihre Heuristiken verbessern? Verbesserungen in Qualitaet oder Geschwindigkeit sind hier moeglich. Diese Aufgabe ist nicht trivial! Wie man an der Literatur sehen kann, gibt es hier noch einiges an Forschungsbedarf. Selbst wenn Sie keine bessere Heuristik erstellen koennen, so waere es doch sehr praktisch wenn Sie von Versuchen und Fehlschlaegen berichten koennen.
- Wichtig: Sie sollten kommunizieren wie weit Sie bisher sind. Entweder per Mail oder bei Problemen mit einem Terminwunsch.
-
Abschlussbesprechung und Pruefung: (Update vom 1. Juli 2015)
-
Wir treffen uns, wie geplant, mit Allen zur Abschlussbesprechung am 13.07. Es wird von jeder (Vierer-Gruppe) die aktuelle Stand vorgestellt. Hier ist wichtig das sie als Vierer-Gruppe koordiniert sind, da wir einen Vortag je Paper moechten!
- Jede Vorstellung sollte 20-30 Minuten Dauer nicht ueberschreiten. Es sollte (unter anderem) vorkommen:
- eine kurze Beschreibung der entsprechenden Heuristik. "Was tut die Heuristik"
- die Laufzeit- und Speicherbedarfseigenschaften (passen die empirisch ermittelten Daten zur asymptotischen Angabe im Paper?)
- Qualitaet des ausgegebenen Baumes (wenn sie Tripel mit so-und-soviel Fehlern haben, wie gut ist der produzierte Baum?)
- Da jaweils min. 2 Implementationen pro Heuristik vorhanden sind: welche Unterschiede zwischen ihren Implementationen gibt es? Gibt es zum Beispiel eine Datenstruktur die ihnen die Implementation einfach gemacht hat?
-
Pruefung / Schein:
- Wer fertig ist (die Algorithmen funktionieren, es gibt keine groesseren Probleme) kann vor der Abschlussbesprechung auch gleich die muendliche Pruefung (Thema ist der Vorlesungsstoff) hinter sich bringen und ist dann mit der Vorlesung durch.
-
Fuer diejenigen die bis zum 13.07. nicht fertig sind gilt
folgendes:
- sie kommen trotzdem zur Besprechung am 13.07.
- wir werden einen zweiten Termin fuer Vorlesung und Besprechung im Herbst anbieten
- sie haben den Sommer (bis Sept. / Okt.) Zeit sich vorzubereiten (funktionierende Implementationen + Pruefung)
- es gibt die Moeglichkeit den Fortschritt zu diskutieren in weiteren Besprechungen
- Bitte per Email an choener@bioinf bis spaetestens 10.7. mitteilen was gewuenscht ist.
-
Wir treffen uns, wie geplant, mit Allen zur Abschlussbesprechung am 13.07. Es wird von jeder (Vierer-Gruppe) die aktuelle Stand vorgestellt. Hier ist wichtig das sie als Vierer-Gruppe koordiniert sind, da wir einen Vortag je Paper moechten!
Praktikum
Das Praktikum findet wie folgt statt:
| Raum: | 109, Härtelstr. 16-18 |
| Zeit: | nach Vereinbarung |
| Datum: | 01.07.15 - 10.07.15 |
| Endbesprechung: | 13.07.15 ab 16 Uhr |
Vorlesung
|
| VL | Datum | Material | Thema |
|---|---|---|---|
| VL 01 | 17.04.15 | ||
| VL 02 | 24.04.15 | ||
| Tag der Arbeit! | 01.05.15 | Feiertag | |
| VL 03 | 08.05.15 | (15:00 - 16:30) Besprechung: Implementationen von Parser und Aho-Algo. (16:30 - 18:00) Vorlesung | |
| VL 04 | 11.05.15 13:15-14:30 Uhr |
||
| Brückentag | 15.05.15 | keine Vorlesung | |
| Besprechungstermine | 01.--03. 07.15 | ||
| Besprechungstermine | 06.--07. 07.15 | ||
| Endbesprechung | 13.07.15 16:30 Uhr |
Literatur
Aho, et al (1981). Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comput. 10(3) 405-421
Wu (2004). Constructing the Maximum Consensus Tree from Rooted Triples. J.Comb.Opt 8,29-39
Hellmuth, et al (2014). Phylogenomics with Paralogs. submitted
Gasieniec, et al (1999). On the Complexity of Constructing Evolutionary Trees. J.Comb.Opt 3,183-197
Byrk, et al (2010) New results on optimizing rooted triplets consistency. Disc.Appl.Math 158,1136-1147
Snir, Rao (2006) Using Max Cut to Enhance Rooted Trees Consistency. Trans.Comp.Bio.BioInf 3(4),323-333
Maemura, et al (2007) Approximation Algorithms for Constructing Evolutionary Trees from Rooted Triplets.
Tazehkand, et al (2013) New Heuristics for Rooted Triplet Consistency. Algorithms 6, 396-406
Lechner, et al (2011) Proteinortho: Detection of (Co-)orthologs in large-scale analysis. 12(124)
Paper hier Download verfuegbar (uni-intern!)