Skip to Main content Skip to Navigation
Journal articles

Minimally-overlapping words for sequence similarity search

Abstract : Motivation: 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. Results: 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. Supplementary information: Supplementary data are available at Bioinformatics online.
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-03087470
Contributor : Gregory Kucherov <>
Submitted on : Wednesday, December 23, 2020 - 8:59:02 PM
Last modification on : Monday, January 11, 2021 - 2:45:37 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-12-23

Please log in to resquest access to the document

Identifiers

Collections

Citation

Martin Frith, Laurent Noé, Gregory Kucherov. Minimally-overlapping words for sequence similarity search. Bioinformatics, Oxford University Press (OUP), 2020, ⟨10.1093/bioinformatics/btaa1054⟩. ⟨hal-03087470⟩

Share

Metrics

Record views

54