# Analytic Combinatorics for Computing Seeding Probabilities
## 4 Results
### Substitutions Only  
In the simplest model, we assume that errors can be only substitutions, and that they occur with the same probability \(p\) for every nucleotide. Importantly, the model is not overly simple and it has some real applications. For instance, it describes reasonably well the error model of the Illumina platforms, where \(p\) is around 0.01 [26]. Under this error model, reads are sequences of single substitutions or error-free intervals. They can be thought of as walks on the transfer graph shown in Figure 3. The symbol \(\Delta_{0}\) stands for an error-free interval and the symbol \(S\) stands for a single substitution. \(F(z)\) and \(pz\) are the weighted generating functions of error-free intervals and substitutions, respectively. The fact that an error-free interval cannot follow another error-free interval is a consequence of the definition: two consecutive intervals are automatically merged into a single one. A substitution is a single nucleotide and thus has size 1. Because substitutions have probability \(p\), their weighted generating function is \(pz\). Conversely, the weighted generating function of correct nucleotides is \(qz\), where \(q=1-p\). Error-free intervals are non-empty sequences of correct nucleotides, so by Proposition 1 their weighted generating function is  
\[F(z)=qz+(qz)^{2}+(qz)^{3}+\ldots=\frac{qz}{1-qz}. \tag{8}\]  
The transfer matrix of the graph shown in Figure 3 is  
\[M_{*}(z)= \begin{array}{c|c|c|c}&\circ&\Delta_{0}&S&\bullet\\ \circ&\circ&F(z)&pz&1\\ \cline{2-5}\Delta_{0}&0&0&pz&1\\ \cline{2-5}S&0&F(z)&pz&1\\ \cline{2-5}\bullet&0&0&0&0\\ \end{array} \end{array}\]  
With the notations of Theorem 1, we have \(H(z)=(F(z),pz)\), \(T(z)=(1,1)^{\top}\), \(\psi(z)=1\) and  
\[M(z)= \begin{array}{c}\Delta_{0}&S\\ \circ&\circ&pz\\ \cline{2-5}F(z)&pz\\ \end{array} \]  
Applying Theorem 1, \(R(z)\), the weighted generating function of all reads is found from the formula \(R(z)=\psi(z)+H(z)\cdot(I-M(z))^{-1}\cdot T(z)\), which, in this case, translates to  
Figure 3: Transfer graph of reads with uniform substitutions. Reads are viewed as sequences of error-free intervals (symbol \(\Delta_{0}\)) or substitutions (symbol \(S\)). \(F(z)\) and \(pz\) are the weighted generating functions of error-free intervals and individual substitutions, respectively. The head vertex is represented as a small white circle, and the tail vertex as a small black circle. \[R(z)=1+(F(z),pz)\cdot\frac{1}{\lambda(z)} \begin{pmatrix}1-pz&pz\\ F(z)&1\end{pmatrix} \cdot \begin{pmatrix}1\\ 1\end{pmatrix} ,\]  
where \(\lambda(z)=1-pz(1+F(z))\) is the determinant of \(I-M(z)\). Using equation (8), this expression simplifies to  
\[R(z)=\frac{1+F(z)}{1-pz(1+F(z))}=\frac{1}{1-z}. \tag{9}\]  
Since \(1/(1-z)=1+z+z^{2}+\ldots\), the total weight of reads of size \(k\) is equal to \(1\) for any \(k\geq 0\). As a consequence, \([z^{k}]R(z)=1\) and the probability that a read of size \(k\) has no exact \(\gamma\)-seed is equal to \([z^{k}]S_{\gamma}(z)\). To find the weighted generating function of reads without an exact \(\gamma\)-seed, we limit error-free intervals to a maximum size of \(\gamma-1\). To do this, we can replace \(F(z)\) in expression (9) by its truncation \(F_{\gamma}(z)=qz+(qz)^{2}+\ldots+(qz)^{\gamma-1}\). We obtain  
\[S_{\gamma}(z)=\frac{1+F_{\gamma}(z)}{1-pz\big{(}1+F_{\gamma}(z)\big{)}}= \frac{1+qz+\ldots+(qz)^{\gamma-1}}{1-pz\big{(}1+qz+\ldots+(qz)^{\gamma-1}\big{)}}. \tag{10}\]  
Now applying Theorem 2 to the expression of \(S_{\gamma}(z)\) above, we obtain the following proposition.