Multiple sequence alignment is a crucial prerequisite for biological sequence data analysis, and a large number of multi-alignment programs have been developed during the last twenty years. Standard methods for multiple DNA or protein alignment are, for example, CLUSTAL W [1], DIALIGN [2] and T-COFFEE [3]; an overview about these tools and other established methods is given in [4]. Recently, some new alignment approaches have been developed such as POA [5], MUSCLE [6] or PROBCONS [7]. These programs are often superior to previously developed methods in terms of alignment quality and computational costs. The performance of multi-alignment tools has been studied extensively using various sets of real and simulated benchmark data [8-10].