Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given some string fragments, I would like to find the shortest possible single string ("output string") that contains all the fragments. Fragments can overlap each other in the output string.

Example:

For the string fragments:

BCDA
AGF
ABC

The following output string contains all fragments, and was made by naive appending:

BCDAAGFABC

However this output string is better (shorter), as it employs overlaps:

ABCDAGF
^
ABC
 ^
 BCDA
    ^ 
    AGF

I'm looking for algorithms for this problem. It's not absolutely important to find the strictly shortest output string, but the shorter the better. I'm looking for an algorithm better than the obvious naive one that would try appending all permutations of the input fragments and removing overlaps (which would appear to be NP-Complete).

I've started work on a solution and it's proving quite interesting; I'd like to see what other people might come up with. I'll add my work-in-progress to this question in a while.

share|improve this question
3  
The problem seems to be NP-complete. If so, you won't be able to find a polynomial algorithm for determining the shortest string at all, but there might be polynomial algorithms which give approximate (not the shortest possible) solutions. – superM Sep 25 '12 at 10:59
    
Thanks superM, I had an idea that this may be the case! – occulus Sep 25 '12 at 10:59
3  
This blog post regarding NP-Complete is nice: codinghorror.com/blog/2008/11/… – occulus Sep 25 '12 at 11:04
    
The blog's really nice, I read it all the time ))) – superM Sep 25 '12 at 11:06
    
@superM this is similar enough to traveling salesman (each string a city and cost between cities = some number-overlap) – ratchet freak Sep 25 '12 at 11:34
up vote 13 down vote accepted

What you're asking about is the Shortest Common Superstring problem, for which there is no algorithm that works for all cases. But it is a common problem (in compression and DNA sequencing) and several approximation algorithms are well-known.

"Greedy" algorithms are generally accepted to be the most effective (as in, they have the least-bad worst-case).

Have a read of the paper Approximation Algorithms for the Shortest Common Superstring Problem by Jonathan Turner for much more information.

share|improve this answer
1  
Thanks, great answer! Edited title of question thus. – occulus Sep 25 '12 at 12:41
1  
    
Hmm, note that the first link in my comment just above address supersequences and not superstrings! A supersequence does not seem to require all characters in a sequence be contiguous. – occulus Sep 25 '12 at 13:24
    
Your link is dead. – Majid Rahimi Dec 15 '14 at 17:12
    
@majidgeek: Thanks for letting me know. – pdr Dec 16 '14 at 3:11

I did mine using greedy. Basically for each string in the set, I compare it with the rest of the strings in the set, and find the most duplicated one, and merge the two.

And keeps doing it until only one string left in the set.

You can look at there for some other solutions people made.

https://www.reddit.com/r/dailyprogrammer/comments/46km7n/20160219_challenge_254_hard_dna_shotgun_sequencing/

share|improve this answer
1  
1  
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review – Snowman Jun 3 at 15:14

protected by gnat Jun 3 at 3:14

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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