Fast Graph-based Algorithms for Analyzing Protein-Protein Interaction Networks - Shen, Yue. (Tufts University. Tisch Library., 2019)
Protein-protein interaction (PPI) networks represent contacts between proteins in the cell. Some proteins in the networks are missing labels that describe their functions. In practice, we look at their 'neighborhood' and predict their functions based on the information from 'neighbors'. To find appropriate neighbors, [11] gives a new metric, the diffusion state distance (DSD), to capture neighbors and do function prediction. [22] introduces an effective method to compute DSD efficiently by using the unsmoothed aggregation algebraic multigrid method combining with random projection. This thesis focuses on two parts. First, based on the numerical results in [22] and our experiments, PPI networks seem to be 'well-conditioned'. Therefore, to show this observation, we introduce lower bounds for the first nonzero eigenvalue and the condition number of the normalized Laplacian of a weighted graph based on the diameter and the maximal average degree of the network. Second, based on the work in [11] and [22], we develop an efficient method to construct a k-nearest- neighbor (kNN) graph in DSD metric to predict functions. Our method is based on random walk combining with random projection, and the computational cost is O(nlogn). We use majority voting to predict functions, and the numerical results show that the performance of the approximate kNN computed by our method and the performance of the exact kNN are similar. In the future, we will improve the quality of the approximate kNN graph built by our method and try different ways to combine multiple random projections. In addition, the numerical result shows that the lower bound for the smallest nonzero eigenvalue of the normalized Laplacian is not tight, and we hope to get a better bound.; Thesis (M.S.)--Tufts University, 2019.; Submitted to the Dept. of Mathematics.; Advisor: Xiaozhe Hu.; Committee: Lenore Cowen, and James Murphy.; Keyword: Applied mathematics.