The complexity of the overlap method for sequencing biopolymers

The problem of trying to reconstruct the sequence of a biopolymer by using overlapping fragments obtained from cleaving agents is shown to be computationally intractable. This strongly suggests that any computer program for overlap sequencing, even though it may work well for a limited number of inputs, will not work sufficiently for all inputs. However, if the problem is restricted so that certain crucial fragments are known, called prime strings, a sequence can be found efficiently in all cases. Graph theory techniques for doing so can also be used to count the number of sequences consistent with the fragment data to determine whether a unique sequence has been obtained.