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|improve this question
3  
Are you talking about algorithms such as Smith-Waterman? –  Oli 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
add comment

migrated from stackoverflow.com Dec 12 '11 at 22:10

This question came from our site for professional and enthusiast programmers.

2 Answers

There are two things to consider when you talk about bad performance. One is the algorithm you implemented (and I can't help you with that, but Wikipedia should be good for that). The other is how you implemented your algorithm. When you concatenate strings in Java, you might be tempted to use the '+' operator on strings, like so:

s = s1 + s2

That, however, is very slow, especially when you have to concatenate many strings. In this case it is much faster to use a StringBuffer. The code is more verbose, but still much faster and would look like this:

StringBuffer b = new StringBuffer(s1);
b.append(s2);
s = b.toString();

For concatenating only two Strings, this is overkill. For more than two, you will already gain something from doing things this way.

share|improve this answer
    
By bad result, I meant that it is far from the optimal that I could have obtained. –  Anna Dec 12 '11 at 18:20
    
StringBuilder is better than StringBuffer unless two threads are going to access the stirng buffer which is almost never the case –  tgkprog Apr 11 '13 at 13:15
add comment

It does look like dynamic programming can handle this. Suppose that you have calculated for i = 1..N in the large string the cost of the best possible alignment of the first i characters of the large string. At position N + 1 consider all possible small strings and work out the cost of aligning the last k characters up to position N + 1 of the large string with the small string plus the cost of aligning characters 1..N+1-k with arbitrary small strings as previously recorded. Pick the smallest cost, over possible small strings and values of k, as the best solution for 1..N+1. I think that if you start off with small values of k and work up to large values, you will find that values of k above some bound cannot be best cost solutions, because you can predict deletion costs produced by large values of k.

share|improve this answer
    
What is your base case of the DP recurrence? How would you define the best alignment of the first 1 characters if all of the strings have length at least 50, for example? –  templatetypedef Dec 7 '11 at 21:22
    
Cases like these will be alignments of e.g. a 1-character string which is the first character of the long sequence, against a 0-character string which is the concatenation of 0 small strings. The best alignment for this will have the cost of a single deletion (or is it a single insertion - I'm not sure which way round these things are defined). –  mcdowella Dec 8 '11 at 5:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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