# Analytic Combinatorics for Computing Seeding Probabilities
## 4 Results
### Substitutions, Deletions and Insertions
\right)\]  
From Theorem 1, the weighted generating function of all reads is \(\psi(z)+H(z)\cdot(I-M(z))^{-1}\cdot T(z)\), which is equal to  
\[R(z)=\frac{(1-r)\big{(}1-(\bar{r}-r)z\big{)}\;(1+(1-\delta)F(z))}{1-a(z)-b(z)F( z)}, \tag{18}\]  
where \(a(z)\) and \(b(z)\) are second degree polynomials defined as  
\[a(z)=r+(1-r)(p+\bar{r})z-p(\bar{r}-r)z^{2},\text{ and } \tag{19}\] \[b(z)=\delta(1-r)+\big{(}(1-r)(p-\delta(p+\bar{r}))+(1-\bar{r})r \big{)}z-p(1-\delta)(\bar{r}-r)z^{2}.\]  
Substituting in (18) the expressions of \(F(z)\), \(a(z)\) and \(b(z)\), we find  
\[R(z)=\frac{1}{1-z}. \tag{20}\]  
Again, we obtain the simple expression \(1/(1-z)=1+z+z^{2}+\ldots\) and the probability that a read of size \(k\) contains no seed is \([z^{k}]S_{\gamma}(z)\). To find the weighted generating function of reads without an exact \(\gamma\)-seed, we replace \(F(z)\) in expression (18) by its truncated version  
\[F_{\gamma}(z)=qz+(1-\delta)(qz)^{2}+(1-\delta)^{2}(qz)^{3}+\ldots+(1-\delta)^ {\gamma-2}(qz)^{\gamma-1}.\]  
We obtain the following expression  
\[S_{\gamma}(z)=\frac{(1-r)\big{(}1-(\bar{r}-r)z\big{)}\;(1+(1-\delta)F_{\gamma }(z))}{1-a(z)-b(z)F_{\gamma}(z)}, \tag{21}\]  
where \(a(z)\) and \(b(z)\) are defined as in expression (19). **Remark 2**. : _Note that when \(r=\bar{r}=0\), then \(a(z)=pz\) and \(b(z)=pz(1-\delta)+\delta\), expression (21) becomes_  
\[S_{\gamma}(z)=\frac{1+(1-\delta)F_{\gamma}(z)}{1-pz-(pz(1-\delta)+\delta))F_{ \gamma}(z)}.\]  
_This is expression (15), i.e., the model described in Section 4.3. When we also have \(\delta=0\), this expression further simplifies to_  
\[S_{\gamma}(z)=\frac{1+F_{\gamma}(z)}{1-pz(1+F_{\gamma}(z))}.\]_This is expression (10), i.e., the model described in Section 4.2. In other words, the error models described previously are special cases of this error model._  
As in the previous sections, we can use Theorem 2 to obtain asymptotic approximations for the probability that the reads contain no seed. **Proposition 4**. : _The probability that a read of size \(k\) has no seed under the error model with substitutions, deletions and insertions is asymptotically equivalent to_  
\[\frac{C}{z_{1}^{k+1}},\]  
_where \(z_{1}\) is the root with smallest modulus of the polynomial \(1-a(z)-b(z)F_{\gamma}(z)\) and_  
\[C=\frac{\left(1-r\right)\left(1-(\tilde{r}-r)z_{1}\right)\left(1+(1-\delta)F_ {\gamma}(z_{1})\right)}{a^{\prime}(z_{1})+b^{\prime}(z_{1})F_{\gamma}(z_{1})+ b(z_{1})F_{\gamma}^{\prime}(z_{1})}. \tag{22}\]  
_If \(z_{1}=1/((1-\delta)q)\), then \(F_{\gamma}(z_{1})=(\gamma-1)/(1-\delta)\) and \(F_{\gamma}^{\prime}(z_{1})=q\gamma(\gamma-1)/2\). Otherwise,_  
\[a(z)=r+(1-r)(p+\bar{r})z-p(\bar{r}-r)z^{2},\text{ and } \tag{19}\]0 \[a(z)=r+(1-r)(p+\bar{r})z-p(\bar{r}-r)z^{2},\text{ and } \tag{19}\]1  
_If \(z_{1}=1/(\tilde{r}-r)\), then \(1-(\tilde{r}-r)z\) divides the numerator and the denominator, which should be simplified to remain coprime. In this case, Theorem 2 should be applied to the simplified rational function._  
**Example 5**. : _Approximate the probability that a read of size \(k=100\) has no seed for \(\gamma=17\), \(p=0.05\), \(\delta=0.15\), \(r=0.05\) and \(\tilde{r}=0.45\). With these values, \(a(z)=0.05+0.475z-0.02z^{2}\) and \(b(z)=0.1425+0.00375z-0.017z^{2}\). We need to solve \(0.95-0.475z+0.02z^{2}-(0.1425+0.00375z-0.017z^{2})(0.9z+0.85(0.9z)^{2}+\ldots+ 0.85^{15}(0.9z)^{16})=0\). We rewrite the equation as \(0.95-0.475z+0.02z^{2}-(0.1425+0.00375z-0.017z^{2})(0.9z-0.85^{15}(0.9z)^{16})/ (1-0.765z)=0\) and use bisection to solve it numerically, yielding \(z_{1}\approx 1.00295617\). From expression (22), we obtain \(C\approx 1.042504\), so the probability that a read contains no seed is approximately \(1.042504/1.00295617^{101}\approx 0.773749\). For comparison, a \(99\%\) confidence interval obtained by performing 10 billion random simulations is \(0.77373-0.77376\)._  
Once again, the analytic combinatorics estimates are accurate.