Using bipartite matching in graph spectra for protein structural similarity

The graph spectrum of a graph is a sequence of eigenvalues of its Laplacian matrix. It quantitatively provides some graph information, e.g., structure, topology, and connectivity, and is extensively used in the field of structural comparison. In this paper, by adopting the concept of minimum weight maximal bipartite matching, we improve the distance measuring on protein graph spectra. In the analysis of protein subunit matching problem, corroborating protein databases CATH, SCOP, and RCSB PDB, results suggest that when proposed method is applied, a similar single polypeptide chain can be identified in MHC (the Major Histocompatibility Complex) protein complexes. In addition, the proposed method outperforms than typical geometric metric distance. This graph-theoretic approach offers a practical direction for protein subunit comparison.