Page PSMB_Seqan_2013_Suboptimal_Alignments

Hintergrund: Suboptimale Alignments

Lokale Alignments sind eine mächtige Methode um Sequenzhomologien zwischen zwei Sequenzen zu bestimmen. Der Smith-Waterman-Algorithmus [1] nutzt dynamische Programmierung um das beste lokale Alignment zwischen zwei Sequenzen zu berechnen. Dies stellt jedoch eine gewisse Einschränkung dar, da man oft weitere homologe Regionen zwischen den beiden Sequenzen identifizieren möchte. Durch anpassen des Scoring-Schemas lassen sich leichte Abwandlungen vom optimalen Alignment erzwingen, jedoch löst das nicht das generelle Problem. Der Waterman-Eggert-Algorithmus [2] ist eine einfache aber geschickte Erweiterung des Lokalen-Alignment-Algorithmus wobei alle nicht überlappende, suboptimalen, lokalen Alignments zwischen zwei Sequenzen gefunden werden. Der Algorithmus arbeitet wie folgt: Als 1. wird das optimale lokale Alignment berechnet. Im 2. Schritt wird die Scoring-Matrix nur in dem Bereich des gefundenen Alignments so neu berechnet, dass kein weiteres suboptimales, lokales Alignment mit dem bisher gefundenen überlappt. Anschließend wird das nächste subotimale lokale Alignment gefunden. Dies geschieht so lange bis entweder der Score des gefundenen Alignments unter einen gegebenen Threshold fällt oder k suboptimale Alignments gefunden wurden.

Aufgaben

Ziel dieser Aufgabe ist es, den Waterman-Eggert Algorithmus zu implementieren. Eingabe des Programms sind zwei FASTA-Dateien mit den beiden Sequenzen, der Threshold t und die Anzahl maximal gefundener suboptimaler Alignments k. Als Ausgabe soll das Programm alle gefundenen Alignments in einer Datei herausschreiben. Es sollen sowohl Tests entwickelt werden, die die Funktionalität auf Korrektheit überprüfen, als auch real Daten mit dem entwickelten Algorithmus prozessiert werden. Das Program soll sowohl für DNA-Sequenzen als auch für Proteinsequenzen funktionieren. SeqAn bietet eine Reihe von Möglichkeiten entsprechende Bewertungsschemata zu selektieren.

Die Aufgabe ist für ein bis zwei Teilnehmer gedacht, wobei folgende Bereiche behandelt werden:

• Teil 1: Implementierung des Waterman-Eggert Algorithmus für lineare Gapkosten.
• Teil 2: Erweiterung des Waterman-Eggert Algorithmus für affine Gapkosten.
• Teil 3: Ausgiebiges Testen der entwickelten Methoden.
• (Optional): Integration in das neue Alignment-Modul von SeqAn.

Für die Bearbeitung der Aufgabe sollen Sie SeqAn benutzen.

Die folgenden Teile von SeqAn sind relevant:

• Das Alignment Modul: Alignment Representation und Scoring Schemes
• Das I/O-Modul: Sequence I/O.

References

• [1] http://en.wikipedia.org/wiki/Smith-Waterman Smith-Waterman-Algorithmus
• [2] A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons. Waterman, M. S., Eggert, M. (1987). J. Mol. Biol. Volume 197, Issue 4, 20 October 1987, Pages 723–728.

Comments