Cargando…
Minimally overlapping words for sequence similarity search
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 onl...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Oxford University Press
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8016470/ https://www.ncbi.nlm.nih.gov/pubmed/33346833 http://dx.doi.org/10.1093/bioinformatics/btaa1054 |
_version_ | 1783673866235674624 |
---|---|
author | Frith, Martin C Noé, Laurent Kucherov, Gregory |
author_facet | Frith, Martin C Noé, Laurent Kucherov, Gregory |
author_sort | Frith, Martin C |
collection | PubMed |
description | 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. AVAILABILITY AND IMPLEMENTATION: Software to design and test minimally overlapping words is freely available at https://gitlab.com/mcfrith/noverlap. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online. |
format | Online Article Text |
id | pubmed-8016470 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
publisher | Oxford University Press |
record_format | MEDLINE/PubMed |
spelling | pubmed-80164702021-04-07 Minimally overlapping words for sequence similarity search Frith, Martin C Noé, Laurent Kucherov, Gregory Bioinformatics Original Papers 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. AVAILABILITY AND IMPLEMENTATION: Software to design and test minimally overlapping words is freely available at https://gitlab.com/mcfrith/noverlap. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online. Oxford University Press 2020-12-21 /pmc/articles/PMC8016470/ /pubmed/33346833 http://dx.doi.org/10.1093/bioinformatics/btaa1054 Text en © The Author(s) 2020. Published by Oxford University Press. http://creativecommons.org/licenses/by/4.0/ This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Original Papers Frith, Martin C Noé, Laurent Kucherov, Gregory Minimally overlapping words for sequence similarity search |
title | Minimally overlapping words for sequence similarity search |
title_full | Minimally overlapping words for sequence similarity search |
title_fullStr | Minimally overlapping words for sequence similarity search |
title_full_unstemmed | Minimally overlapping words for sequence similarity search |
title_short | Minimally overlapping words for sequence similarity search |
title_sort | minimally overlapping words for sequence similarity search |
topic | Original Papers |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8016470/ https://www.ncbi.nlm.nih.gov/pubmed/33346833 http://dx.doi.org/10.1093/bioinformatics/btaa1054 |
work_keys_str_mv | AT frithmartinc minimallyoverlappingwordsforsequencesimilaritysearch AT noelaurent minimallyoverlappingwordsforsequencesimilaritysearch AT kucherovgregory minimallyoverlappingwordsforsequencesimilaritysearch |