Das "Shortest Common Superstring"-Problem (SCS) ist ein kombinatorisches Optimierungsproblem, das darin besteht, die kürzeste mögliche Zeichenkette zu finden, die jede Zeichenkette in einer gegebenen Menge als Teilzeichenkette enthält. Das SCS-Problem ist NP-vollständig,[1] daher sind Approximationsalgorithmen von Interesse.

Beispiel: Für die Teilzeichenketten ["AB", "AC", "BA", "BC", "CA", "CB"] lautet ein möglicher SCS "ABACBCA".

Ein bekannter Approximationsalgorithmus ist der Greedy-Algorithmus, der wiederholt zwei Zeichenketten mit maximaler Überlappung zusammenfügt, bis eine einzige Zeichenkette übrig bleibt.[2]

Ein wichtiges Anwendungsgebiet des SCS findet sich bei der Genomanalyse: Aus einer großen Anzahl einzelner sequenzierter DNA-Bruchstücke lässt sich die Gesamtsequenz mittels des SCS ermitteln.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Kari-Jouko Räihä, Esko Ukkonen: The shortest common supersequence problem over binary alphabet is NP-complete. In: Theoretical Computer Science. 16. Jahrgang, Nr. 2, 1981, S. 187–198, doi:10.1016/0304-3975(81)90075-x (englisch).
  2. https://www.geeksforgeeks.org/shortest-superstring-problem/