Question related to time complexity of Needleman-Wunsch Algorithm
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?
• 4,852 views
•
link
updated
by
Rob
•
written
by
shreya.verma808 •
•
written
by
shreya.verma808 •
1 answer
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.
Log in to answer this question.
More posts like this
-
KMP algorithm's time complexity
written by jessewhite8077 •
-
Force Biopython's Bio.Align to use Smith-Waterman algorithm
written by sean.cascarina •
-
Question about the sped of the global pairwise alignment of Bio.pairwise.align.globalms and Align.P…
written by master_zhen •
-
Equivalent of Waterman-Eggert Algorithm
written by trinityduke100 •
-
protein K-mer connection
written by kartik.aier.gta •
-
Approach to sequence alignment for long strings
written by dustin.farkas.yo •
-
How Can I perform a multiple alignment with characters?
written by cristialf •
-
objective function of the needleman-wunsch algorithm
written by lait
-
Runtime Needleman-Wunsch & Gotoh
written by sarah-spie •
-
New To Bioinformatics, What Is A 6-Mer When It Comes To Alignment Algorithms (And When Do I Choose …
written by Matt •
