Simple Bowtie

Bowtie ist ein "ultrafast and memory-efficient" Read Mapper [1] der auf der Burrows-Wheeler Transformation (BWT) basiert. Die BWT eines Textes T ist eine Neuordnung seiner Buchstaben und ergibt TBWT. TBWT verfügt über zwei sehr nützliche Eigenschaften:

1. TBWT ist komprimierbar und
2. kann genutzt werden um nach dem Suffix Array Suchprinzip nach Pattern zu suchen.

Für eine effiziente Suche müssen allerdings noch zusätzliche Informationen gespeichert werden. Dies geschieht zum Beispiel in Form des FM-indexes der die Zusatzinformationen mit TBWT zur Verfügung stellt. Durch die Verwendung dieser beiden Konzepte waren Langmead at al. in der Lage einen sowohl schnellen als auch speichereffizienten Read Mapper zu entwerfen der heutzutage in der Bioinformatik breite Anwendung findet.

Konzept

In einem ersten Schritt wird das Referenzgenom mit Hilfe des FM-indexes indiziert. Dieser Schritt ist auch schon ausreichend, wenn Reads keine Fehler enthalten würden. Da es allerdings Variationen in den Genomen gibt und Sequenzierfehler auftreten können ist diese Annahme nicht haltbar. Stattdessen müssen die Fehlerquellen berücksichtig und in das Konzept aufgenommen werden.

Um diesen Problem begegnen zu können wurde in Bowtie ein Backtracking Schritt eingeführt. Wann immer ein bestimmtes Read nicht exakt gemapped werden kann, wird die Base mit der geringsten Qualität (also mit der höchsten Wahrscheinlichkeit einen Fehler darzustellen) ausgetauscht und die Suche für das verbleibende Suffix fortgeführt.

Diese Art der Such kann unter Umständen dazu führen, dass sehr viele Backtracking Schritte notwendig sind um ein einzelnes Read zu prozessieren. Aus diesem Grund indiziert Bowtie das Genome zusätzlich vom Ende her und teilt die Reads in zwei Hälften, die dann jeweils exakt gesucht werden.

Aufgaben

1. Einlesen der Reads und des Referenzgenoms.
2. Indizieren des Genoms vom Anfang zum Ende und vom Ende zum Anfang.
3. Exakte Suche der Reads.
4. Implementierung des Backtracking mit Hilfe von Iteratoren (es wird so lange exakt gesucht bis keine Treffer mehr gefunden werden und dann die letzte gefundene Base substituiert).
5. Halbieren der Such und Forward und Backward Suche kombinieren.

Referenzen

[1] Langmead, B., Trapnell, C., Pop, M. and Salzberg, S. T. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome, Genome Biology, Vol 10, No. 3, 2009

[2] P. Ferragina, G. Manzini (2000) Opportunistic data structures with applications, Proceedings of the 41st IEEE Symposium on Foundations of Computer Science