Motivation

Substring-Indizes sind die fundamentalen Datenstrukturen zum effizienten Suchen von Sequenzen in großen Texten [1], zum Finden von maximalen Repeats oder in mehreren Texten gemeinsam vorkommenden Matches (MUMs) [2]. Die für diese Anwendungen kompakteste Datenstruktur stellt das Enhanced Suffix Array (ESA) [2] dar. Gegenwärtig benötigt der Aufbau des ESA für das Humangenom etwa 24h und für EST-Datenbanken noch um ein vielfaches länger.

Anforderungen

Ziel dieser Arbeit ist es, Methoden und Datenstrukturen für die Softwarebibliothek SeqAn [3] zu entwickeln, so dass inkrementelle Änderungen eines Textes konsistent auf einen zugehörigen Substring-Index wie das ESA übernommen werden. Der Text besteht entweder aus genau einer oder aus multiplen Sequenzen. Folgende Änderungen des Textes sollen dabei unterstützt werden:
 

• Einfügen einer Teilsequenz
• Entfernen einer Teilsequenz
• Hinzufügen einer Sequenz (falls Text aus multiplen Sequenzen besteht)
• Entfernen einer Sequenz (dito)

Das Enhanced Suffix Array besteht aus mehreren Tabellen, mindestens aus dem Suffix Array und der LCP-Tabelle [2]. Optional sind noch die Child-Tabelle oder die BWT-Tabelle vorhanden [2]. Zu Änderungen am Text sollen die nötigen Änderungen an den Tabellen bestimmt werden und entweder (i) direkt angewendet werden oder (ii) virtuell in zu den Tabellen gehörenden Datenstrukturen (Journals) gespeichert werden. Änderungen an den Tabellen sollen im letzteren Fall nur zu Änderungen im Journal, nicht aber zu tatsächlichen Änderungen in den Tabellen führen, so dass Änderungen oder Lesezugriffe auf Tabellen höchstens O(log n) benötigen.

Folgende Teilaufgaben sind zu bearbeiten:

• Algorithmus zur konsistenten Änderung von Suffix Array und LCP-Tabelle nach inkrementellen Textänderungen

• Entwickeln eines generischen Journal-Datentyps, zur Speicherung von Änderungen an einem/r Text/Tabelle. Ein Lesezugriff oder das Hinzufügen einer Änderungsoperation soll dabei in O(log n) erfolgen.

• Nach gewisser Zeit (abh. von der Größe des Journals) ist es sinnvoll, alle gespeicherten Änderungen eines Journals auf die zug. Tabelle zu übernehmen und das Journal zu leeren. Ein effizienter Algorithmus soll hierfür entwickelt und implementiert werden.

• Algorithmus zur konsistenten Änderung der Child-Tabelle

• Laufzeitmessungen der konsistenten Änderung des Index, der Substring-Suche und der Tiefensuche nach inkrementellen Textänderungen. Dabei sollen die Laufzeiten der direkten Anwendung mit dem Journal verglichen werden.

Ein dem Journal-Datentyp ähnlicher Datentyp ist das Rope, dieser ist allerdings nicht mit einem/r Text/Tabelle assoziiert, sondern speichert die einzelnen Zeichen in den Blättern eines Binärbaums mit ab.

 

Literatur

[1] M. I. Abouelhoda, E. Ohlebusch, S. Kurtz, Optimal exact string matching based on suffix arrays. (2002)

[2] M. I. Abouelhoda, S. Kurtz, E. Ohlebusch, The enhanced suffix array and its applications to genome analysis. (2002)

[3] SeqAn - The C++ Sequence Library, www.seqan.de