Shortest Common Superstring
aus Wikipedia, der freien Enzyklopädie
Es ist eine Menge S gegeben, die insgesamt n Strings enthält S={s1, s2, …, sn}. Der Shortest Common Superstring (SCS) stellt nun denjenigen String dar, der sowohl alle Elemente aus S als Substrings enthält als auch die kürzeste Länge besitzt.
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.
