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?
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.