Minimally overlapping words for sequence similarity search

Martin C. Frith, Laurent Noé, Gregory Kucherov

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)5344-5350
Number of pages7
JournalBioinformatics
Volume36
Issue number22-23
DOIs
Publication statusPublished - 1 Dec 2020

Fingerprint

Dive into the research topics of 'Minimally overlapping words for sequence similarity search'. Together they form a unique fingerprint.

Cite this