title: A linear-time algorithm for predicting functional annotations from PPI networks.
abstract: Recent proteome-wide screening efforts have made available genome-wide, high-throughput protein-protein interaction (PPI) maps for several model organisms. This has enabled the systematic analysis of PPI networks, which has become one of the primary challenges for the systems biology community. Here, we address the problem of predicting the functional classes of proteins (i.e. GO annotations) based solely on the structure of the PPI network. We present a maximum likelihood formulation of the problem and the corresponding learning and inference algorithms. The time complexity of both algorithms is linear in the size of the PPI network, and our experimental results show that their accuracy in functional prediction outperforms current existing methods.
authors.affiliation: Department of Computer Science and Engineering, University of California Riverside, Riverside, CA 92521, USA. yonghui@cs.ucr.edu
authors.forename: Yonghui
authors.initials: Y
authors.lastname: Wu
authors.forename: Stefano
authors.initials: S
authors.lastname: Lonardi
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D029721:Drosophila Proteins / Q000378:metabolism; D016013:Likelihood Functions; D016014:Linear Models; D008390:Markov Chains; D015233:Models, Statistical; D025941:Protein Interaction Mapping / Q000706:statistics & numerical data*; D029701:Saccharomyces cerevisiae Proteins / Q000378:metabolism; D049490:Systems Biology
chemical_list: D029721:Drosophila Proteins; D029701:Saccharomyces cerevisiae Proteins