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"matrixsatisfyingthetriangleinequality".Suchamatrixcanbeconstructedalongthelinesinthecommentsabove.
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.