PSMB_Seqan_2015_p3

Einleitung

Eines der bekanntesten und meist-genutzten Programme im Kontext der Bioinformatik ist NCBI Blast. Blast ist ein heuristisches Tool zum Finden von bedeutenden lokalen Alignments zwischen Eingabesequenzen und einer Datenbank. Mehrere, z.T. deutlich schnellere Programme als Blast existieren bereits, doch diese haben oft eine niedrigere Sensitivität, da sie andere Algorithmen und Heuristiken verwenden.

Aufgabe dieses Software-Projekts ist es den Blast-Algorithmus in seiner häufiggenutzen BlastX-Variante (Suchen von DNA-Sequenzen in Protein-Datenbanken) möglichst genau nach zu entwickeln. Für wesentliche Schritte des Algorithmus und des "Drumherum" kann dabei auf bestehende Funktionalität in SeqAn zurückgegriffen werden, nicht jedoch für alle. Am Ende sollte ein vollständiges Programm entstehen, das dieselben Ergebnisse produziert wie NCBI BlastX. Es wäre zu hoffen, dass eine effiziente Implementierung auf Basis von SeqAn außerdem schneller wäre als NCBI BlastX.

Programmschritte

• Einlesen der Daten [sequence_IO-Modul]
• Übersetzen von DNA in Proteinsequenzen [translation-Modul]
• Seeding-Phase [könnte mit dem find-Modul gemacht werden]
• Verification-Phase [hier können erstmal das align-Modul und das align_extend-Modul und/oder das seed-Modul verwendet werden]
• scoring, Berechnen von e-Werten [blast-Modul]
• Schreiben der Ausgabe-Dateien [blast-Modul]

Zusatzpunkte gibt es für das einfache Verwenden von Parallelisierung! Bei ausreichender Zeit ließen sich in der Verification-Phase auch noch Algorithmen anpassen bzw. hinzufügen.

Ergebnisse für die/den Studierende/n

• Lesen und verstehen von wichtigen Algorithmen
• Arbeiten mit existierendem Code und Dokumentation
• Eigenes Umsetzen von algorithmischen Ideen in Code
• Entwickeln einer voll funktionierenden SeqAn-Anwendung

Literatur

Da die Primärquellen zu Blast nicht sehr eingängig sind empfehle ich zu erst mit den kurzen Zusammenfassungen in meiner Master-Arbeit anzufangen: http://www.mi.fu-berlin.de/en/inf/groups/abi/theses/master_dipl/hauswedell/msc_thesis_hauswedell.pdf

Inbesondere Section 2.2.1 zum Algorithmus der Seeding-Phase und Section 2.3.1 zum Algorithmus des Verification-Phase.

Original Paper:

• Blast1 1990 http://www.ncbi.nlm.nih.gov/pubmed/2231712
• Gapped Blast 1997 http://nar.oxfordjournals.org/content/25/17/3389.full
• BLAST+ 2009 http://www.biomedcentral.com/1471-2105/10/421

Comments