Question

When mapping NGS reads to a reference genome, what is the primary computational advantage of using the Burrows-Wheeler Transform over a standard suffix tree approach?

Accepted Answer

The primary computational advantage of using the Burrows-Wheeler Transform over a suffix tree is a massive reduction in memory consumption. A suffix tree is a data structure that indexes every possible suffix of a reference genome to allow for rapid pattern matching, but it requires roughly 20 to 50 bytes of memory per character of the genome, which becomes prohibitively large for human-sized genomes. The Burrows-Wheeler Transform is a reversible permutation of a string that reorganizes the genome&#x27;s characters into a format that, when combined with an auxiliary data structure called the FM-index, allows for efficient sequence alignment while requiring significantly less space, typically closer to 0.5 to 1 byte per character. By representing the genome in this compressed form, the Burrows-Wheeler Transform allows aligners to store the entire reference genome and its index in the random access memory of a standard computer, whereas a suffix tree would often exceed available physical memory. This space efficiency is achieved without sacrificing the ability to perform fast searches, as the Burrows-Wheeler Transform maintains the mathematical properties necessary to perform exact and approximate string matching at speeds comparable to tree-based approaches.

Home → All Courses → Science and Mathematics Courses → Computational Biology → Flashcard

When mapping NGS reads to a reference genome, what is the primary computational advantage of using the Burrows-Wheeler Transform over a standard suffix tree approach?