Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Minimally-overlapping words for sequence similarity search

Abstract : Analysis of genetic sequences is usually based on finding similar parts of sequences, e.g. DNA reads and/or genomes. For big data, this is typically done via “seeds”: simple similarities (e.g. exact matches) that can be found quickly. For huge data, sparse seeding is useful, where we only consider seeds at a subset of positions in a sequence. Here we study a simple sparse-seeding method: using seeds at positions of certain “words” (e.g. ac, at, gc, or gt). Sensitivity is maximized by using words with minimal overlaps. That is because, in a random sequence, minimally-overlapping words are anti-clumped. We provide evidence that this is often superior to acclaimed “minimizer” sparse-seeding methods. Our approach can be unified with design of inexact (spaced and subset) seeds, further boosting sensitivity. Thus, we present a promising approach to sequence similarity search, with open questions on how to optimize it.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Gregory Kucherov Connect in order to contact the contributor
Submitted on : Wednesday, December 9, 2020 - 7:40:39 PM
Last modification on : Wednesday, March 23, 2022 - 3:51:21 PM
Long-term archiving on: : Wednesday, March 10, 2021 - 8:06:36 PM


Files produced by the author(s)



Martin Frith, Laurent Noé, Gregory Kucherov. Minimally-overlapping words for sequence similarity search. 2020. ⟨hal-03049398⟩



Record views


Files downloads