KIP-Veröffentlichungen

Das Studium der DNA und ihrer Intra- als auch Interspeziesevolution bleibt auch heute immer noch eine Herausforderung. Algorithmen, die Alignments zwischen DNA-sequenzen erstellen, sind sehr erfolgreich und ihre weitverbreiteter Gebrauch hat sie zu elementaren Werkzeugen in der Genetik und Bioinformatiks gemacht. Das immer größer werdende Wissen über genetische Rekombination und großräumige DNA-Interaktionen zeigen nun Schwächen in den Standardalignmentalgorithmen auf. Um diese Schwächen zu überkommen wurden neue alignment-free Algorithmen entwickelt, über die allerdings bisher wenig geforscht wurde. In der vorliegenden Arbeit werden Untersuchungen über Effizienz und Verläßlichkeit von alignment-free Methoden (Kmer) basierend auf der Häufigkeit von k-Worten  präsentiert. Kmer wurde dabei in Python 3.6.0 und C++11 implementiert. In Kmer werden dabei Sequenzkorrelation für verschiedene Werte von k durchgeführt, in dem unterschiedliche Korrelationsfunktion (Pearson, Spearman, Kendall) auf k-Wort-Spektren angewandt werden. Zur Untersuchung evolutionärer Prozesse, wurde Kmer sowohl auf reale Sequenzen als auch auf zufällig generierte Sequenzen, die zum Teil auch Mutationen unterworfen wurden, angewandt. Es konnte gezeigt werden, dass dieses Verfahren in der Lage ist in den ausgewählten Sequenzen Muster für k = 3, 5 ,7 aufzufinden, ebensowie spezifische Sequenzen in Genomen wiederzufinden. Die besten Resultate wurden mit Kendall erreicht mit relativen Abweichungen zwischen 1.3% und 3.5%. Es wurde ein Versuch unternommen um eine Beziehung zwischen Korrelationswert und Mutationsrate aufzustehen, wobei ein exponentieller Zusammenhang bei allen Korrelationen gefunden wurde, am besten mit Kendall. Eine Subroutine des Algorithmus (sKmer) wurde auf eine einzelne zufällig generierte, mit sich selbst nach Mutationen korrelierte Sequenz angewandt, um ähnliche und mutierte Regionen zu identifizieren. Dieselben zwei Sequenzen wurden mit dem Smith-Waterman Algorithmus untersucht und die identifizierte Regionen wurden zwischen den beiden Methoden verglichen, wobei eine Übereinstimmung bis auf wenige Basenpaare gefunden wurde. Die Ergebnisse legen nahe, dass Kmer eine verlässliche Methode ist und mit ausreichender Statistik zu neuem Wissen über DNA-Mechanismen führen kann. Darüberhinaus ist die Subroutine sKmer ein geeignetes Verfahren um alignment und alignment-free Methoden miteinander zu vergleichen und zu korrelieren.

The study of DNA and its evolution in and among species has been and is still a challenging task. Algorithms applying alignments between DNA sequences to study their evolutionary relations have been especially successful and their ubiquitous use made them basic tools in genetics and bioinformatics. But the increasing knowledge on genetic recombination and long-range DNA interactions made standard alignment algorithms insufficient. To overcome this, new alignment-free algorithms have been developed, yet research on them is relatively small. In this work studies on the efficiency and reliability of an alignment-free method (Kmer) based on k-words' frequency were conducted. Kmer has been implemented in Python 3.6.0 and C++11. It correlates sequences through their k-words distributions, using different correlation functions (Pearson, Spearman, Kendall) and values of k. To study evolutionary processes, Kmer was applied on both real sequences and random-generated and mutated sequences.  It could be shown that this method is able to capture patterns inside the chosen sequences for k= 3, 5, 7 and detect specific sequences inside the genomes. The best results were obtained with Kendall with a relative change between 1.3% and 3.5%. An attempt to get a relation between correlation values and applied mutations was performed, finding an exponential behaviour in all correlations, the best in Kendall. A subroutine of the algorithm (sKmer) was applied on a single random-generated sequence correlated with itself after mutations were applied to identify similar regions and mutations. The same two sequences were used with the Smith-Watermam algorithm and the identified regions between the two methods compared, showing agreement with a variation of few base pairs. The results suggest that Kmer is a reliable method and, with appropriate statistics, could lead to new knowledge on the DNA mechanisms. Moreover its subroutine sKmer is a suitable method to find a translation between alignment and alignment-free methods and eventually integrate them in one system.