Advanced Data Structures: Inverting the BWT

[arpitmathur]

superb explanation. Just started my masters in Computational biology. Thanks

[RLLLx]

This is impressive! How do people come up with this kind of algorithm?!

[Cat-cthn]

Thank you very much for your video! I'm taking a bioinformatics course and this is the clearest explanation I've come across so far, excellent material.

[sabana]

Excellent, and super interesting why this works.

[YaBoiMoustafa]

I’m studying for a bioinformatics exam and reversing the BWT is almost guaranteed to be on the final. I was scared of the question but this video made it super simple. I’m hoping this actually works with any string because if it does then that’s amazing!!!! Thank you

[niemasd]

Someone had asked how we can possibly sort the Last column in linear time to get the First column, but I can't seem to find the comment anymore. Here's the explanation:

All you need to do is keep track of the counts of each letter in your alphabet, which you can do in linear time. Here's a Python implementation, which would be O(n + length of alphabet), and given that n >> "length of alphabet" (not in this simple example, but in reality), it reduces to O(n):


Note that ord(c) converts a character to its ASCII integer, and chr(i) converts an ASCII integer to the corresponding character. Here's a link that lets you step through this code in the browser:

[amy-cvnw]

Thank you so much for the simple explanation, this was so helpful!

[kaneki.ken.]

thank you so much, you're the goat

[julianbiju]

Question:

Thank you for making this video, it really has helped!
A quick question: As you have subscripted the numbers, we can identify that B_1 is followed by A_3. However, programmatically, the burrows-wheeler encoding given to us will not have these subscripts(I.e. perhaps we receive an encoding where we can't distinguish between any of the duplicate characters). Given your example, assuming we observe the first column corresponding to B_1 we see A_3, we will in reality have no idea whether that is A_1, A_2, or A_3. How do we reconcile this in our code?

[Xn_Fdez]

Gracias por el video máquina! Muy buena explicación.

[mlemImlem]

very good explanation thank you for teaching this

[nottofind]

What is the DOI of the original Burrows Wheeler Transformation Paper? I can't find it :/
Great explanation though!