Need help with algorithm (dynamic programming)

[Nineshadow]

You are given n sequences.

Example :

GGATATAAAAAC
GATAACCGCGCAGTGATGAGA
TGATGAGATGGGGATATAAAA
AGATAGATGATAACCGCGCAGT
ATGGGGATATAAAAACTTTTTT

You must compute the shortest sequence which contains all the given sequences as subsequences. For the given example, that would be :

AGATAGATGATAACCGCGCAGTGATGAGATGGGGATATAAAAACTTTTTT

I think this problem could be rewritten as a problem of finding the shortest hamiltonian path/cycle in a graph. I can't really figure out how to make the input data into a graph which makes sense in this context though.

Or if you guys have another idea , please share. I'm pretty sure it can be solved using DP without making it entirely into a graph problem.

[clegger]

This might point you in the right direction, at least for the overlapping part of the problem:

http://stackoverflow.com/questions/1285434/efficient-algorithm-for-string-concatenation-with-overlap

 

The part of the problem that deals with the order in which you attempt to find and apply overlaps (given that you're dealing with multiple sequences at once) is another big part of the problem.

[Nineshadow]

4 minutes ago, clegger said:

This might point you in the right direction, at least for the overlapping part of the problem:

http://stackoverflow.com/questions/1285434/efficient-algorithm-for-string-concatenation-with-overlap

 

The part of the problem that deals with the order in which you attempt to find and apply overlaps (given that you're dealing with multiple sequences at once) is another big part of the problem.

Backtrack with KMP could also work , but it's not fast enough.

[Nineshadow]

So after some documentation I've found out this is called the shortest common supersequence problem which can be derived from the longest common subsequence problem. For arbitrary many inputs , the problem is NP.