Lukas Hübner, Alexandros Stamatakis

Johannes Hengstler

Die Disziplin der Populationsgenetik untersucht die treibenden Kräfte der Evolution mit Bäumen. Entlang eines Genoms beschreibt jeder solche Baum die lokale Abstammung einer kleinen genomischen Region. Zusammen ergeben diese Bäume eine Baumsequenz, die den Stammbaum einer Population an jeder Site des Genoms enthält. Allerdings ist der Rechenauf- wand für die Inferenz von Baumsequenzen für ganze Genome teuer, wenn viele Haplotypen auf einmal in den Stammbaum eingefügt werden sollen. Das state-of-the-art Programm, um eine solche Baumsequenz zu berechnen, ist tsinfer, welches Stammbäume für menschliche Chromosomen mit 5000 Eingabesequenzen in wenigen Stunden berechnet. Das Programm kann die Berechnung parallelisieren, aber wir zeigen eine Struktur in den Eingabedaten auf, welche den Grad der Parallelisierung begrenzt. Wir schlagen eine alternative Methode der Parallelisierung vor, die das Skalierungsverhalten bei hohen Threadzahlen unabhängig von dieser Struktur verbessert. Darüber hinaus optimieren wir den Inferenzalgorithmus, indem wir die Cache-Effizienz einiger Datenstrukturen und die Anzahl an Operationen pro Iteration verringern.

Wir implementieren unseren veränderten Algorithmus und vergleichen diesen mit tsinfer. Unsere Implementation ist auf Daten des 1000 Genomes Projects konsequent um einen Faktor von 1.9 bis 2.4 schneller. Je nach Wahl der Parameter skaliert unsere Parallelisierungsmethode außerdem zwischen 32 und 96 Prozessorkernen besser als tsinfer, und baut so den Geschwin- digkeitsvorteil vor allem bei hohen Kernzahlen aus. In den Phasen der Inferenz, in denen unsere Methode der Parallelisierung nicht anwendbar ist, ist unser Algorithmus trotzdem um einen Faktor 2.2 schneller. Unser Beitrag verringert die Berechnungszeit und verbessert die Parallelisierung der Inferenz von Baumsequenzen. Diese Verbesserungen erlauben trotz des enormen Wachstums von Genomdatensätzen die Inferenz größerer Eingaben in angemessenen Zeiträume