PISB SeqAn - Projekt Normalised Edit Distance

Hintergrund: Normalisierte Edit-Distanz

Die Edit-Distanz ist ein Standarddistanzmaß für Sequenzalignments, Mappings etc. Sie ist ein absolutes Maß, d.h. sie gibt die absolute Anzahl an "Fehlern" zwischen zwei Sequenzen an. Alignments unterschiedlicher Länge sind damit schwer zu vergleichen: Ein Alignment der Länge 6 mit 3 Fehlern wäre danach genauso gut wie ein Alignment der Länge 10 mit 3 Fehlern. Vielmehr noch ist es damit nicht direkt möglich, ein Alignment mit einer vorgegebenen maximalen Fehler rate zu bestimmen. Arslan und Egecioglu [1] beschrieben als erste Algorithmen zur dynamischen Berechnung der normalisierten Edit-Distanz, die genau dies ermöglicht. Sie zeigten auch, dass eine post-normalisation bereits berechneter Alignments nicht generell zum gleichen gültigen Ergebnis wie der Dynamic Programming Ansatz führt.

Aufgaben

Ziel dieses Projektes ist es, die normalisierte Edit-Distanz mit Hilfe von Komponenenten aus der C++-Bibliothek SeqAn zu implementieren. Im Grunde handelt es sich um eine Adaptierung bekannter Alignmentalgorithmen wie Needleman-Wunsch oder SmithWaterman, die bereits in SeqAn implementiert sind, sodass ein normalisierter Score zurückgegeben wird. Der Code sollte folgende Funktionalitäten haben:

1. Einlesen von Sequenzen, die aligniert werden sollen
2. Dynamische Berechnung aller Alignments bzw. der normalisierten Edit-Distanzen (DP Matrix)
3. Optional: Berechnung des Tracebacks
4. Ausgabe des besten Scores (optional: und des besten Alignments)

Zusätzlich sollt ihr euch eigene Beispiele überlegen, wo normalisierte und post-normalisierte Edit-Distanz unterschiedlich sind, und damit euer Programm testen.

Referenzen

[1] Abdullah N. Arslan and Ömer Egecioglu, Efficient Algorithms For Normalized Edit Distance, 1993