A number of technological advancements in high-throughput genome sequencing have led to the generation of exabyte-scale sequencing data worldwide in recent years. These developments have facilitated large-scale resequencing projects like the 1000 Genomes Project, which aim to catalog the genetic diversity of organisms and specific populations. In the context of medical research, incorporating population data, is of particular interest. However, existing applications are often optimised for analysing a few sequences, and the methods used cannot be easily transferred to these vast datasets without exceeding system resources or producing results within a suitable time frame. Simultaneously, the execution model of processors has evolved from sequential to highly parallel process execution, thanks to the addition of processor cores, vector processing units, and advances in superscalar processor designs. This ongoing development in high-performance computing requires applications and algorithms to scale with the growing levels of parallelism. However, highly optimised algorithms are often embedded within applications, making them practically inaccessible to the scientific community. In this dissertation, we first investigate a generic approach to parallelise and vectorise pairwise sequence alignments using a dynamically scalable concurrency model. We explore various techniques and code-level optimisations to effectively utilise the available parallelisms on modern high-performance CPUs. The results demonstrate that the dynamically accelerated pairwise sequence alignment scales proportionally with the number of cores and provides speed-ups of up to a factor of 2500 compared to the sequential reference implementation on modern hardware. Second, we propose a general solution for data-compressed acceleration of pattern matching algorithms by compressing a large collection of related DNA sequences and providing a set of composable algorithms to refine and optimise the applicable operations. Our research on data-compressed acceleration shows hundred-fold speed-ups for online searching over a pangenome comprising over 5000 reference sequences compared to the naive approach of individually searching all sequences. These speed-ups are achieved while utilising only a fraction of the main memory. Moreover, we implemented these features in dedicated modules of the open-source software library SeqAn (https://www.seqan.de/), making them accessible and adoptable by the entire research community. While doing so, we strived for a user-friendly API design so that these methods can be easily customised and extended, making them applicable to a wide range of applications in the domain of computational sequence analysis.
Eine Reihe von technologischen Fortschritten bei der Hochdurchsatz-Sequenzierung von Genomen hat in den letzten Jahren weltweit zur Erzeugung von Sequenzierungsdaten im Exabyte-Bereich geführt. Diese Entwicklungen haben groß angelegte Resequenzierungsprojekte, wie das 1000 Genomes Project, ermöglicht, welche darauf abzielen die genetische Vielfalt ganzer Populationen von unterschiedlichen Organismen zu katalogisieren. Bestehende Anwendungen sind jedoch häufig für die Analyse einiger weniger Sequenzen optimiert. Häufig lassen sich die verwendeten Methoden nicht ohne weiteres auf solche riesigen Datenmengen übertragen, ohne dabei die zur Verfügung stehenden Rechenressourcen zu übersteigen oder in angemessener Zeit entsprechende Ergebnisse zu produzieren. Gleichzeitig führten kontinuierliche Verbesserungen in der Prozessorherstellung zu einem fundamentalen Wechsel im Programmiermodell von einer sequentiellen hin zu einer hochparallelen Ausführung von Prozessen. Diese fortlaufende Entwicklung im Bereich des Hochleistungsrechnens erfordert, dass Anwendungen und Algorithmen mit der zunehmenden Parallelität skalieren. Optimierte Algorithmen sind jedoch häufig in konkrete Anwendungen eingebettet, so dass sie für die wissenschaftliche Gemeinschaft praktisch unzugänglich sind. In dieser Dissertation untersuchen wir zunächst einen generischen Ansatz zur Parallelisierung und Vektorisierung paarweiser Sequenzalignments unter Verwendung eines skalierbaren Nebenläufigkeitsmodells. Dabei betrachten wir verschiedene Optimierungsansätze, um die verfügbaren Parallelitäten moderner Hochleistungs-CPUs effektiv zu nutzen. Unsere Ergebnisse zeigen, dass wir im Vergleich zur sequenziellen Ausführung auf modernen CPUs Geschwindigkeitssteigerungen von bis zu einem Faktor von 2500 erreichen. Im zweiten Teil betrachten wir Methoden zur datenkomprimierten Beschleunigung von Pattern-Matching-Algorithmen. Dabei komprimieren wir eine große Sammlung ähnlicher DNA-Sequenzen anhand einer Referenzsequenz und entwickeln eine Reihe von kombinierbaren Algorithmen, mit deren Hilfe existierende Suchalgorithmen auf dem datenkomprimierten Format angewendet werden können. Durch die Verarbeitung in komprimierter Form, konnten wir, verglichen mit dem naiven Ansatz, hundertfache Geschwindigkeitssteigerungen bei der Online-Suche in einem Pangenom mit über 5000 Referenzsequenzen erzielen. Darüber hinaus haben wir die entwickelten Funktionen und Operationen in konkreten Modulen der Open-Source-Softwarebibliothek SeqAn (https://www.seqan.de/) implementiert, so dass sie für die gesamte Forschungsgemeinschaft zugänglich sind. Dabei haben wir uns um ein benutzerfreundliches API-Design bemüht, so dass unsere Methoden leicht adaptiert und erweitert werden können und für ein breites Spektrum von Anwendungen im Bereich der computergestützten Sequenzanalyse nutzbar sind.
