External memory BWT and LCP computation for sequence collections with applications.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• Sequencing technologies generate massive biosequence data requiring efficient storage and search.
• Compressed indices, often based on the Burrows-Wheeler Transform (BWT) and longest common prefix (LCP) array, are crucial for handling large datasets.
• Building these data structures in external memory while optimizing RAM usage is a significant computational challenge.

Purpose of the Study:

• To develop a space-efficient algorithm for computing the BWT and LCP array in external or semi-external memory settings.
• To enable faster processing of large biosequence collections by optimizing memory usage.
• To provide a foundation for efficient external memory algorithms for key bioinformatics problems.

Main Methods:

• A novel algorithm that splits large collections into smaller, manageable subcollections for in-RAM BWT computation.
• External or semi-external memory merging of partial BWTs to compute the full BWT and LCP array.
• Modification of the algorithm to generate auxiliary arrays for additional bioinformatics applications.

Main Results:

• The proposed algorithm efficiently computes the BWT and LCP array in external memory settings.
• It can be extended to solve problems like maximal repeat computation, all-pairs suffix-prefix overlaps, and succinct de Bruijn graph construction.
• Performance analysis shows the algorithm is competitive with state-of-the-art methods, offering significant speedups (up to 40x) for large datasets or ample RAM.

Conclusions:

• The algorithm achieves optimal sequential I/O complexity, proving its efficiency for large-scale data.
• Experimental results validate its practical performance, outperforming existing methods for longer sequences or sufficient RAM.
• This work offers a scalable solution for processing and analyzing massive biosequence data in bioinformatics.