Succinct Data Stuctures and Compressed Suffix Arrays

Die Vorbesprechung findet am Donnerstag, den 17.04, um 13:00 Uhr in O27/531 statt.

Wichtige Probleme aus der Sequenzanalyse, wie etwa das Exact Pattern Matching Problem (gegeben ein (langer) Text T und ein (kurzer) Text P: gesucht sind alle Position p, an der P in T vorkommt.) lassen sich mit einer Datenstruktur, dem sog. Suffix Array effizient lösen. Diese Datenstruktur wird einmal vorberechnet und dann zum effizienten Lösen der Probleme genutzt.

Suffix Arrays haben aber den Nachteil relativ viel (im Vergleich zum Text selbst) Speicher zu verbrauchen. So benötigt der sehr lange Text des menschlichen Genoms ca. 715 MByte (Text der Länge n= 4*109 über dem Alphabet {A,C,G,T}). Das dazugehörige Suffix Array aber  ca. 4.5 GByte.

Compressed Suffix Arrays bieten dieselbe Funktionalität wie Suffix Arrays; jedoch mit theoretisch langsamerer Zugriffszeit und weniger Speicherverbrauch. Da Compressed Suffix Arrays aber oft noch in den Hauptspeicher eines Computers passen, ist die Zugriffszeit  praktisch dennoch schneller als bei Suffix Arrays, die nicht mehr in den Speicher passen.

Succinct Data Structures sind Repräsentationen von (elementaren) Datenstrukturen (etwa binäre Bäume, Bitvektoren,...) deren Speicherbedarf nahe an der informationstheoretischen Schranke liegt und dennoch eine effiziente Ausführung  bestimmter Operationen zulässt. Beispiel: Ein Bitvektor B, der mit Zufallsbits initialisiert ist, wird mit n+o(n) Bits repräsentiert und wir können dadurch in konstanter Zeit bestimmen, an welche Position die i-te Null in B vorkommt. Diese Succinct Data Structures bilden die Grundlage für die Implementierung von Compressed Suffix Arrays.

Zu Beginn der Veranstaltung werden die theoretischen Grundlagen einmal ausführlich besprochen. Hauptziel ist aber die Implementierung von Succinct Data Structures und Compressed Suffix Arrays.

Bitte melden Sie sich bei Interesse am Praktikum bei Simon Gog.

http://pizzachili.dcc.uchile.cl/index.html