k-nonical space: sketching with reverse complements

Abstract

Motivation: Sequences equivalent to their reverse complements (i.e. double-stranded DNA) have no analogue in text analysis and non-biological string algorithms. Despite this striking difference, algorithms designed for computational biology (e.g. sketching algorithms) are designed and tested in the same way as classical string algorithms. Then, as a post-processing step, these algorithms are adapted to work with genomic sequences by folding a k-mer and its reverse complement into a single sequence: The canonical representation (k-nonical space).

Results: The effect of using the canonical representation with sketching methods is understudied and not understood. As a first step, we use context-free sketching methods to illustrate the potentially detrimental effects of using canonical k-mers with string algorithms not designed to accommodate for them. In particular, we show that large stretches of the genome ("sketching deserts") are undersampled or entirely skipped by context-free sketching methods, effectively making these genomic regions invisible to subsequent algorithms using these sketches. We provide empirical data showing these effects and develop a theoretical framework explaining the appearance of sketching deserts. Finally, we propose two schemes to accommodate for these effects: (i) a new procedure that adapts existing sketching methods to k-nonical space and (ii) an optimization procedure to directly design new sketching methods for k-nonical space.

Availability and implementation: The code used in this analysis is available under a permissive license at https://github.com/Kingsford-Group/mdsscope.

Figure 1.

The left-most tie breaking rule implies a relaxed window guarantee for syncmers when $t\le s/2$. In this example, $k=9,t=2,s=5$, and the alphabetic order on 5-mers is used. The 9-mer is not selected because the 5-mer at position 2 is equal to the 5-mer at position 0 and the left-most tie breaking rule. Because this 5-mer overlaps with itself, it is “almost” repetitive: It is a sesqui-power $x^{n}y$ with $x=\mathtt{AC},y=\mathtt{A},n=2$. Repetitive sequences of length t = 2 are skipped over.

Figure 2.

For k = 6 and σ  =  2, examples of PCRs. Every k-mer on the left side is a canonical k-mer ($\in \mathcal{C}$), and k-mers symmetrical compared to the vertical line are reverse complement of each other. The k-mers inside gray boxes are an example of set $\phi$, and the k-mers in dashed boxes are the corresponding ${\phi }^{\mathrm{c}}$ set. $\mathtt{000010}$ is in both $\phi$ and ${\phi }^{\mathrm{c}}$ (case a). Not every PCR is covered by ${\phi }^{\mathrm{c}}$, and consequently ${\phi }^{\mathrm{c}}$ is not decycling (cases b and c).