Forschungsseminar Sommersemester 2005
"Neue Entwicklungen in der Bioinformatik und Informationsintegration"
David Weese
Implementierung des Skew-Algorithmus
Der Skew-Algorithmus wurde 2003 von Juha Kärkkäinen und Peter Sanders veröffentlicht und war der erste direkte Suffix-Array Algorithmus mit einer linearen Zeitkomplexität. Das Ziel dieser Studienarbeit war, den Algorithmus in SEQAN zu implementieren und auf Praktikabilität zu untersuchen.
SEQAN ist eine in der Arbeitsgruppe für Bioinformatik der Freien Universität zu Berlin entwickelte Software-Bibliothek, die Algorithmen und Datenstrukturen zur Analyse von Genom- und Proteinsequenzen bereit stellt.
In der Arbeit wird erstmals die Erweiterung des Skew-Algorithmus um Difference Covers vorgestellt, durch die Laufzeit und Speicherbedarf reduziert werden konnten. Zum Ende des Vortrages werden Laufzeitmessungen der Skew-Implementierungen im Vergleich mit anderen Suffix-Array Algorithmen vorgestellt.