Complemented palindromes

Zusammenfassung

Implementierung und Vergleich drei verschiedener Ansätze zum Finden von maximalen, komplementären Palindromen einer signifikanten Länge mit Hilfe der in SeqAn vorhandenen Suffixtree- bzw. Suffixarraystruktur.

Expose

Den ersten beiden Ansätzen liegt ein von Dan Gusfield [1] beschriebener Algorithmus zu Grunde, dabei wird das Suffix ab jeder Position i im String S die "longest common extension" mit dem Suffix ab der Position j = n-i (n = |S|) im revers-komplementären String Ŝ gesucht. Ist die Länge l der lce größer k/2, gibt es ein signifikantes komplementäres Palindorm ab der Position i-l.

Um die lce bestimmen zu können werden zwei verschiedene Methoden implementiert, die alle auf der Bildung eines ESA (enhanced suffix array) aus S und Ŝ basieren:

1. Die lce zwischen zwei Positionen i und j in S und Ŝ ist dann das Minimum aller Einträge in der LCP-Tabelle zwischen den Einträgen für das Suffix ab i in S und das Suffix ab j in Ŝ.

2. Es wird ein Top-Down-Iterator verwendet um von der Wurzel aus durch den Suffixbaum zu laufen bis das Suffix an der Position i in S und das Suffix an der Position j in Ŝ in verschiedenen Unterbäumen liegen. Um effizient zu bestimmen in welchem Unterbaum die Suffixe liegen wird die Eigenschaft verwendet, dass alle Suffixe eines Unterbaums im Suffixarray konsekutiv hintereinander liegen.

Der dritte Ansatz basiert auf dem von Stoye und Gusfield [2] entwickelten Verfahren zum Finden von tandemrepeats: Für jeden Knoten v des Baumes wird eine "leaflist" erstellt, die alle Suffixe enthält, die im Unterbaum unterhalb des Knotens liegen. Dann wird für jeden Eintrag dieser leaflist überprüft, ob sich sein "Partner" in der leaflist befindet. Als Patner eines Suffixes i wird dabei das Suffix j = |S|-i bezeichnet. Um die Effizienz dieser Suche zu verbessern, werden die Einträge der größten leaflist eines Kinderknotens des Knoten v nicht gesucht und so das Finden von Paaren in beide Richtungen verhindert.

[1] D. Gusfield, Algorithms on strings, trees, and sequences. (1997), Kaptiel 9, Seiten 196-199

[2] J. Stoye und D. Gusfield, "Simple and Flexible Detection of Contiguous Repeats Using Suffix Tree" (1998)

Wochenberichte

Comments