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

Area of Science:

• Bioinformatics
• Computational Biology
• Data Compression

Background:

• Lossless full-text indexes are crucial for bioinformatics applications.
• Increasing biological data necessitates efficient indexing of large datasets.
• Existing run-length Burrows-Wheeler transform (RLBWT) indexes are computationally expensive to construct.

Purpose of the Study:

• To present algorithms for constructing RLBWT-based compressed full-text indexes and supporting data structures in compressed space.
• To reduce the computational cost and memory requirements of building these indexes.

Main Methods:

• Developed algorithms with O(r) space complexity and O(n) time for repetitive datasets.
• Introduced the first algorithm to compute LCP-related information in O(r) space and optimal time.
• Utilized r samples of the inverse suffix array at regular intervals.

Main Results:

• Achieved O(r) space and O(n) time for constructing RLBWT indexes on repetitive datasets.
• Reduced peak memory usage by 12.6x on the Human Pangenome Reference Consortium Release 2 dataset (from 2,135 GiB to 170 GiB).
• Provided the first optimal time and O(r) space algorithm for LCP-related information.

Conclusions:

• The new algorithms offer significant memory reductions for building compressed full-text indexes.
• These advancements address the computational challenges of indexing large biological datasets.
• The implementation is publicly available, facilitating broader adoption in bioinformatics research.