PISB SeqAn - Teilprojekte Segment-Aligner

Hintergrund: Hierarchisches Genomalignment

Um das Alignment ganzer Genome zu ermöglichen, werden in der Regel zunächst lokale Alignments berechnet und anschließend zu einem globalen Alignment verknüpft. Dabei kann es passieren, dass Segmente der Genome nicht von lokalen Alignments abgedeckt sind und unaligniert bleiben.

Die Grundidee von hierarchischem Alignment ist es, rekursiv unalignierte Abschnitte des Alignments aufzufüllen, indem in diesen Bereichen mit sensitiveren Parametern lokale Alignments berechnet werden. Ein Aligner, der diesen Ansatz verfolgt, besteht beispielsweise aus folgenden Schritten:

1. Lokales Alignment auf den Input-Sequenzen
2. Chaining der lokalen Alignments zu einer Kette
3. Auffinden der unalignierten Abschnitte innerhalb der Kette
4. Rekursives Auffüllen der unalignierten Abschnitte

Diese Strategie kann man zum Beispiel im Programm LAGAN von Brudno et al. [1] wiederfinden und soll auch in diesem Projekt verfolgt werden.

Aufgaben

Das Ziel dieser zwei Teilprojekte ist es, gemeinsam einen hierarchischen Genomaligner mit Hilfe von Komponenenten aus der C++-Bibliothek SeqAn zu implementieren. Die Grundlage in SeqAn bildet die Datenstruktur AlignmentGraph, mit der das Alignment Segment-basiert berechnet werden kann.

Die oben genannten vier Schritte sollen wie folgt umgesetzt werden:

1. Mit dem SeqAn-Tool STELLAR [4] sollen paarweise lokale Alignments auf den Input-Sequenzen berechnet werden. Die lokalen Alignments nennen wir segment matches.
2. Das Chaining soll angelehnt an das Programm SeqAn::T-Coffee [3] umgesetzt werden. Das bedeutet, es soll ein Segment-basiertes Alignment mit den folgenden Schritte berechnet werden:
   • Segment Match Refinement [5]: Überlappende segment matches werden minimal zerschnitten.
   • Consistency Extension (vgl. T-Coffee [2]) um miteinander konsistente Alignmentbereiche zu bestärken
   • Progressives Alignment [6] auf den Segmenten
3. Als Ausgabe des zweiten Schrittes erhalten wir einen Alignment-Graphen. Um unalignierte Abschnitte zu finden, soll über diesen Alignment-Graphen iteriert werden.
4. Die Schritte 1-3 sollen rekursiv wiederholt werden, bis alle Lücken gefüllt sind oder keine lokalen Alignments mehr gefunden werden. Im rekursiven Aufruf soll STELLAR mit immer sensitiveren Parametern aufgerufen werden.

Modul - Segment-Aligner a)

Rekursionsende

Zum Rekursionsende gehört der Aufruf von STELLAR sowie die Schritte des Chainings. STELLAR soll auf allen Paaren von Input-Sequenzen aufgerufen werden. Für die Schritte Segment Match Refinement, Consistency Extension und progressives Alignment müssen die entsprechenden Funktionen aus SeqAn zusammengebracht werden, so dass am Ende ein Alignment-Graph besteht. Das Rekursionsende soll als Funktion zum Aufruf aus Teilprojekt b) implementiert werden.

Modul - Segment-Aligner b)

Rekursiver Aufruf

In diesem Teilprojekt sollen die unalignierten Abschnitte des Alignments gefunden werden, indem über den in Teilprojekt a) berechneten Alignment-Graphen iteriert wird. Auf diesen Abschnitten soll die Funktion aus Projekt a) rekursiv aufgerufen werden und der Alignment-Graph des Abschnittes in den Alignment-Graphen der gesamten Genome integriert werden.

Referenzen

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

[1] 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
[2] 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
[3] 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
[4] Kehr, B. and Weese, D. and Reinert, K., STELLAR: fast and exact local alignments, BMC Bioinformatics, 2011
[5] Vorlesung Match Refinement
[6] Vorlesung Multiples Alignment