Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am doing a project on data mining.

I have a very large string of size, say n and many small strings, l_1,l_2.. each of size at most m. I want to find the sequence of small strings such that their concatenation has the minimum alignment cost (costs can include insertion, deletion and substitution) with my large string of size n. I can use one string more than once and it is not mandatory to use all the strings. Note that m << n

My greedy implementation gives very bad results even for small strings. I can't find an efficient solution to this problem. Can anyone help?

It looks like dynamic programming might be able to help but I'm not sure.

share

migration rejected from stackoverflow.com May 13 at 21:49

This question came from our site for professional and enthusiast programmers. Votes, comments, and answers are locked due to the question being closed here, but it may be eligible for editing and reopening on the site where it originated.

closed as unclear what you're asking by Robert Harvey, MichaelT, GlenH7, gbjbaanb, Dynamic May 13 at 21:49

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

3  
Are you talking about algorithms such as Smith-Waterman? –  Oliver Charlesworth Dec 7 '11 at 20:16
    
Smith-Waterman algorithm can align two strings only. What I want is an optimal concatenation of small strings such that they align to the larger string with min cost –  Anna Dec 7 '11 at 20:31
    
When talking about alignment, do you allow for arbitrary costs to be associated with different mismatched characters, or is the cost always the same? For example, could substituting an A for a G cost more than substituting an A for a T? –  templatetypedef Dec 7 '11 at 21:35
    
Yes, I am looking to handle arbitrary cost models. –  Anna Dec 8 '11 at 21:04
    
You might want to do a Smith Waterman (or similar, probably something more quick and dirty like a FASTA) to get areas of good match for the l_1, l_2 etc. Then use that to guide the concatenation. For example, if l_1 only matches to areas near the start of the large string, and l_2 only near the end, there is no point in concatenating l_2 + l_1. –  user949300 Dec 9 '11 at 1:21

1 Answer 1

Suppose you've a target_sequence consisting of m symbols and you want to produce a sequence that is as similar to target_sequence as possible.

Moreover, you've a library consisting of k sequences, each of length at most n < k. We are looking for a dynamic programming algorithm which yields a concatenation of sequences from library with minimal alignment cost.

Therefore, let's introduce a gap_cast and a mismatch_cost(a,b) for any pair of symbols (a,b). Furthermore, I will denote the alignment cost of aligning target_sequence starting at the i-th symbol with the j-th sequence from library by alignment_cost(i,j), i.e.

alignment_cost = (int i, int j)
    {
        int k = 1,
            result = 0;

        for (i = i - 1; i + k <= m && k <= library[j].size(); ++k)
        {
            if (target_sequence[i + k] != library[j][k])
                result += mismatch_cost(target_sequence[i + k], library[j][k]);
        }

        if (k < library[j].size())
            result += (library[j].size() - k) * gap_cost;
        return result;
    };

Now we are ready to formulate our dynamic program:

vector<vector<int>> opt(m, vector<int>(k + 1));
for (int i = m; i >= 1; --i)
{
    opt[i][0] = gap_cost;
    if (i + 1 <= m)
        opt[i][0] += min_element(opt[i + 1].begin(), opt[i + 1].end());
    for (int j = 1; j <= k; ++j)
    {
        opt[i][j] = alignment_cost(i, j);
        if (i + library[j].size() <= m)
        {
            opt[i][j] += min_element(opt[i + library[j].size()].begin(),
                opt[i + library[j].size()].end());
        }
    }
}

In the code above opt[i][j] is the value of an optimal solution for aligning target_sequence starting from the i-th symbol with the j-th sequence from library. We can obtain the minimum alignment cost by calculating the minimum over each entry of the vector opt[i], i.e.

min_element(opt[1].begin(), opt[1].end())
share
    
Maybe the one who downvoted my answer could give me some kind of explanation. Cause I would like to receive some feedback on my approach, I've formulated this as a question on codereview.stackexchange: codereview.stackexchange.com/questions/49645/… –  0xbadf00d May 13 at 15:27
    
the part deleted in most recent edit is not an answer: "Maybe someone could give me some feedback on this approach." –  gnat May 13 at 16:08
    
@gnat - I need to disagree. Asking for some feedback of the quality or optimality of my approach doesn't downgrade my answer. However, as you see I've removed this passage from my answer. –  0xbadf00d May 13 at 22:11

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