4.4 Algorithms
Using the proposition 6 it is possible to get an algorithm computing our pattern statistic for an under-represented pattern observed Nobs times:
algorithm 4under: exact statistics for under-represented pattern
x0,..., and y0,..., are 2 × (Nobs + 1) real column vectors of size L
initialization for j = 0...Nobs do xj = (1,...,1)'
main loop for i = 1...(n - 1) do
    • for j = 0...Nobs do yj = xj
    • x0 = P × y0
    • for j = 1...Nobs do xj = P × yj + Q × yj-1
end •
    • return log10(q)
If we consider now an over-represented pattern we get
algorithm 4over: exact statistics for over-represented pattern
x1,...,, y1,..., and z are 2Nobs + 1 real column vectors of size L
initialization z = (0,...,0)', x1 = ΣQ and for j = 2...Nobs do xj = (0,...,0)'
main loop for i = 1...(n - 2) do
    • for j = 1...Nobs do yj = xj
    • x1 = P × y1
    • for j = 2...Nobs do xj = P × yj + Q × yj-1
    • z = z +
end •
    • return -log10(p)
As we have O(k × L) non zero terms in P + Q, the complexity of both of these algorithms is O(k × L + Nobs × L) in memory and O(k × L × n × Nobs) in time.
To compute p-values out of floating point range (ex: smaller than 10-300 with C double), it is necessary to use log computations in the algorithms (not detailed here). The resulting complexity stays the same but the empirical running time is obviously slower. That is why we advise to use log-computation only when it is necessary (for example by considering first a rough approximation).