Shortest Common Superstring

from Wikipedia, the free encyclopedia

A set S is given that contains a total of n strings S = {s1, s2,…, sn}. The Shortest Common Superstring (SCS) now represents the string that contains all elements from S as substrings and has the shortest length.

An important area of ​​application of the SCS can be found in genome analysis : the overall sequence can be determined from a large number of individual, sequenced DNA fragments using the SCS.