Shortest Common Superstring

2023-05-26T07:57:15Z

80.155.12.250:

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,<ref>{{cite journal
|title=The shortest common supersequence problem over binary alphabet is NP-complete
|author=Kari-Jouko Räihä, Esko Ukkonen
|journal=Theoretical Computer Science
|volume=16
|number=2
|date=1981
|pages=187–198
|doi=10.1016/0304-3975(81)90075-x
|doi-access=free
|language=en
}}</ref> 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.<ref>https://www.geeksforgeeks.org/shortest-superstring-problem/</ref>

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

== Literatur ==

* 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 ==
<references />

[[Kategorie:Informatik]]
[[Kategorie:Bioinformatik]]
[[Kategorie:Kombinatorik]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Shortest Common Superstring