We show that the Longest Common Prefix Array of a text collection of total size n on alphabet [1, σ] can be computed from the Burrows-Wheeler transformed collection in O(n log σ) time using o(n log σ) bits of working space on top of the input and output. Our result improves (on small alphabets) and generalizes (to string collections) the previous solution from Beller et al., which required O(n) bits of extra working space. We also show how to merge the BWTs of two collections of total size n within the same time and space bounds. The procedure at the core of our algorithms can be used to enumerate suffix tree intervals in succinct space from the BWT, which is of independent interest. An engineered implementation of our first algorithm on DNA alphabet induces the LCP of a large (16 GiB) collection of short (100 bases) reads at a rate of 2.92 megabases per second using in total 1.5 Bytes per base in RAM. Our second algorithm merges the BWTs of two short-reads collections of 8 GiB each at a rate of 1.7 megabases per second and uses 0.625 Bytes per base in RAM. An extension of this algorithm that computes also the LCP array of the merged collection processes the data at a rate of 1.48 megabases per second and uses 1.625 Bytes per base in RAM.

Space-efficient computation of the LCP array from the Burrows-Wheeler transform / Prezza, N.; Rosone, G.. - 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, Leibniz International Proceedings in Informatics, LIPIcs, (2019), pp. 1-18. (30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, Pisa, Italia, June 18-20, 2019). [10.4230/LIPIcs.CPM.2019.7].

Space-efficient computation of the LCP array from the Burrows-Wheeler transform

Prezza N.;
2019

Abstract

We show that the Longest Common Prefix Array of a text collection of total size n on alphabet [1, σ] can be computed from the Burrows-Wheeler transformed collection in O(n log σ) time using o(n log σ) bits of working space on top of the input and output. Our result improves (on small alphabets) and generalizes (to string collections) the previous solution from Beller et al., which required O(n) bits of extra working space. We also show how to merge the BWTs of two collections of total size n within the same time and space bounds. The procedure at the core of our algorithms can be used to enumerate suffix tree intervals in succinct space from the BWT, which is of independent interest. An engineered implementation of our first algorithm on DNA alphabet induces the LCP of a large (16 GiB) collection of short (100 bases) reads at a rate of 2.92 megabases per second using in total 1.5 Bytes per base in RAM. Our second algorithm merges the BWTs of two short-reads collections of 8 GiB each at a rate of 1.7 megabases per second and uses 0.625 Bytes per base in RAM. An extension of this algorithm that computes also the LCP array of the merged collection processes the data at a rate of 1.48 megabases per second and uses 1.625 Bytes per base in RAM.
978-3-95977-103-0
Burrows-Wheeler Transform; DNA reads; LCP array
File in questo prodotto:
File Dimensione Formato  
PrezzaRosone_CPM2019.pdf

Open Access

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 600.44 kB
Formato Adobe PDF
600.44 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/194135
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact