EDIT: I naively thought similarity matrix == dissimilarity matrix, this isn't the case. It's been too long since I did bioinformatics. My answer below should properly say "dissimilarity matrix".

A similarity matrix is just a metric on a finite space. The standard metric on the space of all finite metric spaces is the [Gromov-Hausdorff metric][1].



  [1]: http://en.wikipedia.org/wiki/Gromov-Hausdorff_convergence#Gromov-Hausdorff_distance