Shortest Common Superstring
# Shortest Common Superstring

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, 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.

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.

