Question

What is the specific computational advantage of using the Burrows-Wheeler Transform (BWT) combined with an FM-index compared to a standard hash-table alignment method when mapping short reads to a reference genome?

Accepted Answer

The primary computational advantage of using the Burrows-Wheeler Transform combined with an FM-index is the dramatic reduction in memory usage compared to hash-table methods, which allows for mapping sequences to large genomes on standard consumer hardware. A hash-table index requires storing the reference genome plus additional data structures to map every k-mer, which are fixed-length substrings of the genome, to their positions; this leads to a memory footprint that scales linearly with the size of the genome and the number of k-mers. In contrast, the Burrows-Wheeler Transform is a reversible permutation of a string that groups similar characters together, creating a highly compressible representation of the reference genome. The FM-index is a compressed full-text substring index based on the BWT that allows for exact pattern matching without decompressing the data. Because the FM-index uses the properties of the suffix array and the BWT to search through the reference using backward search, it stores the index in a space proportional to the entropy of the genome rather than its absolute length. While hash-table methods offer faster lookups by trading memory for speed, the FM-index enables the entire human genome to fit into a few gigabytes of RAM, whereas a hash-table equivalent would require several times more memory, making the FM-index the standard for memory-efficient alignment.

Home → All Courses → Science and Mathematics Courses → Genomic Data Science → Flashcard

What is the specific computational advantage of using the Burrows-Wheeler Transform (BWT) combined with an FM-index compared to a standard hash-table alignment method when mapping short reads to a reference genome?

Community Answers