PSMB_Seqan_2016_p3

Hintergrund

Der erste Schritt ein einer Pipeline zur Analyse von Genomvarianten ist das Read Mapping. Dabei soll für jeden NGS Read eigentlich die Position bestimmt werden, von der das sequenzierte Modul stammt. Durch Repeats und Sequenzierfehler ist dies jedoch im Allgemeinen nicht möglich, daher beschränkt man sich auf die Suche von einer (oder mehreren) "gut passenden" Positionen.

Oft legt man ein Distanzmaß zu Grunde, etwa Hamming oder Edit Distanz und sucht nach einem oder mehreren besten Positionen in der Referenzsequenz für diesen Read. Sucht man nach einem besten Match, so spricht man von "best mappern", sucht man alle beste Matches, so spricht man von "all mappern". Viele moderne Read Mapper sind "best mapper" und basieren oft auf Textindizes. Moderne all-mapper basieren oft auf String-Filtern.

Aufgaben

Im Rahmen dieses Projektes soll ein einfacher Read Mapper implementiert werden.

Mindestanforderung:

• Eingabe:
  • Eine kleine App zum Bauen eines Indexes (SA, ESA, FM, qGram, …)
  • Einlesen von FASTA & FASTQ mit single-end reads.
  • Einlesen des vorgebauten Indexes für die Referenzsquenz.
  • Einlesen einer Fehlerrate, sowie eine Distanzfunktion zum Berechnen der Hamming oder Edit Distanz.
• Ausführung:
  • Finden einer besten Position für jedes Read gegeben der Distanzfunktion.
  • Ausgabe der gefundenen Hits in SAM-Format.

Um die Position eines Reads in der Referenzsequenz effizient zu finden müssen mögliche Treffer gefiltert werden. Hier bietet sich das Pigeonhole Lemma an. Dabei wird der Read in kleine Seeds aufgeteilt, so dass mindestens ein Seed ohne Fehler lokalisiert werden kann. Um mögliche Treffer schnell zu finden muss die Referenzsequenz mit einer geeigneten Datanstruktur (FM-Index, Suffix Array oder q-gram Index) indiziert werden. Anschließend muss verifiziert werden, ob der vollständige Read auch tatsächlich matched. Dazu wird ein semi-globales Alignment in dem Band des entsprechenden Fensters berechnet.

Die Ausgabe des Programms soll der beste Match für jeden Read sein (Referenzsequence/Chromosom, Startposition, (Endposition,) Zahl der Fehler, Alignment, z.B. als CIGAR). Hierfür bietet sich zum Schreiben auf die Festplatte zum Beispiel das SAM Format an.

Zusatz:

• Das Filtern möglicher Hits soll mit OpenMP parallelisiert werden.
• Das semi-globale Alignment soll durch Myers' bitvector Algorithmus ersetzt werden.
• Laufzeit sowie Qualität der Ergebnisse sollen mit bestehenden Tools wie BWA und RazerS 3 verglichen werden.

References

• Flicek, Paul and Birney, Ewan. "Sense from sequence reads: methods for alignment and assembly". Nature Methods 6, 6 - 12. (2009).
• Myers, G. A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM (JACM), 85721, 1–11. (1999).
• Holtgrewe, Manuel, et al. "A novel and well-defined benchmarking method for second generation read mapping." BMC bioinformatics 12.1 (2011): 210.
• http://samtools.sourceforge.net/SAM1.pdf

Expose (von Gruppe)

Fortschrittsbericht (von Gruppe)