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?

  • 1
    $\begingroup$ I have no familiarity with these algorithms, or even the general problem, so could you provide links? $\endgroup$ – rcollyer Dec 7 '11 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 '11 at 4:48
  • $\begingroup$ @rcollyer Yes that is what I meant. Sorry I didn't provide the background $\endgroup$ – flipchart Dec 7 '11 at 6:46

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.

| cite | improve this answer | |
  • $\begingroup$ Thanks very much for the book link. It looks great! I'll definitely be reading that soon $\endgroup$ – flipchart Dec 7 '11 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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