Question related to time complexity of Needleman-Wunsch Algorithm
1
1
Entering edit mode
4.4 years ago

The time complexity of Needleman-Wunsch algorithm is O(m*n) for pairwise sequence alignment with one sequence of length m and another sequence of length n.For three sequence alignment with lenght m,n,k respectively then what is the time complexity?

alignment • 3.8k views
ADD COMMENT
3
Entering edit mode
4.4 years ago
Rob 6.9k

It is O(mnk), and for each new sequence, there is a multiplicative factor of the new sequence's length. This is why MSA is intractable in the general case to solve optimally. See e.g. https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/msa.pdf.

ADD COMMENT

Login before adding your answer.

Traffic: 733 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