Lukas Hübner, Alexandros Stamatakis

Dominik Siebelt

Bei der Analyse von DNA-Sequenzierungsdaten, um krankheitsverursachende Mutationen zu finden, evolutionäre Beziehungen zwischen Arten zu verstehen und Varianten zu identifizieren, werden DNA-Reads mit einem Referenzgenom verglichen. Ein Referenzgenom ist ein repräsentatives Beispiel für ein Set von Genen einer Spezies. Das Sortieren dieser aligned DNA-Reads nach ihrer Position innerhalb der Referenzsequenz ist ein entscheidender Schritt in vielen dieser nachgelagerten Analysen. SAMtools sort, ein weit verbreitetes Tool, führt das externe Speichersortieren von aligned DNA-Reads durch, die im BAM-Format (Binary Alignment Map) gespeichert sind. Dieses Format ermöglicht die komprimierte Speicherung von Ausrichtungsdaten. SAMtools sort bietet das umfassendste Set an Funktionen und weist nachweislich schnellere Ausführungszeiten auf als andere Open-Source-Alternativen. In dieser Arbeit analysieren wir SAMtools sort zum Sortieren von BAM-Dateien und schlagen Methoden zur Reduzierung der Laufzeit vor. Wir unterteilen die Analyse in drei Teile: Verwaltung von Zwischendateien, Komprimierung und Eingabe/Ausgabe (IO). Für die Verwaltung von Zwischendateien stellen wir fest, dass die maximale Anzahl Zwischendateien, die SAMtools sort gleichzeitig öffnen kann, geringer ist als die maximale Anzahl offener Dateien, die vom Betriebssystem zugelassen wird. Dies führt zu einer unnötig hohen Anzahl von Merges von Zwischendateien zu größeren Zwischendateien, was zusätzlichen Aufwand bedeutet, da SAMtools sort zusätzliche Schreib- und Komprimierungsvorgänge durchführt. Um dies zu überwinden, schlagen wir ein dynamisches Limit für die Anzahl von Zwischendateien vor, das sich an das soft-limit des Betriebssystems für offene Dateien anpasst. Für die Komprimierung testen wir sieben verschiedene kompatible Libraries und eine Reihe von Komprimierungsstufen (Level), um Möglichkeiten zu identifizieren, die schnellere Komprimierung bieten und zu einer bis zu fünfmal schnelleren Ausführung von SAMtools sort im Single-Thread- Betrieb führen. Für die Ein- und Ausgabe zeigen wir, dass ein minimales Komprimierungsniveau IO-Overhead vermeidet und dadurch die Laufzeit von SAMtools sort im Vergleich zu unkomprimiertem Out- put reduziert. Wir zeigen jedoch auch, dass unkomprimierter Output im Pipelining von SAMtools-Befehlen verwendet werden kann, um die Laufzeit aufeinanderfolgender SAMtools-Befehle zu reduzieren. Unsere vorgeschlagenen Änderungen an SAMtools sort und dem Benutzerverhalten haben das Potenzial, Speedups von bis zu 6 zu erreichen. Dies stellt einen wichtigen Beitrag im Bereich der Bioinformatik dar, angesichts der weit verbreiteten Verwendung von SAMtools sort, die durch über 5.000 Zitate und über 5,1 Millionen Downloads über Bioconda belegt wird.