Aktuelle Informationen finden Sie im Moodle Kurs: https://moodle.uni-ulm.de/course/view.php?id=30182

Problemstellung

Die Aufgabe die in diesem Projekt bearbeitet werden soll ist verwandt zum Pan-Genom-Read-Mapping.

Ein 'Pan-Genom' ist eine DNA-Sequenz die geläufige genetische Variationen enthält (Größenordnung 10⁶ - 10⁹ bp).
Ein 'Read'  ist es kurzes Fragment (Substring) der Sequenz (Größenordnung 100 - 1.000 bp).
Das Problem ist, die Stelle zu finden an der dieser Read im der Sequenz steht.
(Das Mapping-Problem erhält man, wenn der Read Fehler enthalten kann und daher die Stelle gesucht wird an der der Read am besten passt.)

Das das Pan-Genome sehr groß ist und es üblicherweise sehr viele Reads gibt, kommen String-Matching-Algorithmen, die den Read in irgendeiner Weiße am Pan-Genome entlang schieben nicht in Frage. Lösungen des Problems verarbeiten das Pan-Genome in einer Art und Weise vor, sodass die Anfragen schneller erledigt werden können. Die schnellsten Lösungen für Read-Mapping-Problem auf Genomen ohne Variationen benutzen Techniken verwandt zu Suffixbäumen. Diese sind allerdings nicht direkt auf Pan-Genome übertragbar. Eine andere Lösungsweg, die leichter übertragbar ist, verwendet einen  k-mer-Index.

Ein k-mer ist ein Fragment der Sequenz mir der Länge k. (Größenordnung  k = 10 - 20 bp).
Ein k-mer-Index speichert alle Positionen eines k-mers im Pan-Genome.
Mit dem Wissen über die Positionen der k-mere lassen sich die Positionen der Reads bestimmen.

Im Projekt soll der komplette Ablauf von Vorverarbeitung des Pan-Genom bis Finden von Reads implementiert werden. Es gibt verschiedene Möglichkeiten die Verwendung der k-mer-Indexe zu optimieren. Verschiedene Teilnehmer können verschiedene Möglichkeiten austesten. Die Implementierungen sollen an großen Daten getestet und ausgewertet werden.