Projekt Sequenzanalyse

• Gute Programmierkenntnisse
• Optional: Vorlesung Sequenzanalyse

Die Themen sollen - je nach Umfang - alleine oder in Gruppen mit bis zu drei Studierenden bearbeitet werden. Die Themen stammen aus dem Bereich der Sequenzanalyse. Eine vorläufige Themenliste besteht aus:

• Textindizierung per LZ77 und SLP
• Textindizierung per LZ77 und RL - BWT
• Implementierung und Vergleich von BWT - Konstruktionsalgorithmen

Selbstverständlich können auch eigene Themen vorgeschlagen werden.

Folien der Vorbesprechung

LZ-Index:

• LZ-Index Implementierung
• Sebastian Kreft, Gonzalo Navarro: On compressing and indexing repetitive sequences, Theoretical Computer Science, 483, S. 115-133, 2013
• Variante 1 (Grammatikbasiert):
  Travis Gagie , Pawel Gawrychowski , Juha Kärkkäinen , Yakov Nekrich: A faster grammar-based self-index, Proceedings of the 6th international conference on Language and Automata Theory and Applications, LATA '12, S. 240-251, 2012
• Variante 2 (BWT-supported):
  Djamal Belazzougui, Fabio Cunial, Travis Gagie, Nicola Prezza, Mathieu Raffinot: Composite Repetition-Aware Data Structures, Proceedings of the 26th annual conference on Combinatorial Pattern Matching, CPM '15, S. 26-39, 2015

BWT Konstruktion:

• BWT inplace:
  Maxime Crochemore, Roberto Grossi, Juha Kärkkäinen and Gad M. Landau: Computing the Burrows-Wheeler transform in place and in small space, Journal of Discrete Algorithms, 32, S. 44 - 52, 2015
• Dynamische Strukturen für BWT inplace von Nicola Prezza: DYNAMIC
• BWT durch Vorsortierung von Suffixen mit gleichem Anfangsbuchstaben:
  Markus J. Bauer, Anthony J. Cox, Giovanna Rosone: Lightweight algorithms for constructing and inverting the BWT of string collections, Theoretical Computer Science, 483, S. 134-148, 2013

Textindizierung ist ein wesentlicher Bestandteil der Sequenzanalyse, bei dem ein Text derart vorverarbeitet wird um anschließend effizient exakte Suche und Textextraktion innerhalb der konstruierten Strukturen betreiben zu können. Die verschiedenen Textindizierungsarten sollen zuerst implementiert, und anschließend anhand von Experimenten mit gängigen anderen Indizierungsarten (z.B. FM-Index, Enhanced Suffix Array, ...) bezüglich Konstruktionszeit, Speicherverbrauch und Queryzeit verglichen werden. Als Programmiersprache ist C++ vorgesehen.