2012/01/01 by Markus Bauer, Markus J. Bauer, Anthony J. Cox +2 · 43 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Biology #Computation #Computer science #DNA #DNA and Biological Computing #DNA sequencing #Data structure #Genetics #Genomics and Phylogenetic Studies #Mathematics #Parallel computing #Prefix #Programming language #Sequence (biology) #String (physics) #String searching algorithm #Substring #Theoretical computer science #Trie #cs.DS #k-mer #q-bio.GN
paper · pdf · doi:10.1007/978-3-642-33122-0_26
published in Lecture notes in computer science, 326-337 (Springer Science+Business Media) · Springer LNCS (Lecture Notes in Computer Science) should be considered as the original place of publication, please cite accordingly. The final version of this manuscript is available at http://link.springer.com/chapter/10.1007/978-3-642-33122-0_26
openalex publication_date 2012/01/01 · arxiv created 2013/05/01 · arxiv updated 2013/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.