Engineering Algorithms for Personal Genome Pipelines

Abstract

Recent technical advances in high-throughput sequencing technologies and their commercial availability at low costs have paved the way for revolutionary opportunities in the life sciences. One milestone was reaching the $1000 genome, allowing to determine the genetic makeup of hundreds of human individuals within a week for less than $1000 each. This ongoing revolution of the life sciences creates new challenges for the software and algorithms that are processing this data. In my thesis, I consider a typical software pipeline for determining the genome of a human individual. For the preprocessing pipeline step, I describe a method for error correction and consider the comparison of such methods. For the read mapping step, I provide a formal definition of read mapping and I present a software package implementing a benchmark for read mapping, based on my formal definition. I then describe the implementation, parallelisation, and engineering of a fully sensitive read mapper and evaluate its performance. For the variant calling step, I present a method for the prediction of insertion breakpoints and the assembly of large insertions. Of course, such a pipeline is not limited to the processing of human data but it is also applicable to data from other mammals or organisms with smaller and less complex genomes. The presented work is available as an efficient open source C++ implementation, either as parts of the SeqAn library or as programs using SeqAn.

Die technischen Fortschritte der letzten Jahre im Bereich der Hochdurchsatzsequenzierung und die kommerzielle Verfügbarkeit dieser Technik haben den Weg für revolutionäre Möglichkeiten in den Lebenswissenschaften geebnet. Ein Meilenstein dabei war das Erreichen des sogenanten 1000 Dollar Genoms. Es ist heute möglich, das Erbgut von hunderten von Menschen in unter einer Woche für weniger als je 1000 Dollar auszulesen. Diese Revolution der Lebenswissenschaften stellt auch neue Herausforderungen an die Software und Algorithmen für die Verarbeitung dieser Daten. In meiner Arbeit betrachte ich eine typischen Pipeline um ein menschliches Genom zu dekodieren. Für den Vorverarbeitungsschritt beschreibe ich eine Methode zur Fehlerkorrektur und vergleiche verschiedene solcher Methoden. Für den Read Mapping Schritt entwickle ich zunächst eine for- male Definition von Read Mapping und stelle dann ein Softwarepaket vor, dass den Vergleich von Read Mappern, basierend auf der formalen Definition, erlaubt. Danach beschreibe ich die Imple- mentierung, Parallelisierung, und das Engineering eines vollsensitiven Read Mappers. Für den Schritt der Variantenanalyse präsentiere ich eine Methode für die Vorhersage von Bruchpunkten und eine Methode für das gezielte Assemblieren von langen Insertionen. Eine solche Pipeline kann selbstverständlich auch für genomische Daten von anderen Säugetie- ren oder Lebewesen mit kürzerem, weniger komplexen Genom einsetzt werden. Die vorgestellte Arbeit ist als effiziente, quelloffene C++ Implementierung verfügbar, zum Teil als Bestandteil der SeqAn Bibliothek und zum Teil als Programme auf der Grundlage von SeqAn.