I am trying some large-scale viral phylogenies with 1000s of gene DNA sequences, each almost 2Kb in length, using a parallel version of ClustalW coded for an SMP machine.
I don't have access to a large cluster, but on a 16-core machine I'm using I found that most of the processing time is not actually the pairwise alignment - it's in the tree building, where only one CPU is being used.
One of the runs with ~10K sequences failed to complete even after a couple of months - had to reboot, but only because of some power test. Go Linux!
Any suggestions as to alternatives that accelerate the tree generation?