Proteins clustering. Proteins are clustered using an overall measure of similarity based on protein–protein interaction information. Clustering information is used to predict unknown protein functions. By definition, the best cluster maximizes the sum of the measures of similarity between adjacent proteins. Matrix ‘sij ‘ below provides the measure of similarities (expressed as a percentage) among 8 proteins.

‘sij ‘ = ®

100 20 30 29 24 22 38 45 20 100 10 22 0 15 31 0 30 10 100 14 11 95 30 41 29 22 14 100 20 27 28 50 24 0 11 20 100 24 55 0 22 15 95 27 24 100 26 37 38 31 30 28 55 26 100 40 45 0 41 50 0 37 40 100



(a) Define the distance matrix of the TSP.

(b) Determine an upper bound on the measure of similarity for the optimum protein cluster.