Hi Ines,
No, less memory != fast search. Not necessarily. (If the difference in footprint allows the problem to fit into a faster memory, then yes, less memory == fast search.) In this case, the BWT technique offers a combination of small memory footprint (far smaller than suffix arrays, suffix trees, and smaller than hash tables when the tables are built over the reference genome), and good performance. People often ask why BWT is faster than hash tables in certain situations, and it's hard to answer because so much depends on exactly what hash-based tool you're comparing against and what the reads and alignment policy look like. I suspect it chiefly comes down to minimizing cache misses and minimizing wasted work.
Thanks,
Ben
No, less memory != fast search. Not necessarily. (If the difference in footprint allows the problem to fit into a faster memory, then yes, less memory == fast search.) In this case, the BWT technique offers a combination of small memory footprint (far smaller than suffix arrays, suffix trees, and smaller than hash tables when the tables are built over the reference genome), and good performance. People often ask why BWT is faster than hash tables in certain situations, and it's hard to answer because so much depends on exactly what hash-based tool you're comparing against and what the reads and alignment policy look like. I suspect it chiefly comes down to minimizing cache misses and minimizing wasted work.
Thanks,
Ben
Comment