Minimally-overlapping words for sequence similarity search - Archive ouverte HAL Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

Minimally-overlapping words for sequence similarity search

Résumé

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.
Fichier principal
Vignette du fichier
2020.07.24.220616v2.full.pdf (433.26 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03049398 , version 1 (09-12-2020)

Identifiants

Citer

Martin Frith, Laurent Noé, Gregory Kucherov. Minimally-overlapping words for sequence similarity search. 2020. ⟨hal-03049398⟩
39 Consultations
49 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More