2.3 Algorithms
Using with the corollary 2 we get a simple algorithm to compute p = ℙ(En)
algorithm 1: direct p-value
x is a real column vector of size L - 1 and y a real column vector of size k
initialization x = (v1,...,vL-1)' and y = (v1,...,vk)'
main loop for i = 1...n - 2 do
    • x = R × x (sparse product)
    • y = y + (x1,...,xk)'
end return
and using the corollary 3 we get an even simpler algorithm to compute the q = 1 - p = ℙ()
algorithm 2: complementary p-value
x is a real column vector of size L - 1
initialization x = (1,...,1)'
main loop for i = 1...n - 1 do
    • x = R × x (sparse product)
end return
The more critical stage of both these algorithms is the sparse product of the matrix R by a column vector which can be efficiently done with ζ operations.
It is interesting to point out the fact that these algorithms do not require the stationarity of the underlying Markov chain. More surprisingly, it is also possible to relax the random sequence homogeneity assumption. Indeed, if our transition matrix ∏ depends on the position i in the sequence, we simply have to replace R in the algorithms with the corresponding Ri (which may use a significant amount of additional memory depending on its expression as a function of i).
For complementary p-value, we require to compute R1R2...Rn-1Rnx which is easily done recursively starting from the right. In the direct p-value case however, it seems more difficult since we need to compute x + R1x + R1R2x + ... + R1R2...Rn-1Rnx. Fortunately this sum can be rewritten as x + R1(x + R2{... [x + Rn-1(x + Rnx)]...}) which is again easy to compute recursively starting from the right.
The resulting complexities in the heterogeneous case are hence the same than in the homogeneous one (assuming that the number of non zero terms in Ri remains approximately constant). This remarkable property of the FMCI should be remembered especially in the biological field where most sequences are known to have complex heterogeneous structures which are often difficult to take into account.