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 satisfying the triangle inequality". Such a matrix can be constructed along the lines in the comments above.
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.