A survey of BWT variants for string collections

Area of Science:

• Bioinformatics
• Computational Biology
• String Processing

Background:

• Bioinformatics research increasingly focuses on sequence collections, not individual sequences.
• The Burrows-Wheeler Transform (BWT) is fundamental for string processing, with many tools developed for sequence collections.
• Existing BWT tools often compute non-equivalent variants, leading to significant differences in output and parameters like the number of runs.

Purpose of the Study:

• To investigate and compare different Burrows-Wheeler Transform (BWT) variants used in bioinformatics tools for string collections.
• To highlight the discrepancies between BWT variants and their impact on key parameters.
• To assess the influence of input data order on BWT computation.

Main Methods:

• Studied 18 dedicated tools for computing the BWT of string collections.
• Identified and categorized 6 distinct BWT variants.
• Performed theoretical and practical comparisons of BWT variants on 8 real-life biological datasets.
• Analyzed variations in the number of runs (r) across different BWT variants.

Main Results:

• Identified 6 different BWT variants among 18 studied tools.
• Demonstrated significant differences between BWT variants, particularly on collections of many similar short sequences.
• Observed substantial variation in the number of runs (r), with multiplicative factors up to 4.2.
• Found that some BWT variants are sensitive to the input order of the sequence collection.

Conclusions:

• The choice of BWT variant significantly impacts the analysis of sequence collections.
• Discrepancies among BWT tools can lead to non-comparable results and affect downstream analyses.
• Standardization or clear documentation of BWT variants is crucial for reproducible bioinformatics research.