Cargando…

Efficient taxa identification using a pangenome index

Tools that classify sequencing reads against a database of reference sequences require efficient index data-structures. The r-index is a compressed full-text index that answers substring presence/absence, count, and locate queries in space proportional to the amount of distinct sequence in the datab...

Descripción completa

Detalles Bibliográficos
Autores principales: Ahmed, Omar, Rossi, Massimiliano, Boucher, Christina, Langmead, Ben
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Cold Spring Harbor Laboratory Press 2023
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10538492/
https://www.ncbi.nlm.nih.gov/pubmed/37258301
http://dx.doi.org/10.1101/gr.277642.123
_version_ 1785113317931483136
author Ahmed, Omar
Rossi, Massimiliano
Boucher, Christina
Langmead, Ben
author_facet Ahmed, Omar
Rossi, Massimiliano
Boucher, Christina
Langmead, Ben
author_sort Ahmed, Omar
collection PubMed
description Tools that classify sequencing reads against a database of reference sequences require efficient index data-structures. The r-index is a compressed full-text index that answers substring presence/absence, count, and locate queries in space proportional to the amount of distinct sequence in the database: [Formula: see text] space, where r is the number of Burrows–Wheeler runs. To date, the r-index has lacked the ability to quickly classify matches according to which reference sequences (or sequence groupings, i.e., taxa) a match overlaps. We present new algorithms and methods for solving this problem. Specifically, given a collection [Formula: see text] of d documents, [Formula: see text] over an alphabet of size [Formula: see text] , we extend the r-index with [Formula: see text] additional words to support document listing queries for a pattern [Formula: see text] that occurs in [Formula: see text] documents in [Formula: see text] in [Formula: see text] time and [Formula: see text] space, where w is the machine word size. Applied in a bacterial mock community experiment, our method is up to three times faster than a comparable method that uses the standard r-index locate queries. We show that our method classifies both simulated and real nanopore reads at the strain level with higher accuracy compared with other approaches. Finally, we present strategies for compacting this structure in applications in which read lengths or match lengths can be bounded.
format Online
Article
Text
id pubmed-10538492
institution National Center for Biotechnology Information
language English
publishDate 2023
publisher Cold Spring Harbor Laboratory Press
record_format MEDLINE/PubMed
spelling pubmed-105384922023-09-29 Efficient taxa identification using a pangenome index Ahmed, Omar Rossi, Massimiliano Boucher, Christina Langmead, Ben Genome Res Methods Tools that classify sequencing reads against a database of reference sequences require efficient index data-structures. The r-index is a compressed full-text index that answers substring presence/absence, count, and locate queries in space proportional to the amount of distinct sequence in the database: [Formula: see text] space, where r is the number of Burrows–Wheeler runs. To date, the r-index has lacked the ability to quickly classify matches according to which reference sequences (or sequence groupings, i.e., taxa) a match overlaps. We present new algorithms and methods for solving this problem. Specifically, given a collection [Formula: see text] of d documents, [Formula: see text] over an alphabet of size [Formula: see text] , we extend the r-index with [Formula: see text] additional words to support document listing queries for a pattern [Formula: see text] that occurs in [Formula: see text] documents in [Formula: see text] in [Formula: see text] time and [Formula: see text] space, where w is the machine word size. Applied in a bacterial mock community experiment, our method is up to three times faster than a comparable method that uses the standard r-index locate queries. We show that our method classifies both simulated and real nanopore reads at the strain level with higher accuracy compared with other approaches. Finally, we present strategies for compacting this structure in applications in which read lengths or match lengths can be bounded. Cold Spring Harbor Laboratory Press 2023-07 /pmc/articles/PMC10538492/ /pubmed/37258301 http://dx.doi.org/10.1101/gr.277642.123 Text en © 2023 Ahmed et al.; Published by Cold Spring Harbor Laboratory Press https://creativecommons.org/licenses/by/4.0/This article, published in Genome Research, is available under a Creative Commons License (Attribution 4.0 International), as described at http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) .
spellingShingle Methods
Ahmed, Omar
Rossi, Massimiliano
Boucher, Christina
Langmead, Ben
Efficient taxa identification using a pangenome index
title Efficient taxa identification using a pangenome index
title_full Efficient taxa identification using a pangenome index
title_fullStr Efficient taxa identification using a pangenome index
title_full_unstemmed Efficient taxa identification using a pangenome index
title_short Efficient taxa identification using a pangenome index
title_sort efficient taxa identification using a pangenome index
topic Methods
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10538492/
https://www.ncbi.nlm.nih.gov/pubmed/37258301
http://dx.doi.org/10.1101/gr.277642.123
work_keys_str_mv AT ahmedomar efficienttaxaidentificationusingapangenomeindex
AT rossimassimiliano efficienttaxaidentificationusingapangenomeindex
AT boucherchristina efficienttaxaidentificationusingapangenomeindex
AT langmeadben efficienttaxaidentificationusingapangenomeindex