Generate paths of fixed length across a weighted matrix (defined in $\mathbb{R}$) whose weights' sum falls into given interval

Question

PSSM or PWM (Positional Weighted Matrix) is a common thing in biological science, used often to observe the distribution of letters inside a group of strings of the same length. It's composed by log-odds of observing a letter inside a given positions, so the value of each cell in the matrix could be either a positive or negative float. Follows an example of a PWM.

	A	C	D	E	F	G	H	I	K	L
0	0.426379	-2.96691	-1.137176	-1.859917	1.523913	-0.404392	-1.913876	0.330149	0.065161	0.570567
1	-1.104135	-2.96691	-1.400210	-1.859917	-2.012140	-2.519869	-2.498838	0.165090	-2.567107	2.644822
2	-0.186597	-2.96691	1.322256	-0.637524	0.753395	1.270208	-1.176910	-0.486986	-1.429604	0.093245
3	-0.750498	-2.96691	1.005782	0.777513	-1.164143	0.180571	0.588625	-1.178864	1.177054	-0.449897
4	-0.186597	-1.96691	-0.634675	-0.171861	0.189494	-0.712514	-0.176910	1.003339	-0.496718	0.175707
5	-0.573621	-2.96691	-1.722138	0.255561	0.250895	-2.519869	1.086124	0.290621	-0.982145	0.253710
6	0.369796	-1.96691	-2.137176	0.584868	-0.012140	-0.934906	0.086124	-0.124416	0.783390	-0.055618
7	-0.229666	-2.96691	-3.137176	-2.222487	-0.427177	-3.104831	-1.913876	0.478248	-2.304073	1.476102

This makes possible to assign a score to a string, which would be the sum of the positional weights. For example:

string: DDFGKKLA
score: -3,3616

What I was trying to achieve is the following: given a desiderable interval (defined by a score ± tolerance), I want to obtain all the possible sequences of length l (with l == num_rows) whose score falls inside the interval.
At a first sight it looks like a knapsack problem, despite that weights are defined inside $\mathbb{R}$ and I'm not finding a single, optimal solution.

I've got no formal CS background, so I got a bit lost when looking for similar algorithms on literature. Any idea or suggestion are very well accepted.

Answer 1

You're right. It is a sort of 0-1 knapsack problem. It is NP-complete in general. So you will need to settle for approximate solutions or heuristics or algorithms that only work for short strings or make other compromises.

You probably don't want to find all such solutions, as there could be exponentially many. Perhaps you want to find one of them.

If you only care about strings of length 8, then this can be solved fast enough in practice, using a meet-in-the-middle algorithm. Specifically, enumerate all $26^4$ possibilities for the first half of the string (there are about 457,000 possibilities), and for each, compute its score. Sort them by score; call that sorted list $L$. Now, enumerate all $26^4$ possibilities for the second half of the string. For each such possibility, compute its score, check what range of scores for the first half would make the whole string acceptable, and use binary search in $L$ to check whether there is any possibility for the first half of the string whose score falls into that acceptable range. This will be efficient enough for strings of length 8, but in general its running time is exponential in the length of the string, so it will be completely infeasible for strings of length 20 (say).

Another approach is to use dynamic programming to check whether there exists any solutions and, if one exists, to find one. One thing that makes your problem more challenging is that the entries in the matrix are real numbers. So, multiply them all by a large constant $C$, and then round to the nearest integer, so that they are all integers. (You'll need to multiply the acceptable range too.) I suggest you pick $C$ to be something like $100/\text{tolerance}$. Now, the goal is to check whether there is a string whose total score falls into the acceptable range. This can solved using dynamic programming. Define $A[i,t]$ to be true if there exists a string of length $i$ whose total score is $t$ (using the integer entries for the matrix). Note that $A[i,t]$ is true iff $A[i-1,t-s]$ is true for some $s$ that appears in the matrix for position $i$. Therefore, you can fill in the entries of $A$ in increasing order of $i$ and increasing order of $t$. Finally, by checking the value of $A[n,t]$ for each $t$ in the acceptable range, where $n$ is the desired length of the string, we can check whether there is any solution whose total score is acceptable, when using the integer scores. You can also extend the dynamic programming algorithm to find such a solution if one exists. This is a pretty good approximation to your original problem.