BLAST Implementation in SeqAn

Es soll ein BLASTX (Nukleotidsequenz 6-fach translatieren und gegen Proteindatenbank abgleichen) 'from scratch' für die SeqAn-Bibliothek erstellt werden.

Ideen des Algorithmus'

1. Vorbereitung:
   • Nukleotidsequenzen einlesen und translatieren (6-frame)
   • Translatierte Sequenzen für Suche vorbereiten (ESA Suchbaum 'A') (generisch, sodass ESA-Index durch FM-Index ausgetauscht werden kann)
   • Proteindatenbank einlesen und für Suche vorbereiten (ESA Suchbaum 'B') (generisch, sodass ESA-Index durch FM-Index ausgetauscht werden kann)
   • Beide Bäume sind alphabetisch geordnet
2. Matching:
   • Fehler beim Vergleich zweier Aminosäuren müssen durch einen Threshold begrenzt werden
   • Fehler werden durch eine Substitutionsmatrix (PAM/ BLOSUM) gewichtet
   • Fehler werden auf die Länge der bislang gefundenen Sequenz normalisiert (Gedanken machen und Lösung überlegen)
   • Problem: Da die Suchbäume vom Anfang zum Ende der translatierten Sequenzen aufgebaut werden, könnte es Probleme mit Sequenzen geben die schlechtes Matching am Anfang, jedoch gutes Matching am Ende vorweisen. Diese Sequenzen würde möglicherweise zu früh aussortiert --> Gute Lösung überlegen (eine Möglichkeit wäre Backtracking)
3. Hauptidee:
   • Iteriere durch Baum 'A' und 'B' parallel, sodass jede Kante beider Bäume maximal einmal besucht wird
4. Ablauf: (für alle Vergleiche wird das Matching verwendet)
   • Suche die 1. Sequenz (alphabetisch) aus 'A' in 'B' so weit wie möglich
   • Wenn gefunden: --> Auswertung
   • Gehe eine Ebene hoch und suche nächste Sequenz (alphabetisch) aus 'A' in 'B' (wenn erste und zweite Sequenz ein gemeinsames Prefix haben muss dieses nicht erneute verifiziert werden)
   • Wenn gefunden --> Auswertung
   • …
   • Ende: Iterator für 'A' ist fertig
5. Auswertung:
   • Für alle in 4. gefundenen Sequenzen durchführen
   • Berechne Signifikanzniveau (hat 'Stellar' für Nukleotide?)
   • Ausgabe im BLAST-Stil

Eingabe

• Substitutionsmatrix: BLOSUM/ PAM (sind die in SeqAn bereits implementiert?)
• Threshold (für Matching)
• Nukleotidsequenz (FASTA)
• Proteindatenbank

Basis Programm

• Einlesen der Datenbank und der Pattern
• Erstellen zweier generischer Suchbäume (ESA-Index, FM-Index) für Datenbank und Pattern
• Paralleles exact Matching der Pattern in der Datenbank
• Ausgabe in Blast-Stil
• Vergleich mit bestehenden Tools

Erweiterungen

• Entwicklung einer normalisierten Nachbarschaftsumgebung
• Backtracking um die normalisierten Nachbarschaftsumgebung anzuwenden

Anmerkungen vom 06.07.12

• IM Gespräch mit Prof. Reinert wurde vereinbart, dass zwei Implmentierungen mit einander verglichen werden:

1. In einem ersten Schritt werden erst alle Strings der Nachbarsch erstellt und dann ein Suchbaum aus diesen generiert
2. Die "Nachbarschaftspattern" werden erst on the fly erzeugt

• Interessante Fragestellungen sind dann die Geschwindigkeit und der Speicherverbrauch im Vegleich.

Zeitplan

• Planung/ Vorbereitung - 1 Woche
• Algorithmus implementieren - 3 Wochen
• Fehlerbehebung/ Verfeinerung der Implementierung - 1 Woche
• SeqAn-Tests schreiben - 1 Woche
  • Dient zur Stabilität der einzelnen Funktionen des Algorithmus
• Programme vergleichen - 1 Woche
  • Wie schlägt sich das eigene Programm im Vergleich mit NCBI-BLASTX/ WU-BLASTX (Laufzeit/ Speicherbedarf)?
  • Vergleichsdaten auswerten/ grafisch darstellen
• Bachelorarbeit (Dokument) anfertigen - 2 Wochen
• Zeitlicher Puffer - 1 Woche

Wochenbericht

Vorbereitung:

• Grobe Planung des Algorithmus/ Einlesen in Paper mit verwandten Themen
• Einrichten von SeqAn unter Ubuntu (Sandbox, App erstellen)
• Einlesen von FASTA-Dateien (Code bereits im Softwareprojekt [Mai 2012] entwickelt)

10.07.2012, Woche 1:

• Anmeldung zur Bachelorarbeit
• 6-Frame-Translation (DNA → Protein in 6 Leserastern)
• Erstellen des Index für Sequenz- und Datenbankbaum (ESA)
• Exakte Suche der Sequenzen im Datenbankbaum

17.07.2012, Woche 2:

• Algorithmus zur Erstellung der normalisierten Nachbarschaft (BLOSUM62) von Proteinen implementiert
• Exakte Suche der gesamten Sequenz-Nachbarschaft im Datenbankbaum
• Ausarbeitung des Algorithmus (Treffen mit Jochen Singer und Prof. Reinert)

24.07.2012, Woche 3:

• Neuer Ansatz: Nicht erst die gesamte Nachbarschaft erstellen und exakt suchen, sondern während der Suche normalisierte Nachbarschaft einbeziehen.

31.07.2012, Woche 4:

• Implementierung kleinerer Funktionen
• Umsetzung der Such-Funktion

07.08.2012, Woche 5:

• Implementierung kleinerer Funktionen
• Umsetzung der Such-Funktion

14.08.2012, Woche 6:

• Implementierung der Ausgabe (ähnlich wie NCBI-BLASTX)
• Fehlersuche, Optimierung des Codes

21.08.2012, Woche 7:

• Implementierung der Eingabeparameter (Query, Database, Output, Cutoff, Treshold, SeedLength, ReportLength)
• Fehlersuche, Optimierung des Codes

28.08.2012, Woche 8:

• Planung, Umsetzung und Auswertung der Versuche (vergleiche seqan::BLASTX mit NCBI-BLASTX)
• Datensatz: Hefe-Datenbank von NCBI
• Versuch 1: Sensitivität
• Versuch 2: Arbeitsspeicher und Laufzeit
• Statistische Auswertungen implementiert (Bitscore S' und Erwartungswert E), neuer Eingabeparameter: Evalue
• Start: Schreiben der Bachelorarbeit

04.09.2012, Woche 9:

• Schreiben der Bachelorarbeit

11.09.2012, Woche 10:

• Schreiben der Bachelorarbeit
• Quellcode kommentieren
• Wiki-Einträge aktualisieren (zum Teil Gedächtnisprotokoll…)

18.09.2012, späteste Abgabe!