Efficient construction of a complete index for pan-genomics read alignment

DOI10.1007/978-3-030-17083-7_10zbMATH Open1412.92202arXiv1811.06933OpenAlexW2901237963MaRDI QIDQ2415261FDOQ2415261

Authors: Alan Kuhnle, Taher Mun, Christina Boucher, Travis Gagie, Ben Langmead, Giovanni Manzini 

Publication date: 21 May 2019

Abstract: While short read aligners, which predominantly use the FM-index, are able to easily index one or a few human genomes, they do not scale well to indexing databases containing thousands of genomes. To understand why, it helps to examine the main components of the FM-index in more detail, which is a rank data structure over the Burrows-Wheeler Transform (BWT) of the string that will allow us to find the interval in the string's suffix array (SA) containing pointers to starting positions of occurrences of a given pattern; second, a sample of the SA that --- when used with the rank data structure --- allows us access the SA. The rank data structure can be kept small even for large genomic databases, by run-length compressing the BWT, but until recently there was no means known to keep the SA sample small without greatly slowing down access to the SA. Now that Gagie et al. (SODA 2018) have defined an SA sample that takes about the same space as the run-length compressed BWT --- we have the design for efficient FM-indexes of genomic databases but are faced with the problem of building them. In 2018 we showed how to build the BWT of large genomic databases efficiently (WABI 2018) but the problem of building Gagie et al.'s SA sample efficiently was left open. We compare our approach to state-of-the-art methods for constructing the SA sample, and demonstrate that it is the fastest and most space-efficient method on highly repetitive genomic databases. Lastly, we apply our method for indexing partial and whole human genomes, and show that it improves over Bowtie with respect to both memory and time.

Full work available at URL: https://arxiv.org/abs/1811.06933

Recommendations

• FM-index of alignment with gaps
• FM-index of alignment: a compressed index for similar strings
• scientific article; zbMATH DE number 7716299
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Refining the \(r\)-index

zbMATH Keywords

Burrows-Wheeler transformpan-genomicsread alignment index

Mathematics Subject Classification ID

Genetics and epigenetics (92D10)

Cited In (15)

• Tailoring r-index for Document Listing Towards Metagenomics Applications
• Pangenomic genotyping with the marker array
• Toward optimal fingerprint indexing for large scale genomics
• Title not available (Why is that?)
• An LMS-based grammar self-index with local consistency properties
• Computing the original eBWT faster, simpler, and with less memory
• Refining the \(r\)-index
• Spectrum preserving tilings enable sparse and modular reference indexing
• Big-BWT
• r-index
• MAGE: strain level profiling of metagenome samples
• Acceleration of FM-index queries through prefix-free parsing
• Improved characters distance sampling for online and offline text searching
• Title not available (Why is that?)
• FM-index of alignment with gaps

Uses Software

• Soap
• IDBA-UD
• KMC
• GitHub

This page was built for publication: Efficient construction of a complete index for pan-genomics read alignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415261)