FM Index

[@LintonF1]

Thank you so much for your incredibly clear lectures. I have taken a couple of classes that discussed the BWT and FM index superficially, but you've made it so much easier to understand. Thank you thank you!

[@xruan6582]

Thank you for this clear and concise, and by far the best BW tutorial

[@hariprasadyalla]

Very nice explanation. Both the lectures on BWT and FM Index are very nicely explained.

[@wilfredolugo5157]

Thank you very much. These have been excellent videos. They helped me understand in detailed your Bowtie tool/algorithm.

[@BlopFreeze]

There is an alternative to this method using wavelet tree datastructure for rank-queries (your Tally). Also, you dont need F.

[@MightyPuff]

Could you provide further information on how F is not necessary please?

[@erascarecrow2541]

@MightyPuff Because you can reconstruct it easily. Also if you count the totals of characters in L, you can get F without more than 1 int per character.

[@nakulsuresh6476]

How do you create the partially stored suffix array?

[@zorankristoo]

Very good explanation. Thanks

[@syamcr]

Beautifully explained. I have a question regarding look-up using a partial suffix array. At 31:58 you said we need to store SA values at constant positions apart in 'T' to have O(1) lookups. But what if we just store every Nth element of the SA without bothering about T? This would be much easier to implement. Is there an upper bound for the number of lookups needed as a function of N?

[@wimthiels638]

great ! finally got it. thanks ben

[@antoneliseev372]

Sorry but you are wrong telling that we have linear space for storing tally matrix when we use spaced checkpoints. Lets suppose we hawe n-th length string and we store every thirtieth element of matrix by this way we store [n/30] elements and it's still O(n). Of course you able to store just 30 elements of whole tally matrix but then we got O(n) for each lookup.

[@antoneliseev372]

may by it's just a typo on this (24:55) slide

[@udbharat_official]

what is 2step FM index ?

[@rzipper1716]

Thank you. Very Helpful

[@Gowthamsrinivasan]

Neatly explained :)

[@Paradisekid999]

Great lecture thank you very much!

[@avis9ditiu]

if build FM index for DNA, how do I get the Last column, use the raw method would be unrealistic, it seems to need 3G size sequence of 3G to sorting..

[@luissoto4525]

That's an interesting question. The short answer is that they use the suffix array, but from block to block. It means, his method builds the suffix array and the BWT block-by-block and in tandem, discarding suffix array blocks once the corresponding BWT block has been built. By setting a small block size relative to the length of the genome, the technique achieves a very small memory footprint. The blockwise method also enables the user to trade flexibly between speed and peak memory usage by adjusting block size and other parameters. If you're interested to learn more about that, u should read this paper www.cs.helsinki.fi/u/tpkarkka/publications/tcs07-revised.pdf

[@luoyonggang]

In time 23:50, the rank of b should be 437

[@Daoro123]

Yonggang Luo Nope, remember he asked for the rank and his ranking begins in Zero. So the first B you see actually is B0 and the hundrendth B would be B99

[@TommyCarstensen]

The tally is 437, but the rank is 436.

[@erascarecrow2541]

Yeah that threw me off too.