An important problem in genomics is the study of evolutionary relatedness of proteins. We use our algorithms to cluster proteins to homologous groups given pairwise similarities of their amino-acid sequences. Such similarities are computed by the sequence alignment tool BLAST [12]. We follow the approach of Paccanaro et al. [13] and Nepusz et al. [14], and compare the computed clustering against a ground truth given by SCOP, a manually crafted taxonomy of proteins [15]. The SCOP taxonomy is a tree with proteins at the leaf nodes. The ground truth clusters used in the experiments are subsets of the leafs, that is, proteins, rooted at different SCOP superfamilies. These are nodes on the 3rd level below the root.