Analyse und Optimierung eines Algorithmus zur Bestimmung aller Wiederholungen mit einer Lücke beschränkter Größe

Beschreibung

Bei der Untersuchung von genetischen Sequenzen ist es von Interesse mehrfach auftretende Strukturen zu erkennen. Eine solche Struktur sind die sogenannten maximalen α-gapped repeats und Palindrome. Dabei handelt es sich um zwei Teilwörter eines Texts, wobei das zweite Teilwort eine Wiederholung des ersten ist, bzw. beide Teilwörter hintereinandergeschrieben ein Palindrom sind. Zusätzlich gilt, dass die Größe der Lücke zwischen den beiden durch eine Konstante α beschränkt wird.

Ziel dieser Bachelor-Arbeit ist es einen Algorithmus zu implementieren und zu optimieren, der alle maximalen α-gapped repeats bzw. α-gapped palindromes eines Texts im worst case theoretisch in optimaler Zeit finden kann. Dazu wird die Laufzeit in der Praxis ermittelt und diese mit einem naiven Ansatz verglichen.

Typ

Bachelorarbeit

Bearbeiter

Daniel Kurowski (2017).

Betreuer

 
Last modified: 2017-04-28 12:48 (external edit)
DokuWikiRSS-Feed