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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ I have no familiarity with these algorithms, or even the general problem, so could you provide links? $\endgroup$– rcollyerDec 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$– flipchartDec 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$– Samuel MuldoonSep 19, 2022 at 17:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Thanks very much for the book link. It looks great! I'll definitely be reading that soon $\endgroup$ Dec 7, 2011 at 6:45