Cargando…

BLEND: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis

Generating the hash values of short subsequences, called seeds, enables quickly identifying similarities between genomic sequences by matching seeds with a single lookup of their hash values. However, these hash values can be used only for finding exact-matching seeds as the conventional hashing met...

Descripción completa

Detalles Bibliográficos
Autores principales: Firtina, Can, Park, Jisung, Alser, Mohammed, Kim, Jeremie S, Cali, Damla Senol, Shahroodi, Taha, Ghiasi, Nika Mansouri, Singh, Gagandeep, Kanellopoulos, Konstantinos, Alkan, Can, Mutlu, Onur
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Oxford University Press 2023
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9853099/
https://www.ncbi.nlm.nih.gov/pubmed/36685727
http://dx.doi.org/10.1093/nargab/lqad004
_version_ 1784872819437338624
author Firtina, Can
Park, Jisung
Alser, Mohammed
Kim, Jeremie S
Cali, Damla Senol
Shahroodi, Taha
Ghiasi, Nika Mansouri
Singh, Gagandeep
Kanellopoulos, Konstantinos
Alkan, Can
Mutlu, Onur
author_facet Firtina, Can
Park, Jisung
Alser, Mohammed
Kim, Jeremie S
Cali, Damla Senol
Shahroodi, Taha
Ghiasi, Nika Mansouri
Singh, Gagandeep
Kanellopoulos, Konstantinos
Alkan, Can
Mutlu, Onur
author_sort Firtina, Can
collection PubMed
description Generating the hash values of short subsequences, called seeds, enables quickly identifying similarities between genomic sequences by matching seeds with a single lookup of their hash values. However, these hash values can be used only for finding exact-matching seeds as the conventional hashing methods assign distinct hash values for different seeds, including highly similar seeds. Finding only exact-matching seeds causes either (i) increasing the use of the costly sequence alignment or (ii) limited sensitivity. We introduce BLEND, the first efficient and accurate mechanism that can identify both exact-matching and highly similar seeds with a single lookup of their hash values, called fuzzy seed matches. BLEND (i) utilizes a technique called SimHash, that can generate the same hash value for similar sets, and (ii) provides the proper mechanisms for using seeds as sets with the SimHash technique to find fuzzy seed matches efficiently. We show the benefits of BLEND when used in read overlapping and read mapping. For read overlapping, BLEND is faster by 2.4×–83.9× (on average 19.3×), has a lower memory footprint by 0.9×–14.1× (on average 3.8×), and finds higher quality overlaps leading to accurate de novo assemblies than the state-of-the-art tool, minimap2. For read mapping, BLEND is faster by 0.8×–4.1× (on average 1.7×) than minimap2. Source code is available at https://github.com/CMU-SAFARI/BLEND.
format Online
Article
Text
id pubmed-9853099
institution National Center for Biotechnology Information
language English
publishDate 2023
publisher Oxford University Press
record_format MEDLINE/PubMed
spelling pubmed-98530992023-01-20 BLEND: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis Firtina, Can Park, Jisung Alser, Mohammed Kim, Jeremie S Cali, Damla Senol Shahroodi, Taha Ghiasi, Nika Mansouri Singh, Gagandeep Kanellopoulos, Konstantinos Alkan, Can Mutlu, Onur NAR Genom Bioinform Methods Article Generating the hash values of short subsequences, called seeds, enables quickly identifying similarities between genomic sequences by matching seeds with a single lookup of their hash values. However, these hash values can be used only for finding exact-matching seeds as the conventional hashing methods assign distinct hash values for different seeds, including highly similar seeds. Finding only exact-matching seeds causes either (i) increasing the use of the costly sequence alignment or (ii) limited sensitivity. We introduce BLEND, the first efficient and accurate mechanism that can identify both exact-matching and highly similar seeds with a single lookup of their hash values, called fuzzy seed matches. BLEND (i) utilizes a technique called SimHash, that can generate the same hash value for similar sets, and (ii) provides the proper mechanisms for using seeds as sets with the SimHash technique to find fuzzy seed matches efficiently. We show the benefits of BLEND when used in read overlapping and read mapping. For read overlapping, BLEND is faster by 2.4×–83.9× (on average 19.3×), has a lower memory footprint by 0.9×–14.1× (on average 3.8×), and finds higher quality overlaps leading to accurate de novo assemblies than the state-of-the-art tool, minimap2. For read mapping, BLEND is faster by 0.8×–4.1× (on average 1.7×) than minimap2. Source code is available at https://github.com/CMU-SAFARI/BLEND. Oxford University Press 2023-01-20 /pmc/articles/PMC9853099/ /pubmed/36685727 http://dx.doi.org/10.1093/nargab/lqad004 Text en © The Author(s) 2023. Published by Oxford University Press on behalf of NAR Genomics and Bioinformatics. https://creativecommons.org/licenses/by/4.0/This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Methods Article
Firtina, Can
Park, Jisung
Alser, Mohammed
Kim, Jeremie S
Cali, Damla Senol
Shahroodi, Taha
Ghiasi, Nika Mansouri
Singh, Gagandeep
Kanellopoulos, Konstantinos
Alkan, Can
Mutlu, Onur
BLEND: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis
title BLEND: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis
title_full BLEND: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis
title_fullStr BLEND: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis
title_full_unstemmed BLEND: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis
title_short BLEND: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis
title_sort blend: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis
topic Methods Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9853099/
https://www.ncbi.nlm.nih.gov/pubmed/36685727
http://dx.doi.org/10.1093/nargab/lqad004
work_keys_str_mv AT firtinacan blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT parkjisung blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT alsermohammed blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT kimjeremies blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT calidamlasenol blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT shahrooditaha blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT ghiasinikamansouri blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT singhgagandeep blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT kanellopouloskonstantinos blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT alkancan blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis
AT mutluonur blendafastmemoryefficientandaccuratemechanismtofindfuzzyseedmatchesingenomeanalysis