(Shortest Common Superstring: Input: A set S = {s1, . . . , sn} of strings over an alphabet Σ. Feasible solutions: Each superstring w of S, i.e., each string w that contains all strings $s_i$ ∈ S as substrings. )

I just finished implementing cycle cover superstring algorithm, but step 4 and 5 just doesn't make sense to me. first algorithm

Why is it important that we compute a minimum cycle cover for the representative vertices? They will be replaced by the concatenation of all prefixes in the cycle followed by the representative itself, and then these strings will not be merged, they will be concatenated together to achieve a superstring. Why is maximizing overlaps a goal, if we don't merge, only concatenate? I found a different algorithm for Cycle Cover Superstring, and here step 4 and step 5 are left out! second algorithm

To me, the second algorithm makes perfect sense so I decided to implement that one, but could anybody tell me why would be the first one better? It seems to give the same output but it's slower. I'm afraid I misunderstood something. The first algorithm can be found in Algorithmic Aspects of Bioinformatics.

The second algorithm can be found in Approximation Algorithms for the Shortest Superstring Problem by Martin Paluszewski (first link if you google it)

EDIT: I tested the two algorithms with multiple examples on paper and on computer using my implementation. The outcame wasn't always the same, but the length of the superstrings was always the same, which means that both algorithms are good, only that the second one is faster. I'm more concerned about that my interpretation of the first algorithm isn't correct - once it states that the representatives are merged in order, and then that they have to be concatenated. I posted this question hoping that somebody would notice that I somehow misinterpreted the first algorithm.

  • 1
    $\begingroup$ Have you tried working through an example? Have you tried proving your alternative algorithm to be correct? Have you tried to determine the worst-case running time algorithm of your algorithm, and of the algorithm you don't understand, and comparing those two running times? If you have, can you edit the question to show us what you've come up with? If you haven't, I'd suggest trying that as your next step. $\endgroup$ – D.W. Apr 29 '17 at 0:24
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$ – Raphael Apr 29 '17 at 10:44

Your Answer

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

Browse other questions tagged or ask your own question.