Lesson 4

The previous three problems are examples of the shortest common superstring problem (or simply the superstring problem). As you might have guessed, making the superstring shorter is possible because some pairs of strings have overlaps: formally, \(\operatorname{overlap}(s,t)\) is the longest suffix of \(s\) that is also a prefix of \(t\). It is not difficult to show that the optimal superstring corresponds to a permutation of the original strings that maximizes the total length of adjacent overlaps.

In general, this problem is hard: no one knows how to solve it in polynomial time. However, there is an important special case where the problem can be solved very quickly: it is the case when all substrings of length \(k\) of an unknown string are given. Below, using a toy example, we will learn how to solve this special case. The ideas we demonstrate form the basis of modern genomic assemblers.