# Analytic Combinatorics for Computing Seeding Probabilities
## 4 Results
### Accuracy of the Approximations  
So far, all the examples showed that the analytic combinatorics approximations are accurate. Indeed, the main motivation for our approach is to find estimates that converge exponentially fast to the target value. To find out whether we can use the approximations in place of the true values, we need to describe the behavior of the estimates in the worst conditions. The approximations become more accurate as the size of the sequence increases, i.e., as the reads become longer. This is somewhat inconvenient: the read size is usually fixed by the technology or by the problem at hand, so the user does not have easy ways to improve the accuracy. Overall, the approximations described above tend to be less accurate for short reads. Another aspect is convergence speed. The proof of Theorem 2 shows that the rate of convergence is fastest when the dominant singularity has a significantly smaller _modulus_ than the other singularities. Conversely, convergence is slowest when at least one other singularity is almost as close to 0. The worst case for the approximation is thus when the reads are small and when the parameters are such that singularities have relatively close _moduli_. It can be shown that, for the error model of uniform substitutions, this corresponds to small values of the error rate \(p\) (see Appendix A). In practical terms, the situation above describes the specifications of the Illumina technology, where errors are almost always substitutions, occurring at a frequency around 1% on current instruments. Since the reads are often around 50 nucleotides, the analytic combinatorics estimates of the seeding probabilities are typically less accurate than suggested in the previous sections. Figure 9 shows the accuracy of the estimates in one of the worst cases. The analytic combinatorics estimates are clearly distinct from the simulation estimates at the chosen scale, but the absolute difference is never higher than approximately 0.015 (and lower for read sizes above 40). Whether this error is acceptable depends on the problem. Often \(p\) itself must be estimated, which is a more serious limitation on the precision than the convergence speed of the estimates. In most practical applications, the approximation error of Theorem 2 can be tolerated even in the worst case, but it is important to bear in mind that it may not be negligible for reads of size 50 or lower. If this level of precision is insufficient, the best option is to compute the coefficients by recurrence. Figure 8: _Example estimates for substitutions, deletions and insertions._ The analytic combinatorics estimates of Proposition 4 are benchmarked against random simulations. Shown on both panels are the probabilities that a read of given size contains a seed, either estimated by 10,000,000 random simulations (dots), or by Proposition 4 (lines). The curves are drawn for \(\gamma=17\), \(p=0.05\), \(\delta=0.15\), \(\bar{r}=0.45\) and \(r=0.04\), \(r=0.05\) or \(r=0.06\) (from top to bottom). For long reads, the approximations rapidly gain in accuracy. Importantly, the calculations are also numerically stable, even for very long reads and for very high values of the error rate. To explore the behavior of the estimates, they were computed over a wide range of conditions, and compared to the values obtained by computing recurrence (12). The value of \(s_{k}\) is the _exact_ probability that a read of size \(k\) does not contain a seed in the uniform substitution error model, when the probability of substitution is equal to \(p\). However, because the numbers are represented with finite precision, the computed value of \(s_{k}\) is also inexact in practice. Figure 10 shows the relative error of the estimates given by Proposition 2, as compared to the value of \(s_{k}\) computed through equation (12) in double precision arithmetic. For all the tested values of \(p\), the relative error first decreases to approximately \(10^{-15}\) and then slowly rises.