Question: Question related to time complexity of Needleman-Wunsch Algorithm
1
gravatar for shreya.verma808
5 months ago by
shreya.verma80810 wrote:

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 • 296 views
ADD COMMENTlink modified 5 months ago by Rob4.5k • written 5 months ago by shreya.verma80810
3
gravatar for Rob
5 months ago by
Rob4.5k
United States
Rob4.5k wrote:

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 COMMENTlink modified 5 months ago • written 5 months ago by Rob4.5k
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1247 users visited in the last hour