Prefix-free parsing for building big BWTs

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• High-throughput sequencing generates massive genomic data, necessitating efficient indexing methods.
• Constructing indexes for large genomic databases is computationally challenging.
• Genomic data's repetitive nature can be leveraged for index construction.

Purpose of the Study:

• Introduce a novel preprocessing algorithm, prefix-free parsing, for efficient Burrows-Wheeler Transform (BWT) computation.
• Develop a method to construct BWT from a dictionary and parse, reducing memory requirements.
• Demonstrate the practical applicability of prefix-free parsing for large-scale genomic indexing.

Main Methods:

• Developed a one-pass prefix-free parsing algorithm to generate a dictionary (D) and a parse (P) from input text (T).
• The BWT of T can be constructed from D and P using limited workspace and linear time.
• Experimental evaluation on human chromosome 19 and complete human genomes.

Main Results:

• Prefix-free parsing generates a dictionary and parse significantly smaller than the original text.
• Enabled building a 131-MB run-length compressed FM-index for 1000 copies of human chromosome 19 in 2 hours using 21 GB memory.
• Projected ability to build a 6.73 GB index for 1000 human haplotypes in ~102 hours using ~1 TB memory.

Conclusions:

• Prefix-free parsing is a practical and memory-efficient approach for indexing large, repetitive genomic data.
• The method facilitates the construction of compressed FM-indexes for massive genomic datasets.
• This technique addresses the challenges posed by the exponential growth of genomic databases.