3
$\begingroup$

I have a set of strings that are slices of a single, longer string. It is not guaranteed, however, that any two strings from this set must overlap: only that all of them together overlap. I want to reconstruct the original longer string.

For example, suppose the longer string is LGHFDJGHSJGHDFKSJBSFSHJKADGHS. The slices might be FKSJBSFS, JKADGHS, LGHFDJGHS, SFSHJKA and GHSJGHDFK. I need an algorithm to reconstruct the original LGHFDJGHSJGHDFKSJBSFSHJKADGHS.

I understand that this algorithm may be somewhat probabilistic: given any two strings, the probability that they overlap by pure chance is $\frac{2}{n}$ where $n$ is the size of the alphabet used. I want to find the "best" overlapping longer string.

So far I've asked around and I've been told to look into suffix trees and de Bruijn graphs. I have done so but I can't see how I can apply them to solve this problem. Any help would be appreciated.

$\endgroup$
2
$\begingroup$

This is the DNA sequence assembly problem, an algorithms problem that has been well studied in the literature. You can apparently find entire courses on the subject. In general, the problem is NP-hard. However, there are many algorithms that seem to work well in practice; greedy assembly is one very simple approach, but there are many others.

$\endgroup$
  • $\begingroup$ Hmm, does this mean that it would be suboptimal for me to write my own implementation of the algorithm? $\endgroup$ – Bluefire Jul 3 '18 at 16:26
  • $\begingroup$ @Bluefire, given that it is a complex subject that has received a lot of study, most likely! But suboptimal might well be good enough in your particular situation; or it might not. In general if you have enough redundancy in your short strings, almost any algorithm is fine; it's when you have less redundancy that the algorithm becomes more critical. $\endgroup$ – D.W. Jul 3 '18 at 16:30
  • $\begingroup$ That makes sense. I can assume that my inputs won't be that lengthy and there will be a fair amount of redundancy, so I guess there is no need for over-optimisation and a greedy algorithm will do. $\endgroup$ – Bluefire Jul 3 '18 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.