wissen.leben | WWU Münster 


Home   > Theses   > Thesis details

Diploma thesis: Entwicklung und Implementierung eines Algorithmus zur Lokalisierung von Haarnadel-bedingten Tandem-Wiederholungen


Status finished on 2010-02-28
Student Stöver, Ben
Supervisors Müller, Kai
Quandt, Dietmar
Accepting institution Nees Instutite for Biodiversity of Plants
University Bonn
Meckenheimer Allee 170
53115 Bonn
Germany
Home institution Evolution and Biodiversity of Plants
Institute for Evolution and Biodiversity
WWU Münster
Hüfferstraße 1
48149 Münster
Germany
URL http://bioinfweb.info/r/DiplomarbeitHIR

Abstract

Ben C. Stöver (2010): Entwicklung und Implementierung eines Algorithmus zur Lokalisierung Haarnadel-bedingter Tandem-Wiederholungen. Externe Diplomarbeit am Institut für Evolution und Biodiversität, Westfälische Wilhelms-Universität Münster.

Eine Haarnadel-bedingte Tandem-Wiederholung ("hairpin initiated repeat", HIR) besteht aus direkt aufeinander folgenden Wiederholungen eines Sequenzmotivs, die durch Einfaltung einer Haarnadelstruktur während der DNA-Replikation entstehen. In dieser Arbeit wird ein entsprechender Mechanismus postuliert, der im Unterscheid zu slipped-strand mispairing (SSM) (Levison, Gutman, 1987), nicht nur die Vergrößerung einer bereits bestehende Tandem-Wiederholung, sondern auch das Entstehen neuer Tandem-Wiederholungen erklären kann. Dieser könnte entsprechend auch als Startmechanismus für SSM dienen.

Um das Vorkommen und die Häufigkeit von HIRs (bestehend aus einer Tandem-Wiederholung und einer oder mehrerer mit dieser an den Ende überlappender Haarnadelstrukturen) in verschiedenen Genomen feststellen zu können, ist es notwendig, diese automatisiert zu lokalisieren. In der vorliegenden Arbeit wurden dazu formale Definitionen der beteiligten Strukturen eingeführt und darauf basierend ein Algorithmus zur effizienten Suche nach diesen entwickelt.

Grundlage ist ein Verfahren zur Lokalisation von Tandem-Wiederholungen (Sokol et al., 2007), welches auf der Levenshtein-Distanz (Levenshtein, 1966) basiert. Dabei wird die zu untersuchende Sequenz rekursiv in Hälften geteilt, und auf jeder Rekursionsebene durch eine von der Mitte ausgehende Alignierung der Teilsequenz mit sich selbst, in unterschiedlichen Verschiebungen, auf das Vorhandensein von Tandem-Wiederholungen hin untersucht. Die Verschiebungen entsprechen dabei jeweils den Periodenlängen einer möglichen Tandem-Wiederholung. Es handelt sich bei diesem Verfahren um einen Teile-und-herrsche-Algorithmus, worauf seine Effizienz beruht. Gefunden werden sog. k-edit-Wiederholungen, welche durch eine absolute Fehlerzahl (Fehlpaarungen, Insertionen oder Deletionen zwischen den einzelnen Perioden) definiert werden. Das Verfahren wurde in dieser Arbeit so erweitert, dass stattdessen Wiederholungen sehr unterschiedlicher Länge, die durch eine relative Fehlerrate charakterisiert sind, gefunden werden können.

Darüber hinaus wurde eine Abwandlung des Algorithmus entwickelt, die in der Lage ist, invertierte Wiederholungen (Haarnadelstrukturen) zu lokalisieren, indem an verschiedenen Positionen versucht wird eine Sequenz mit ihren invertierten Gegenstück ("reverse complement") zu alignieren. Eine solche Suche ist aufwendiger als die nach Tandem-Wiederholungen, da zwischen den beiden Stämmen eine Schleife unterschiedlicher Länge liegen kann. Die Gesamtsequenz wird hier ebenfalls (in diesem Fall iterativ) in Hälften zerlegt, wobei dann aber in jeder Iteration jede Sequenz mit sich selbst und allen anderen aligniert werden muss. Auch die Suche nach Haarnadelstrukturen ist in der Lage mit einer relativen Fehlerrate zu arbeiten. Abschließend können aus den lokalisierten Tandem- und invertierten Wiederholungen Kandidaten für mögliche HIRs bestimmt werden.

Die Implementierung der HIR-Suche erfolgte in der Software HIR-Finder, welche in Java geschrieben ist und Sequenzdaten im FASTA- oder Nexus-Format einlesen kann. Entsprechende Funde in diesen Sequenzen können gleichzeitig in einer Sequenzansicht und einer Tabelle dargestellt und in einem eigens entwickelten XML-Format gespeichert und wieder geladen werden. Weiterhin können Tabellen mit den Häufigkeiten der verschiedenen Wiederholungen exportiert werden. Die momentane Version ist in der Lage, einen großen Teil, aber noch nicht alle Wiederholungsmuster innerhalb einer Sequenz zu lokalisieren. Dies ist kein prinzipielles Problem der entwickelten Algorithmen, sondern auf das noch nicht abgeschlossene Testen der Implementierung zurückzuführen, da dies innerhalb der vorgegebenen Bearbeitungszeit nicht vollständig möglich war. Bei der Implementierung wurde konsequent auf die Verwendung aktueller Entwurfsmuster geachtet, wodurch eine spätere Erweiterbarkeit des HIR-Finders um zusätzliche Funktionen, sowie die Wartbarkeit des Codes sichergestellt sind.

Die Leistungsfähigkeit der aktuellen Version wurde anhand von Beispielanalysen simulierter Sequenzdaten und Komplettgenomen demonstriert. Bei der Analyse von simulierten Sequenzdaten zeigt sich, dass die Häufigkeit von Tandem-Wiederholungen exponentiell mit der Periodenlänge abnimmt und bereits rein stochastisch Kandidaten für HIRs in allen Sequenzen enthalten sind. Im Chloroplastengenom von Marchantia polymorpha sind überproportional viele HIR-Kandidaten im Vergleich zu den insgesamt gefundenen Tandem-Wiederholungen enthalten, was den Schluss nahelegt, dass dort ein biologischer Mechanismus vorhanden ist der zu deren Entstehung beiträgt. (Das untersuchte Kern- und Mitochondriengenom zeigen keinen entsprechenden HIR-Anteil.) Da die betreffenden Wiederholungsmotive fast ausschließlich nur zwei vollständige Perioden besitzen, kommt slipped-strand mispairing nicht in Frage. Es könnte sich stattdessen um den postulierten HIR-Mechanismus handeln.

Publications

Conference abstract (poster)

Stöver BC, Quandt D, Müller KF: Complex mutations and multiple sequence alignment - Example: Hairpin-initiated repeats (HIRs). 2nd annual Münster Graduate School of Evolution Symposium; Münster, Germany; 2012 (Details)

Related Software

  • HIR Finder ()

About | © 2011 WWU Münster
Institute for Evolution ind Biodiversity
Hüfferstraße 1 · 48149 Münster