Fast Graph-based Algorithms for Analyzing Protein-Protein Interaction Networks
Shen, Yue.
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 ... read moreneighbors 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.read less - ID:
- ks65hr16h
- To Cite:
- TARC Citation Guide EndNote
