3
$\begingroup$

As far as global optimal sequence alignment goes, is the Needleman-Wunsch and Hirschberg's algorithm still state of the art? Or have there been any improvements to these algorithms since they were published, or any newer algorithms?

$\endgroup$
4
  • 1
    $\begingroup$ I have no familiarity with these algorithms, or even the general problem, so could you provide links? $\endgroup$
    – rcollyer
    Dec 7, 2011 at 4:16
  • $\begingroup$ @rcollyer: I'm guessing this, but it would have been nice if the OP was a bit more forthcoming... $\endgroup$
    – J. M.
    Dec 7, 2011 at 4:48
  • $\begingroup$ @rcollyer Yes that is what I meant. Sorry I didn't provide the background $\endgroup$
    – flipchart
    Dec 7, 2011 at 6:46
  • $\begingroup$ @J.M. The author was referring the the following two algorithms: The Needleman–Wunsch Algorithm and Hirschberg's Algorithm $\endgroup$ Sep 19, 2022 at 17:43

1 Answer 1

6
$\begingroup$

According to Wing-Kin Sung's excellent "Algorithms in Bioinformatics" (2010, pp 30-39), the fastest algorithm was discovered in 1980 by Masek and Paterson and can solve the global alignment problem in $O(nm /\log(n))$ time, which is barely better than the Needleman-Wunsch algorithm:

W.J Masek and M.S. Paterson. 1980. "A faster algorithm computing string edit distances." Journal of Computer and System Sciences 20(1):18-31.

Sung's book has a short but well-written section on global alignment.

$\endgroup$
1
  • $\begingroup$ Thanks very much for the book link. It looks great! I'll definitely be reading that soon $\endgroup$
    – flipchart
    Dec 7, 2011 at 6:45

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.