<p>The problem can be solved at least in $O(M \cdot T \log T)$ which is theoretically better, but may be slower than $O(M\cdot T\cdot L)$ in practice if $L$ is comparable to $\log T$.  </p>

<p>Let's show how to find a score of each $v_i$ independently in $O(T \log T)$. For any (possibly gapped) string $W = w_0 w_1 \ldots w_{n-1}$ define two polynomials $zeros_W(x)$ and $ones_W(x)$ as follows:</p>

<p>$$ zeros_W(x) = \sum_{i=0}^{n-1} [w_i = &#39;&#39;0&#39;&#39;]x^i$$
$$ ones_W(x) = \sum_{i=0}^{n-1} [w_i = &#39;&#39;1&#39;&#39;]x^i$$</p>

<p>where $[P]$ is <a href="http://en.wikipedia.org/wiki/Iverson_bracket" rel="nofollow">Iverson notation</a>. </p>

<p>For example, $zeros_{01...01}(x) = 1 + x^5$, $ones_{01...01}(x) = x + x^6$, $zeros_{0001100}(x) = 1+x+x^2+x^5+x^6$ and $ones_{0001100}(x) = x^3 + x^4$.</p>

<p>Then compute coefficients of the following polynomial $$c(x) = zeros_S(x) \cdot ones_{rev(v_i)}(x) + ones_{S}(x) \cdot zeros_{rev(v_i)}(x) = \sum_{j}c_j x^j$$ where $rev(W) = w_{n-1} \ldots w_1 w_0$ is just reversed $W$. It's easy to see that $c_{L-1+k}$ will be equals exactly to the difference between $s_k s_{k+1} \ldots s_{k+L-1}$ and $v_i$. For example, for $S=&#39;&#39;0100&#39;&#39;$ and $v_i = &#39;&#39;10&#39;&#39;$ $c(x)$ will be equal to $(1+x^2+x^3)\cdot x + x \cdot 1 = 2x + x^3 + x^4$ which gives us all interesting differences (2, 0, 1) so we can calculate score in linear time. Thus the problem is reduced to polynomial multiplication, which can be done in $O(T \log T)$ using <a href="http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods" rel="nofollow">FFT</a>.</p>

<p>The possible disadvantage of such approach is that FFT has essential constant hidden in its big-O, so using $O(T^{1.585})$ <a href="http://en.wikipedia.org/wiki/Karatsuba_algorithm" rel="nofollow">Karatsuba multiplication</a> or something similar may work better in practice for not very large $T$.</p>

CC BY-SA 3.0
2012-01-07T10:55:12.880Z
2012-01-07T12:07:50.530Z
2012-01-07T12:07:50.530Z
Dmytro Korduban
<p>Let us define: </p>

<ul>
<li><p>$U = \left\{ u_j \right\}, 1 \leq j \leq N = 2^{L}$, the set of all different binary sequences of length $L$.</p></li>
<li><p>$V = \left\{ v_i \right\}, 1 \leq i \leq M = \binom{L}{k}2^{k}$, the set of all different gapped binary sequences with $k$ known bits and $L-k$ gaps.</p></li>
</ul>

<p>We have a score function $f : V \rightarrow R$, that associates a real number $c_i$ to any of $v_i$'s; i.e. $c_i = f(v_i)$.</p>

<p>Given any pair of $u_j$ and $v_i$, we can count the number of mismatches, by counting the known bits of $v_i$ that are different in $u_j$.  For example given $L=7, k=4$: </p>

<p>$\text{diff}(\text{&quot;0001100&quot;}, \text{&quot;01...01&quot;}) = 2$,</p>

<p>because the second bit and the last bit are different (gaps can match to any value).</p>

<p>We have a weight associated to the number of mismatches. In general, the number of mismatches can be any number between $0$ and $k$. so we have $k+1$ such weights given by $\left \{ w[0],w[1],\ldots,w[k] \right \}$.</p>

<p>For a given sequence $S$ of $T$ bits, $S = s_0s_1 \ldots s_{T-1}$, we define the total score as the weighted sum of all the $c_i$'s for all the the contiguous $L$-bits subsequences of $S$ weighted by their distance: </p>

<p>$g(S)=\sum_{j=0}^{T-L}\sum_{i=1}^{M} c_i \times w[\text{diff}(v_i, s_js_{j+1} \ldots s_{j+L-1})]$.</p>

<p>the obvious algorithm is as follows: </p>

<p>g:=0;
for j:=0 to T-L
  for i:=0 to M
    g:=g+c[i]*calcDif(S,j,i) </p>

<p>where calcDif() takes $O(L)$ to count number of mismatches. so the overall time would be in the order of $T*M*L$.</p>

<p>What is a better approach to calculate the total score more efficiently? Typical values are: $L=20, k=10, T=2000$? </p>

CC BY-SA 3.0
2011-04-14T01:18:44.290Z
Ghandi: Any approaches you've tried? It may help us to understand the question.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-04-14T19:27:34.300Z
Does the score function $ c_i $ have any symmetries or special properties?  Because it looks like partitioning $V$ into strings of the same weight w.r.t. substrings of $ S $ may help if we know more about $ c_i $.
Jack
CC BY-SA 3.0
2011-04-14T23:15:37.313Z
$c_i$ is a real number. there is no special property about it. if we quantize it, however, we may bin similar $c_i$'s together.
mghandi
CC BY-SA 3.0
2011-04-16T22:30:54.240Z
@Jack: The weights W[0] .. W[k] are however strongly decaying, so for large m's it is almost equal to zero. Therefore an approximation algorithm that only uses few top w[m]'s would probably be useful in practice.
mghandi
CC BY-SA 3.0
2011-04-22T18:49:48.590Z
except that W[j] is used (k choose j)/$2^k$ of the time, which may be growing as a function of j as strongly as your W[j]'s are decaying.
Jack
<ds.algorithms><string-matching>
Fast algorithm for scoring a sequence
mghandi
# Fast algorithm for scoring a sequence

(Asked by: username_0 on 2011-04-13)

Let us define:

* $U = \left\{ u\_j \right\}, 1 \leq j \leq N = 2^{L}$, the set of all different binary sequences of length $L$.
* $V = \left\{ v\_i \right\}, 1 \leq i \leq M = \binom{L}{k}2^{k}$, the set of all different gapped binary sequences with $k$ known bits and $L-k$ gaps.

We have a score function $f : V \rightarrow R$, that associates a real number $c\_i$ to any of $v\_i$'s; i.e. $c\_i = f(v\_i)$.

Given any pair of $u\_j$ and $v\_i$, we can count the number of mismatches, by counting the known bits of $v\_i$ that are different in $u\_j$. For example given $L=7, k=4$:

$\text{diff}(\text{"0001100"}, \text{"01...01"}) = 2$,

because the second bit and the last bit are different (gaps can match to any value).

We have a weight associated to the number of mismatches. In general, the number of mismatches can be any number between $0$ and $k$. so we have $k+1$ such weights given by $\left \{ w[0],w[1],\ldots,w[k] \right \}$.

For a given sequence $S$ of $T$ bits, $S = s\_0s\_1 \ldots s\_{T-1}$, we define the total score as the weighted sum of all the $c\_i$'s for all the the contiguous $L$-bits subsequences of $S$ weighted by their distance:

$g(S)=\sum\_{j=0}^{T-L}\sum\_{i=1}^{M} c\_i \times w[\text{diff}(v\_i, s\_js\_{j+1} \ldots s\_{j+L-1})]$.

the obvious algorithm is as follows:

g:=0;
for j:=0 to T-L
for i:=0 to M
g:=g+c[i]\*calcDif(S,j,i)

where calcDif() takes $O(L)$ to count number of mismatches. so the overall time would be in the order of $T\*M\*L$.

What is a better approach to calculate the total score more efficiently? Typical values are: $L=20, k=10, T=2000$?

**Tags:** ds.algorithms, string-matching

> **Comments:**
> **username_1**: Ghandi: Any approaches you've tried? It may help us to understand the question.  
> **username_2**: Does the score function $ c_i $ have any symmetries or special properties?  Because it looks like partitioning $V$ into strings of the same weight w.r.t. substrings of $ S $ may help if we know more about $ c_i $.  
> **username_0**: $c_i$ is a real number. there is no special property about it. if we quantize it, however, we may bin similar $c_i$'s together.  
> **username_0**: @username_2: The weights W[0] .. W[k] are however strongly decaying, so for large m's it is almost equal to zero. Therefore an approximation algorithm that only uses few top w[m]'s would probably be useful in practice.  
> **username_2**: except that W[j] is used (k choose j)/$2^k$ of the time, which may be growing as a function of j as strongly as your W[j]'s are decaying.  

---

## 1 answers

### Answer by username_3 on 2012-01-07. Score: 3 | Accepted answer

The problem can be solved at least in $O(M \cdot T \log T)$ which is theoretically better, but may be slower than $O(M\cdot T\cdot L)$ in practice if $L$ is comparable to $\log T$.

Let's show how to find a score of each $v\_i$ independently in $O(T \log T)$. For any (possibly gapped) string $W = w\_0 w\_1 \ldots w\_{n-1}$ define two polynomials $zeros\_W(x)$ and $ones\_W(x)$ as follows:

$$ zeros\_W(x) = \sum\_{i=0}^{n-1} [w\_i = ''0'']x^i$$
$$ ones\_W(x) = \sum\_{i=0}^{n-1} [w\_i = ''1'']x^i$$

where $[P]$ is [Iverson notation](http://en.wikipedia.org/wiki/Iverson_bracket).

For example, $zeros\_{01...01}(x) = 1 + x^5$, $ones\_{01...01}(x) = x + x^6$, $zeros\_{0001100}(x) = 1+x+x^2+x^5+x^6$ and $ones\_{0001100}(x) = x^3 + x^4$.

Then compute coefficients of the following polynomial $$c(x) = zeros\_S(x) \cdot ones\_{rev(v\_i)}(x) + ones\_{S}(x) \cdot zeros\_{rev(v\_i)}(x) = \sum\_{j}c\_j x^j$$ where $rev(W) = w\_{n-1} \ldots w\_1 w\_0$ is just reversed $W$. It's easy to see that $c\_{L-1+k}$ will be equals exactly to the difference between $s\_k s\_{k+1} \ldots s\_{k+L-1}$ and $v\_i$. For example, for $S=''0100''$ and $v\_i = ''10''$ $c(x)$ will be equal to $(1+x^2+x^3)\cdot x + x \cdot 1 = 2x + x^3 + x^4$ which gives us all interesting differences (2, 0, 1) so we can calculate score in linear time. Thus the problem is reduced to polynomial multiplication, which can be done in $O(T \log T)$ using [FFT](http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods).

The possible disadvantage of such approach is that FFT has essential constant hidden in its big-O, so using $O(T^{1.585})$ [Karatsuba multiplication](http://en.wikipedia.org/wiki/Karatsuba_algorithm) or something similar may work better in practice for not very large $T$.


---

