Minimally overlapping words for sequence similarity search

Martin C. Frith, Laurent Noé, Gregory Kucherov

Результат исследований: Вклад в журналСтатьярецензирование

3 Цитирования (Scopus)


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.

Язык оригиналаАнглийский
Страницы (с-по)5344-5350
Число страниц7
Номер выпуска22-23
СостояниеОпубликовано - 1 дек. 2020


Подробные сведения о темах исследования «Minimally overlapping words for sequence similarity search». Вместе они формируют уникальный семантический отпечаток (fingerprint).