BScDataStructureSV

SNP efficient Journal Strings

Einleitung

In den letzten 10 Jahren hat sich die Technologie zur Sequenzierung der DNS von Organismen kolossal verbessert. Dabei konnten die Kosten für die Sequenzierung eines einzelnen Genoms dramatisch gesenkt werden, so dass das Speichern der Daten teurer ist als das Generieren der Selbigen. Um den Speicheraufwand zu reduzieren werden typischerweise Kompressionsalgorithmen angewendet, um die Daten in kompakter Form persistent aufzubewahren. Um die Daten zu analysieren müssen sie vorher wieder dekomprimiert werden.

Für biologische Sequenzen hat sich die Methode der referenzbasierten Komprimierung als besonders effizient erwiesen und zeichnet sich durch einen hohe Kompressionsrate aus [1-3]. Die zugrunde liegende Idee der referenzbasierten Komprimierung lässt sich aus der Beobachtung ableiten, dass zwei Organismen derselben Art oder Population sich nur geringfügig in Ihrer DNS unterscheiden [4].

Ziel der referenzbasierten Komprimierung ist es, möglichst lange Segmente der Zielsequenz in der Referenzsequenz wieder zu finden und anschließend nur Zeiger zu diesen Segmenten innerhalb der Referenzsequenz zu speichern. In SeqAn wurde die Datenstruktur "Journal String" [5, 6] implementiert, die das Prinzip der referenzierten Komprimierung ausnutzt und für eine Zielsequenz die Segmente in Form eines binären Suchbaumes abspeichert. Dadurch ist es möglich direkt auf den Daten in Ihrer komprimierten Form zu arbeiten, ohne die Sequenzen vorher zu dekomprimieren. In der aktuellen Version der Journal Strings werden SNPs als eine einzelne Insertion von einer Base gefolgt von einer Löschung einer einzelnen Base abgespeichert. Eine detaillierte Analyse des Chr 22 aus dem 1000 Genom Projekt [4] ergab allerdings, dass die Mehrheit der Varianten SNPs sind, so dass eine effizientere Datenstruktur speziell für die SNPs den Speicherbedarf weiter senken könnte.

Aufgabenstellung

Ziel der Arbeit wird es sein die Journal Strings so zu erweitern, dass diese SNPs effizienter speichern können. Nach entsprechender Einarbeitungszeit wird die erweiterte Datenstruktur entworfen und die nötigen Anpassungen geplant. Nach eingehender Überprüfung des Entwurfes wird anschließend die Erweiterung in SeqAn implementiert. Dabei sollen alle Funktionen der aktuellen Implementierung erhalten bleiben und Random-Access Zugriff weiterhin möglich sein. Anschließend vergleicht der Student Speicherbedarf und Zugriffszeiten für große Datensätze zwischen der alten und der neuen Datenstruktur und wertet diese detailliert aus.

Erwarteter Aufwand: Einarbeitung und Entwurf der erweiterten Datenstruktur (2 Wochen) Implementierung der erweiterten Datenstruktur und adaptieren der Interfaces (3 Wochen) Testen und Evaluieren der Datenstruktur sowie Niederschreiben der Ergebnisse (3 Wochen)

Referenzen

[1] Christley, S., Lu, Y., Li, C., & Xie, X. (2009). Human genomes as email attachments. Bioinformatics (Oxford, England), 25(2), 274–5. doi:10.1093/bioinformatics/btn582

[2] Deorowicz, S., & Grabowski, S. (2011). Robust relative compression of genomes with random access. Bioinformatics (Oxford, England), 27(21), 2979–86. doi:10.1093/bioinformatics/btr505

[3] Wandelt, S., & Leser, U. (2012). Adaptive efficient compression of genomes. Algorithms for molecular biology : AMB, 7(1), 30. doi:10.1186/1748-7188-7-30

[4] McVean et al. (2012). An integrated map of genetic variation from 1,092 human genomes, Nature 491, 56–65 doi:10.1038/nature11632

[5] Pyl, P. T. (2009). Incremental Index Structures, Master's Thesis

[6] Rahn R. (2011). Genomes per E-Mail: Efficient Compression of Biological Sequences. Master's Thesis

Comments