Latest
Open
RNA-Seq
ChIP-Seq
SNP
Assembly
Tutorials
Tools
Jobs
Forum
Planet
All »
Home
Log In
Question: Question related to time complexity of Needleman-Wunsch Algorithm
1
gravatar for shreya.verma808
5 months ago by
shreya.verma808 • 10
shreya.verma808 • 10 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 COMMENT • link •
modified 5 months ago by Rob ♦ 4.5k • written 5 months ago by shreya.verma808 • 10
3
gravatar for Rob
5 months ago by
Rob ♦ 4.5k
United States
Rob ♦ 4.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 COMMENT • link modified 5 months ago • written 5 months ago by Rob ♦ 4.5k
Please log in to add an answer.

Similar posts • Search »

Content
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