Design, analysis, development and experimental validation of algorithms for high throughput sequencing mass data using the SeqAn library for biological sequence analysis

• Applicant: Professor Dr. Knut Reinert
• Subject Area: Bioinformatics and Theoretical Biology
• Term: from 2010 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 192954395

• Final Report Year: 2015

Final Report Abstract

Während der letzten Dekade konnte ein super-exponentielles Wachstum von Sequenzierungsdaten durch die rapide Entwicklung moderner Sequenzierungsverfahren beobachtet werden. Zum Zeitpunkt des Schreibens dieses Berichtes hatte eine einzige Sequenziermaschinen bereits einen Durchsatz von 30 Milliarden Nukleotiden pro Tag. Ziel dieses Projektes war es entsprechend der massenhaften Generierung von Sequenzierdaten neuartige Datenstrukturen und Algorithmen zu entwickeln, die in komprimierter Form repräsentiert werden können. Wir haben die Implementierung des Journaled Strings verbessert um noch mehr Speicher einzusparen und um die Datenstruktur schneller zu iterieren. Im Anschluss haben wir ein entsprechendes Dateiformat entworfen und eine Applikation implementiert um die Daten anzuzeigen, zu modifizieren oder darzustellen. In der zweiten Phase des Projekts entwickelten wir eine neuartige Datenstruktur um die Daten in vertikalem Modus zu repräsentieren. Dies bedeutet, dass die Unterschiede zwischen einer Donorsequenz und einer Referenzsequenz nicht pro Sequenz gespeichert werden, sondern dass die Differenz für alle Sequenzen gleichzeitig sichtbar ist. Mit dieser Repräsentierung konnten wir einen generischen Algorithmus entwickeln, der die Sequenzen daten-parallel traversiert. Das heißt redundante Bereiche werden nur einmal betrachtet. Wir haben die Datenstruktur und den Algorithmus auf mehr als 2000 Sequenzen vom Chromosom 1 getestet und mit der naiven Suchstrategie verglichen und ausgewertet.

Publications

• Unifying Alignment Algorithms Using Generic Meta-Programming. Intelligent Systems for Molecular Biology (ISMB) (ISCB 2013), July 21-23, Berlin
  R. Rahn, D. Weese, M. Holtgrewe and K. Reinert
  
• Journaled string tree - a scalable data structure for analyzing thousands of similar genomes on your laptop. Bioinformatics (2014) 30 (24): 3499- 3505
  R. Rahn, D. Weese and K. Reinert