Differences
This shows you the differences between two versions of the page.
— |
fischer:abschlussarbeiten:gappedrepeat [2017-04-28 12:48] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ===== 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 ==== | ||
+ | [[staff:fischer|Johannes Fischer]] und [[staff:koeppl|Dominik Köppl]] | ||