2
$\begingroup$

I recently read that original the Smith-Waterman algorithm to do a local pairwise alignment of sequences has a complexity of $O(m^2 \times n)$, where $m$ and $n$ would be the lengths of the sequences with $m$ the potentially longer one. What I am wondering is where the additional complexity arises in the algorithm compared to the Needelmann-Wunsch algorithm of global alignment, which has complexity $O(m \times n)$.

Am I correct to assume the $m\times n$ for the Needelmann-Wunsch algorithm comes from building up the scoring matrix - whereas the traceback is negligible in complexity i.e. $O(m\times n + m)$? Hence we arrive at $O(m\times n)$.

Why is there a $m^2$ term for the Smith-Watermann algorithm?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I think your source is wrong. You are correct to assume the brunt of its complexity comes from building the $m *n$ matrix. The main differences are in the calculations per cell and the traceback, but these don't make $m ^2$. Wikipedia also gives an identical $O(m * n)$ as worst case for both algorithms.

edit: Aparently in this paper the algorithms were improved to go from $m^2n$ to $m*n$

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Yes, the Smith-Waterman algorithm is often called the Smith-Waterman-Gotoh algorithm for this reason. $\endgroup$
    – user172818
    Oct 10, 2022 at 0:13
  • $\begingroup$ Thank you for the great reference. I gave it a read. So under certain gap penalties, the complexity is reduced. I don't yet fully understand why though. Is there a heuristic explanation? $\endgroup$
    – Gordon J. Köhn
    Oct 21, 2022 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.