# Analytic Combinatorics for Computing Seeding Probabilities
## 4 Results
### Substitutions and Deletions  
We now consider a model where errors can be deletions or substitutions, but not insertions. This case is not very realistic, but it will be useful to clarify how to construct reads with potential deletions. As in the case of uniform substitutions, we assume that every nucleotide call is false with a probability \(p\) and true with a probability \(1-p=q\). Here, we also assume that between every pair of decoded nucleotides in the read, an arbitrary number of nucleotides from the original molecule are deleted with probability \(\delta\). Regardless of the number of deleted nucleotides, all the deletions are equivalent when the read is viewed as a sequence of error-free intervals or error symbols (see Figure 2). A deletion may be adjacent to a substitution, or lie between two correct nucleotides. In the first case, the deletion does not interrupt any error-free interval so it does not change the probability that the read contains a seed. For this reason, we ignore deletions next to substitutions. More precisely, we assume that they can occur, but whether they do has no importance for the problem. Under this error model, a read can be thought of as a walk on the transfer graph shown in Figure 5. The graph is almost the same as the one shown Figure 3; the only difference is the edge labelled \(\delta F(z)\) from \(\Delta_{0}\) to \(\Delta_{0}\). This edge represents the fact that an error-free interval can follow another one if a deletion with weighted generating function \(\delta\) is present in between (as illustrated for instance in Figure 2). The weighted generating function of error-free intervals \(F(z)\) has a different expression from that of Section 4.2. When the size of an error-free interval is 1, the weighted generating function is just \(qz\). For a size \(k>1\), there are \(k-1\) \"spaces\" between the nucleotides, so the weighted generating function is \((1-\delta)^{k-1}(qz)^{k}\). Summing for all the possible sizes, we obtain the weighted generating function of error-free intervals as  
\[F(z)=qz+(1-\delta)(qz)^{2}+(1-\delta)^{2}(qz)^{3}+\ldots=\frac{qz}{1-(1-\delta )qz}. \tag{13}\]  
The transfer matrix of the graph shown in Figure 5 is  
Figure 4: _Example estimates for substitutions only._ The analytic combinatorics estimates of Proposition 2 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 2 (lines). The curves are drawn for \(\gamma=17\) and \(p=0.08\), \(p=0.10\) or \(p=0.12\) (from top to bottom). \[\frac{C}{z_{1}^{k+1}},\]  
_where \(z_{1}\) is the root with smallest modulus of \(1-pz-\big{(}pz(1-\delta)+\delta\big{)}\big{(}qz+(1-\delta)(qz)^{2}+\ldots+(1- \delta)^{\gamma-2}(qz)^{\gamma-1}\big{)}\), and where_  
\[ \begin{split} C&=\frac{z_{1}\big{(}1-(1-\delta)qz_{1 }\big{)}^{2}}{\big{(}(p+q\delta)z_{1}-c_{1}(1-\delta)^{\gamma-1}(qz_{1})^{ \gamma}\big{)}\left(\delta+(1-\delta)pz_{1}\right)},\text{with}\\ c_{1}&=\gamma\delta-(1-\delta)\big{(}(\gamma-1) \delta-p\big{(}(\gamma-1)\delta+\gamma+1)\big{)}z_{1}-\gamma(1-\delta)^{2}pqz_ {1}^{2}.\end{split}  \tag{16}\]  
_If \(z_{1}=1/\big{(}(1-\delta)q\big{)}\), expression (16) is undefined and the constant \(C\) should be computed as \(-P(z_{1})/Q^{\prime}(z_{1})\), where \(P(z)\) and \(Q(z)\) are the respective numerator and denominator of \(S_{\gamma}(z)\) in expression (15)._  
**Example 4**. : _Approximate the probability that a read of size \(k=100\) has no seed for \(\gamma=17\), \(p=0.05\) and \(\delta=0.15\). To find the dominant singularity of \(S_{17}\), we solve \(1-0.05z-\big{(}0.0425z+0.15\big{)}(0.95z+0.85(0.95z)^{2}+\ldots+0.85^{15}(0.95 z)^{16}\big{)}=0\). We write it as \(1-0.05z-\big{(}0.0425z+0.15\big{)}(0.95z-0.85^{16}(0.95z)^{17}\big{)}/(1-0.8075 z)=0\) and use numerical bisection to obtain \(z_{1}\approx 1.006705\).