Question about Four Russians speed up for block alignment and longest common subsequence.
0
0
Entering edit mode
6 days ago

I'm trying to make sense of the notes for my course.

It starts with block alignment.

He sets the block size to (log(n))/4 and shows that (with ATCG) we have lookup table size of 4^t * 4^t = n.

Then it is claimed that we can therefore build the lookup table in O(n). How can we build a lookup table of size n in O(n) unless we can compute alignments in constant time?

Then it states that we have (n/t)^2 blocks which is n^2 / (log n)^2. This value is then multiplied by the log(n) that it takes for each access to the table. Why does it take anything other than constant time to access a lookup table? Isn't the whole point of building a lookup table that you can access it in constant time?

This is then expanded to cover the LCS case but with the same arguments as above (building a table of size n^(3/2) in O(n^(3/2)) time, and taking log n for each look up).

Sequence_Alignment • 70 views
ADD COMMENT

Login before adding your answer.

Traffic: 2970 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6