| Graph theory is an important discipline that not only provides tools and methods for the study of graphs,but also has a wide range of applications in practice.It views graphs and networks as structures consisting of nodes and edges,and represents them in the form of matrices in mathematical terms.Common graph matrices include adjacency matrices,distance matrices and Laplacian matrices.These matrices reflect different properties of graphs and networks,such as the connectivity relationships between nodes,distances between nodes,etc.The eigenvalues and eigenvectors of these matrices can reveal the topology and algebraic properties of graphs and networks.Widely used in the fields of computers,social networks,biological networks and transportation networks,graph the-ory can help people better understand the nature and characteristics of networks,optimise network structures and improve network performance,thus providing a theoretical basis and a solution for practical applications.Proteins are among the most important molecules in living organisms and are es-sential for maintaining the life activities of cells.They are involved in a variety of bio-logical processes within the cell such as metabolism,signalling and structural support,thus maintaining the normal functioning of life activities.Depending on their importance to the organism,proteins can be divided into two categories:essential proteins and non-essential proteins.Of these,essential proteins play an integral role in the life activities of the cell.A essential proteins identification algorithm is proposed to improve the identifi-cation accuracy in protein-protein interaction（PPI）networks,using distance matrix and graph theory.The main research work of this paper is as follows:（1）Some bounds on the radius of the generalized distance spectrum of then-order connected graphand its second largest eigenvalue are obtained.Based on the relation-ship between the eigenvalues and eigenvectors of the matrix,first,we find a lower bound for1based on the distance and transmission;after that,we find an upper bound and a lower bound for1based on the maximum（minimum）transmission and the distance spectral radius1;finally,we find a lower bound for2based on the ordernand the diameter(9.（2）Based on the definition of self-complementary graph,the generalized distance spectrum of the self-complementary graph composed ofn-order-regular graphs is cal-culated,and the distance（signless）Laplacian spectrum is obtained by combining the rela-tionship between the generalized distance spectrum and the distance（signless）Laplacian spectrum.（3）Combining the distance matrix,the interaction of topological information and biological information between the 1st,2nd,3rd and 4th order distances of proteins were considered respectively,and a random walks method was used to integrate the appealing two kinds of interaction information,and a four-order distances-based algorithm DSEP for essential proteins identification was proposed,which overcame the problem of in-sufficient accuracy in identifying essential proteins by considering only the first order neighbours in the existing algorithms.By comparing the analysis with 11 classical algo-rithms for identifying essential proteins in three PPI networks,it can be seen that DSEP has better performance in identifying essential proteins.In addition,a method to calcu-late finite-order distances is proposed by combining the knowledge about distances in graph theory,which can greatly reduce the time complexity of DSEP. |
