RLBWT-Based LCP Computation in Compressed Space for Terabase-Scale Pangenome Analysis

Lossless full text indexes are utilized in a myriad of applications in bioinformatics. The continuously decreasing cost of generating biological data has resulted in the need to build full text indexes on biological datasets of increasing size. Many compressed full text indexes have been developed to address this problem. In particular, run-length Burrows-Wheeler transform (RLBWT) based compressed full text indexes have seen wide development and adoption. However, the construction of these RLBWT-based compressed full text indexes is still computationally expensive, sometimes prohibitively so, even for current dataset sizes. Therefore, we present algorithms for the construction of RLBWT-based compressed full text indexes and their supporting data structures in compressed space. The algorithms have a space complexity of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>r</mml:mi> <mml:mo>)</mml:mo></mml:math> words and run in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:math> time for repetitive datasets, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>r</mml:mi></mml:math> is the number of runs in the BWT, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> is the length of the text, and repetitive datasets implies the average run length is at least <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>log</mml:mi> <mml:mspace></mml:mspace> <mml:mi>n</mml:mi></mml:math> . We provide the first algorithm to compute LCP-related information for repetitive datasets in optimal time and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>r</mml:mi> <mml:mo>)</mml:mo></mml:math> space, greatly reducing memory requirements. The key idea behind this algorithm is the utilization of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>r</mml:mi></mml:math> samples of the inverse suffix array at regular intervals. For example, on the Human Pangenome Reference Consortium Release 2 dataset, this reduces peak memory from 2,135 GiB to 170 GiB (12.6x reduction) compared to the previous best method (pfp-thresholds).