Entering edit mode
13.0 years ago
User 5037
▴
290
hi could someone please tell me what is the computational complexity of creating a dotplot ?
3
Entering edit mode
13.0 years ago
Farhat
★
2.9k
It will be quadratic in the length of the sequence. You are comparing every base to every other base. There are n(n-1)/2 comparisons to be made.
2
Entering edit mode
13.0 years ago
Fabian Bull
★
1.3k
The naive way is quadratic in the length of both length:
O(m * n)
where m is the length of sequence 1 and n is the length of sequence 2.
I would not be suprised if there is a fancy datastructure which could do the job in linear time.
Similar Posts
Loading Similar Posts
Traffic: 1498 users visited in the last hour
Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by the
version 2.3.6
version 2.3.6
You can't escape comparing nucleotide of one sequence against all of the other in order to find interesting changes occurring between the two genomes/chromosomes .
Long time ago: A very wise man stated that a linear algorithm for LCS would be impossible yet it exists.