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,[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- Jonathan S. Turner, Approximation algorithms for the shortest common superstring problem, Information and Computation, Volume 83, Issue 1, 1989, Pages 1-20, ISSN 0890-5401, https://doi.org/10.1016/0890-5401(89)90044-8.
Einzelnachweise
Bearbeiten- ↑ 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).
- ↑ https://www.geeksforgeeks.org/shortest-superstring-problem/