# Analytic Combinatorics for Computing Seeding Probabilities
## 4 Results
### Substitutions, Deletions and Insertions  
Here, we consider a model where all types of errors are allowed (also referred to as the \"full error model\"). Introducing insertions brings two additional difficulties: the first is that a substitution is indistinguishable from an insertion followed by a deletion (or a deletion followed by an insertion). By convention, we will count all these cases as substitutions. As a consequence, a deletion can never be found next to an insertion. The second difficulty is that insertions usually come in bursts. This is also the case of deletions, but we could neglect it because this does not affect the size of the interval (all deletions have size 0). To model insertion bursts, we need to assign a probability \(r\) to the first insertion, and a probability \(\tilde{r}>r\) to all subsequent insertions of the burst. We will still denote the probability of a substitution \(p\) and that of a correct nucleotide \(q\), but here \(p+q+r=1\). We will also assume that an insertion burst stops with probability \(1-\tilde{r}\) at each position of the burst. Under this error model, reads can be thought of as walks on the transfer graph shown in Figure 7. To not overload the figure, the body of the transfer graph is represented on the left, and the head and tail vertices on the right. The symbols \(\Delta_{0}\), \(S\) and \(I\) stand for error-free intervals, single substitutions and single insertions, respectively. The terms \(F(z)\), \(pz\) and \(\delta F(z)\) are the same as in Section 4.3. The terms \(rz\) and \(\tilde{rz}\) are the weighted generating functions of the first inserted nucleotide and of all subsequent nucleotides of the insertion burst, respectively. The burst terminates with probability \(1-\tilde{r}\) and is followed by an error-free interval or by a substitution. The total weight of these two cases is \(p+q<1\), so we need to further scale the weighted generating functions by a factor \(p+q=1-r\). The expression of the weighted generating function of error-free intervals \(F(z)\) is the same as in Section 4.3, namely  
\[F(z)=qz+(1-\delta)(qz)^{2}+(1-\delta)^{2}(qz)^{3}+\ldots=\frac{qz}{1-(1- \delta)qz}.\]  
Figure 7: _Transfer graph of reads under the full error model._ Reads are viewed as sequences of error-free intervals (symbol \(\Delta_{0}\)), substitutions (symbol \(S\)) or insertions (symbol \(I\)). The body of the transfer graph is shown on the left, and the head and tail edges are shown on the right. \(F(z)\) and \(pz\) are the weighted generating functions of error-free intervals and individual substitutions, respectively. \(\delta F(z)\) is the weighted generating function of a deletion followed by an error-free interval. \(rz\) and \(rz\) are the weighted generating functions of the first and all subsequent insertions of a burst, respectively. \((1-\tilde{r})F(z)/(1-r)\) is the weighted generating function of an error-free interval following an insertion and \((1-\tilde{r})pz/(1-r)\) is the weighted generating function of a substitution following an insertion. The head vertex is represented as a small white circle, and the tail vertex as a small black circle. The transfer matrix of the graph shown in Figure 7 is  
\[M_{*}(z)= \begin{array}{c}\circ\\ \Delta_{0}\\ \Delta_{0}\\ s\\ I\\ \bullet\end{array} \left( \begin{array}{c|cccc}\circ&\Delta_{0}&S&l&\bullet\\ \hline 0&F(z)&pz&rz&1\\ \hline 0&\delta F(z)&pz&rz&1\\ 0&F(z)&pz&rz&1\\ 0&\frac{1-r}{1-r}F(z)&\frac{1-r}{1-r}pz&\bar{r}z&1\\ \hline 0&0&0&0&0\end{array} \right)\]  
With the notations of Theorem 1, \(H(z)=(F(z),pz,rz)\), \(T(z)=(1,1,1)^{\top}\), \(\psi(z)=1\) and  
\[M(z)= \begin{array}{c}\Delta_{0}\\ S\\ I\\ \end{array} \left( \begin{array}{c|cccc}\delta F(z)&pz&rz\\ F(z)&pz&rz\\ \frac{1-r}{1-r}F(z)&\frac{1-r}{1-r}pz&\bar{r}z\end{array}