Lightweight LCP Construction for Next-Generation Sequencing Datasets

DOI10.1007/978-3-642-33122-0_26MaRDI QIDQ4916913zbMATH OpenOpenAlexFDO

Authors Markus J. Bauer, Anthony J. Cox, Giovanna Rosone, M. Sciortino

Publication date 26 April 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

BWTLCPmassive datasetsnext-generation sequencing datasetstext indexes

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32) Protein sequences, DNA sequences (92D20)

Abstract: The advent of "next-generation" DNA sequencing (NGS) technologies has meant that collections of hundreds of millions of DNA sequences are now commonplace in bioinformatics. Knowing the longest common prefix array (LCP) of such a collection would facilitate the rapid computation of maximal exact matches, shortest unique substrings and shortest absent words. CPU-efficient algorithms for computing the LCP of a string have been described in the literature, but require the presence in RAM of large data structures. This prevents such methods from being feasible for NGS datasets. In this paper we propose the first lightweight method that simultaneously computes, via sequential scans, the LCP and BWT of very large collections of sequences. Computational results on collections as large as 800 million 100-mers demonstrate that our algorithm scales to the vast sequence collections encountered in human whole genome sequencing experiments.

Recommendations

• Efficient construction of a compressed de Bruijn graph for pan-genome analysis
• Algorithms for next-generation sequencing data. Techniques, approaches, and applications
• Fast and Lightweight LCP-Array Construction Algorithms
• Low-dimensional representation of genomic sequences
• Next generation sequencing under de novo genome assembly

Cited in

(12)

• A survey of string orderings and their application to the Burrows-Wheeler transform
• Computing the multi-string BWT and LCP array in external memory
• Lightweight metagenomic classification via eBWT
• An external-memory algorithm for string graph construction
• Indeterminate string factorizations and degenerate text transformations
• Lightweight LCP construction for very large collections of strings
• Full-text indexes for high-throughput sequencing
• Better external memory LCP array construction
• Binary block order Rouen transform
• Burrows-Wheeler transform and LCP array construction in constant space
• Inducing suffix and LCP arrays in external memory
• LCP array construction in external memory

This page was built for publication: Lightweight LCP Construction for Next-Generation Sequencing Datasets

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