# Analytic Combinatorics for Computing Seeding Probabilities
## 4 Results  
### Reads, Error Symbols and Error-Free Intervals  
From the experimental point of view, a sequencing read is the result of an assay on some polymer of nucleic acid. The output of the assay is the decoded sequence of monomers that compose the molecule. Three types of sequencing errors can occur: _substitutions_, _deletions_ and _insertions_. A substitution is a nucleotide that is different in the molecule and in the read, a deletion is a nucleotide that is present in the molecule but not in the read, and an insertion is a nucleotide that is absent in the molecule but present in the read. For our purpose, the focus is not the nucleotide sequence per se, but whether the nucleotides are correct. Thus, we need only four symbols to describe a read: one for each type of error, plus one for correct nucleotides. In this view, a read is a finite sequence of letters from an alphabet of four symbols. Figure 1 shows the typical structure of a read.  
A read can be partitioned uniquely into maximal sequences of identical symbols referred to as \"intervals\". Thus, reads can also be seen as sequences of either error-free intervals or error symbols (Figure 2). As detailed below, this will allow us to control the size of the largest error-free interval.  
These concepts established, we can compute seeding probabilities in the read mapping problem. We define an \"exact \(\gamma\)-seed\", or simply a seed, as an exact match of minimum size \(\gamma\) between the read and the actual sequence of the molecule. In other words, an exact \(\gamma\)-seed is an error-free interval of size at least \(\gamma\). Because of sequencing errors, it could be that the read contains no seed. In this case, the read cannot be mapped to the correct location if the mapping algorithm requires seeds of size \(\gamma\) or greater.  
Our goal is to construct estimators of the probability that a read contains an exact \(\gamma\)-seed based on expected sequencing errors. For this, we will construct the weighted generating functions of reads that _do not_ contain an exact \(\gamma\)-seed by decomposing them as sequences of either error symbols or error-free intervals of size less than \(\gamma\). We will obtain their weighted generating functions from Theorem 1 and use Theorem 2 to approximate their probability of occurrence. With the weighted generating function of all the reads \(R(z)\), and that of reads without an exact \(\gamma\)-seed \(S_{\gamma}(z)\), the probability that a read of size \(k\) has no exact \(\gamma\)-seed can be computed as \([z^{k}]S_{\gamma}(z)/[z^{k}]R(z)\), i.e., the total weight of reads of size \(k\) without seed divided by the total weight of reads of size \(k\).  
Figure 1: _Read as sequence of symbols._ Reads consist of correct nucleotides (white boxes), substitutions (black boxes), deletions (vertical bars) and insertions (grey boxes). A single deletion can correspond to several missing nucleotides.  
Figure 2: _Read as sequence of error-free intervals or error symbols._ Consecutive correct nucleotides can be lumped together in error-free intervals. The representation of a read as a sequence of either error-free intervals or error symbols is unique.