BAliBASE is a benchmark database to evaluate the performance of software programs for multiple protein alignment [37]. The database consists of a large number of protein families with known 3D structure. These structures are used to define so-called core blocks for which 'biologically correct' alignments are known. There are two scoring systems to evaluate the accuracy of multiple alignments on BAliBASE protein families. The BAliBASE sum-of-pairs score measures the percentage of correctly aligned pairs of amino acid residues within the core blocks. By contrast, the column score measures the percentage of correctly aligned columns in the core blocks, see [38,10] for more details. These BAliBASE scoring functions are not to be confused with the objective functions used by different alignment algorithms.