**Probability computation using lazy evaluation ofthe DP matrix**. In this example we use the same PSSM

*M*, character distribution, and p-value threshold

*π *=

as in Figure 11. However, in each row of the PSSM the scores are sorted in descending order, and the rows are sorted with the most discriminant row coming first (see coloured PSSMs for this relationship). Observe that the

*LazyDistrib *algorithm evaluates the DP vectors non-recursively top-down. Cells computed in the actual step are marked red. In step

*d *= 0 the algorithm computes

*Q*_{2}(11) by evaluating paths through the PSSM contributing to

*Q*_{2}(ll), which is in this example only the high scoring path GGA. Intermediate results of

*Q*_{0}(4),

*Q*_{1}(7), and

*Q*_{2}(11) are collected in buffers

*Pbuf*_{0}(4),

*Pbuf*_{1}(7), and

*Pbuf*_{2}(11) first, and finally copied to the correponding cells in

*Q*. See (A) for the situation after step

*d *= 0 has been completed. In step

*d *= 1, see (B), the algorithm computes

*Q*_{2}(10), starting in row

*k *= 1 with the determination of

*Pbuf*_{1}(6) and

*Q*_{1}(6). That is,

*Q*_{1}(6) =

*Pbuf*_{1}(6) =

*Q*_{0}(4)·

*f*(

*A*) +

*Q*_{0}(4)·

*f*(

*C*) +

*Q*_{0}(4)·

*f*(

*T*) =

. Analogously

*Q*_{2}(10) and

*Pbuf*_{2}(10) are computed based on

*Q*_{1}(7) and

*Q*_{1}(6). Additionally

*Pbuf*_{2}(9) is filled for further reuse in subsequent steps

*d *+ 1,

*d *+ 2,.... We compute

*Pbuf*_{2}(9) =

*Q*_{1}(6)·

*f*(

*C*) =

. The algorithm can directly start in row

*k *= 1 with the computation of

*Q*_{1}(6) instead of

*Q*_{0}(3) since a score of 3 cannot be achieved by the first prefix PSSM

*M*_{0}. Only score 4 of

*M*_{0 }contributes to

*Q*_{2}(10), scores 2 and 1 do not. In step

*d *= 2, see (C), the algorithm computes

*Q*_{2}(9), starting in row

*k *= 0.

*Pbuf*_{2}(9) is computed reusing the partial sum calculated in previous steps, such that

*Pbuf*_{2}(9) =

+

*Q*_{1}(7)·

*f*(

*T*) +

*Pbuf*_{1}(5)·

*f*(

*A*) =

, and then copied to

*Q*_{2}(9).

*Pbuf*_{1}(4),

*Pbuf*_{2}(8), and

*Pbuf*_{2}(7) are filled based on

*Pbuf*_{0}(2),

*Q*_{1}(6),

*Pbuf*_{1}(5), and

*Q*_{1}(5) for further reuse. After step

*d *= 2 the rest of the computation can be skipped since the cumulated probability

*Q*_{2}(11) +

*Q*_{2}(10) +

*Q*_{2}(9) =

exceeds the given p-value

*π *=

and we obtain a score threshold of

*th *= 10 corresponding to

*π*.

## PubMed Commons