# Global optimal sequence alignment algorithms

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?

• I have no familiarity with these algorithms, or even the general problem, so could you provide links? – rcollyer Dec 7 '11 at 4:16
• @rcollyer: I'm guessing this, but it would have been nice if the OP was a bit more forthcoming... – J. M. Dec 7 '11 at 4:48
• @rcollyer Yes that is what I meant. Sorry I didn't provide the background – 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: