This is a test version of Biostars. For the public version, visit https://www.biostars.org.
Computational Complexity Of Creating A Dotplot

hi could someone please tell me what is the computational complexity of creating a dotplot ?

• 2,706 views • link
updated by Fabian Bull Fabian Bull • written by User 5037 • User 5037

2 answers

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.

• 0 views • link
written by Farhat Farhat

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.

• 0 views • link
written by Fabian Bull Fabian Bull

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 .

• 0 views • link
written by Raygozak Raygozak

Long time ago: A very wise man stated that a linear algorithm for LCS would be impossible yet it exists.

• 0 views • link
written by Fabian Bull Fabian Bull

Log in to answer this question.

More posts like this