Projekt Sequenzanalyse

Voraussetzungen

  • Gute Programmierkenntnisse
  • Optional: Vorlesung Sequenzanalyse

Themen

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.

Materialien

Folien der Vorbesprechung

LZ-Index:

BWT Konstruktion:

Ziele

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.

Termin

Vorbesprechung am 14.4.2016 um 14.00 Uhr in O27/531.

Themenauswahl bis spätestens 30.4.2016.

Weitere Informationen

LSF-Eintrag