Projektmanagement im Softwarebereich - Seqan 2011

Das ist die vorläufige Wiki-Seite zum Praktikum Projektmanagement im Softwarebereich - Seqan.

Aufteilung auf die Teilprojekte

Name	Teilprojekt
Samuel Pliska	1. QUASAR: Threshold-Berechnung
Marco Phieler	2. QUASAR: q-gramme zählen
Gerrit Bostelmann	3. BLASTn: Seeds auffinden
Marcel Steinmetz	4. BLASTn: HSPs auffinden (Extension)
Kevin Selm	5. Segment-Aligner: Unalignierte Segmente finden
Sandra Appelt	6. Segment-Aligner: rekursiver Aufruf
Evelyn Schnapka	7. Ein-/Ausgabe und Statistiken

Zeitplan

01.04.2011, 10 Uhr	Vorbesprechung
04.04 - 08.04.2011	C++-Kurs
11.04.-15.04.2011	SeqAn-Tutorial, Aufteilung der Teilprojekte
26.04.2011 11 Uhr (s.t.)	Vorstellung der Projektpläne
27.05.2011	Abgabe des Abschlussberichts
30.05.2011	Vorstellung der Ergebnisse

Grundlagen

Q-gram threshold
Gegeben seien zwei Sequenzen udn der Länge m und ein shape Q (bspw. 110010110111100111). Für ein Match der Mindestlänge n zwischen und , wieviele Q-gramme muessen die Sequenzen innerhalb eines gewissen Fensters mindestens gemeinsam haben? Siehe Kapitel 3 in [3]. Diese Mindestanzahl nennen wir die Q-gram treshold t.

Hierarchisches Alignment
Die Grundidee von hierarchischem Alignment ist es, rekursiv unalignierte Bereiche des Alignments aufzufüllen. Im Allgemeinen besteht ein Aligner dabei aus folgenden vier Schritten:

• Lokales Alignment auf den Input-Sequenzen
• Chaining der lokalen Alignments zu einer Kette
• Rekursives Auffüllen der unalignierten Abschnitte zwischen den lokalen Alignments innerhalb der Kette
• Banded Alignment um die lokalen Alignments in der Kette

Dieser Strategie folgt beispielsweise das Programm LAGAN von Brudno et al. [6].

Segment-basiertes Alignment
Auch Segment-basiertes Alignment kann man in vier Schritte aufteilen:

• Berechnen paarweiser lokaler Alignments ("segment matches") der Input-Sequenzen
• Segment Match Refinement [10]: Überlappende Segment matches werden minimal zerschnitten.
• Consistency Extension (vgl. T-Coffee [7])
• Progressives Alignment [9] auf den Segmenten

Diese Schritte sind in SeqAn::T-Coffee umgesetzt worden [8].

Das Projekt

Ziel dieses Praktikums ist, einen hierarchischen Segment-basierten Aligner zu implementieren.

Input

Eine Menge von Genomen.

Output

Multiples Sequenz Alignment im Fasta-Format.

Teilprojekte

Modul 1 - QUASAR zur Berechnung lokaler Alignments

Threshold-Berechnung

In diesem Teilprojekt soll ein Modul implementiert werden, dass die Threshold von beliebigen q-gram Shapes berechnet. Siehe auch [3].

Modul 2 - QUASAR zur Berechnung lokaler Alignments

Filtern und Verifikation (basierend auf dem Zählen von q-grammen)

Quasar [4] ist ein Q-gram basierter Filter, der genomische Regionen herausfiltert, die garantiert keine Matches enthalten. Die übrigen Region können evtl. Matches enthalten und heißen potential matches. Quasar sucht nach genomischen Regionen, die mindestens t Q-gramme gemeinsam haben.

Modul 3 - BLASTn zur Berechnung lokaler Alignments

Seeds auffinden

Hier sollen paarweise exakte Matches zweier Genome berechnet werden, die nicht mehr durch Matches erweitert werden können, aber einen Mindestscore erreichen.

Modul 4 - BLASTn zur Berechnung lokaler Alignments

Seeds vergrößern

Ausgehend von exakten Matches wie sie in Modul 3 berechnet werden soll hier eine X-drop Extension wie in BLASTn durchgeführt werden. Das Ergebnis sind paarweise lokale Alignments.

Modul 5 - Segment-Aligner

Auffinden unalignierter Segmente

In diesem Teilprojekt sollen auf einem Alignmentgraphen diejenigen zusammenhängenden Bereiche ermittelt werden, die unaligniert sind. Außerdem soll ein lokaler Aligner aufgerufen und ggf. die Matches in die richtige Datenstruktur konvertiert werden.

Modul 6 - Segment-Aligner

Rekursiver Aufruf und Integration von Subalignments

Es soll ausgehend von einer Menge lokaler Alignments der Segment-basierte Aligner implementiert werden und der rekursive Aufruf durchgeführt werden. Zusätzlich zu vielen Funktionsaufrufen bedeutet dies, dass ein Alignmentgraph eines kleineren Abschnitts mit einem Alignmentgraphen eines größeren Abschnitts gemischt werden muss.

Modul 7 - User-interface Segment-Aligner

Ein-/Ausgabe und Alignment Statistiken

Es soll ein einfach zu bedienender Command Line Parser für den Segment-Aligner erstellt und die Alignmentgraphen in einem geeigneten Format ausgegeben werden. Im Falle von sehr großen Alignments sollten statt des gesamten Alignmentgraphen zugehörige interessante und aussagekräftige Statistiken berechnet werden, beispielsweise der durchschnittliche Knotengrad oder die durchschnittliche Segmentlänge. Es wird erwartet, dass der Student seine eigenen Ideen für die Statistiken einbringt.

Referenzen

Achtung: Die Paper-Links gehen nur von der FU (bzw. VPN) aus.

[1] Vorlesung Fast Filtering Algorithms, P4 SS09
[2] Vorlesung Filtering
[3] Burkhardt, S. and Kärkkäinen, J., Better Filtering with Gapped q-Grams, Fundamenta Informaticae, 2003
[4] Burkhardt, S. and Crauser, A. and Ferragina, P. and Lenhof, H.P. and Rivals, E. and Vingron, M., q-gram Based Database Searching Using a Suffix Array (QUASAR), RECOMB, 1999
[5] Altschul, S.F. and Gish, W. and Miller, W. and Myers, E.W. and Lipman, D.J., Basic local alignment search tool, Journal of Molecular Biology, 1990
[6] Brudno, M. and Do, C.B. and Cooper, G.M. and Kim, M.F. and Davydov, E. and others, LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA, Genome research, 2003
[7] Notredame, C. and Higgins, D.G. and Heringa, J., T-coffee: a novel method for fast and accurate multiple sequence alignment, Journal of molecular biology, 2000
[8] Rausch, T. and Emde, A.K. and Weese, D. and Döring, A. and Notredame, C. and Reinert, K., Segment-based multiple sequence alignment, Oxford Univ Press, 2008
[9] Vorlesung Multiples Alignment
[10] Vorlesung Match Refinement

Vorlagen für Abschlussbericht und Präsentationen

• Latex Template
• PPT Template

Formular für regelmäßiges progress meeting

• progress meeting

Links

• Homepage von SeqAn: Hier gibt es alle Informationen sowie aktuelle Snapshots der Bibliothek zum herunterladen.
• SeqAn Dokumentation: Die Doku des letzten SeqAn-Releases.
• SeqAn Nightly-Dokumentation: Die aktuellste Version der Doku.
• SeqAn Tutorial: Einführung in verschiedene Module von SeqAn mit Übungsaufgaben.
• SeqAn Trac: System für Fehlerreports in SeqAn und direkter Einblick in den aktuellen Entwicklungsstand des Projekts. Hier könnt ihr Fehler melden, wenn ihr welche gefunden habt.

Comments