RLBWT-based LCP computation in compressed space for terabase-scale pangenome analysis.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Science

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 novel algorithms for constructing RLBWT-based compressed full-text indexes.
• To develop supporting data structures that operate 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 for computing 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 complexity and O(n) time for repetitive dataset index construction.
• Significantly reduced peak memory usage, e.g., from 2135 GiB to 170 GiB for the Human Pangenome Reference Consortium Release 2 dataset.
• Enabled efficient computation of LCP-related information, reducing memory requirements substantially.

Conclusions:

• The new algorithms offer a computationally efficient and memory-saving approach to building compressed full-text indexes.
• These advancements are critical for handling the growing scale of biological data.
• The implementation is publicly available, facilitating broader adoption in bioinformatics research.