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?
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.
Login before adding your answer.
Use of this site constitutes acceptance of our User Agreement and Privacy