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

https://hal-upec-upem.archives-ouvertes.fr/hal-03049398
Contributor : Gregory Kucherov <>
Submitted on : Wednesday, December 9, 2020 - 7:40:39 PM
Last modification on : Monday, December 14, 2020 - 8:39:33 AM
Long-term archiving on: : Wednesday, March 10, 2021 - 8:06:36 PM

File

2020.07.24.220616v2.full.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

22

Files downloads

50