Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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.
Liste complète des métadonnées
Contributeur : Gregory Kucherov Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 décembre 2020 - 20:59:02
Dernière modification le : mercredi 23 mars 2022 - 15:51:21


Fichiers éditeurs autorisés sur une archive ouverte



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⟩



Consultations de la notice


Téléchargements de fichiers