title: Predicting protein function via downward random walks on a gene ontology.
abstract: BACKGROUND
  High-throughput bio-techniques accumulate ever-increasing amount of genomic and proteomic data. These data are far from being functionally characterized, despite the advances in gene (or gene's product proteins) functional annotations. Due to experimental techniques and to the research bias in biology, the regularly updated functional annotation databases, i.e., the Gene Ontology (GO), are far from being complete. Given the importance of protein functions for biological studies and drug design, proteins should be more comprehensively and precisely annotated.
  
  
  RESULTS
  We proposed downward Random Walks (dRW) to predict missing (or new) functions of partially annotated proteins. Particularly, we apply downward random walks with restart on the GO directed acyclic graph, along with the available functions of a protein, to estimate the probability of missing functions. To further boost the prediction accuracy, we extend dRW to dRW-kNN. dRW-kNN computes the semantic similarity between proteins based on the functional annotations of proteins; it then predicts functions based on the functions estimated by dRW, together with the functions associated with the k nearest proteins. Our proposed models can predict two kinds of missing functions: (i) the ones that are missing for a protein but associated with other proteins of interest; (ii) the ones that are not available for any protein of interest, but exist in the GO hierarchy. Experimental results on the proteins of Yeast and Human show that dRW and dRW-kNN can replenish functions more accurately than other related approaches, especially for sparse functions associated with no more than 10 proteins.
  
  
  CONCLUSIONS
  The empirical study shows that the semantic similarity between GO terms and the ontology hierarchy play important roles in predicting protein function. The proposed dRW and dRW-kNN can serve as tools for replenishing functions of partially annotated proteins.
authors: College of Computer and Information Sciences, Southwest University, Beibei, Chongqing, China. gxyu@swu.edu.cn.|Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, China. gxyu@swu.edu.cn.
authors: Guoxian
authors: G
authors: Yu
authors: Department of Computer Science, Hong Kong Baptist University, Hong Kong, Hong Kong. hlzhu@comp.hkbu.edu.hk.
authors: Hailong
authors: H
authors: Zhu
authors: Department of Computer Science, George Mason University, Fairfax, VA, USA. carlotta@cs.gmu.edu.
authors: Carlotta
authors: C
authors: Domeniconi
authors: Department of Computer Science, Hong Kong Baptist University, Hong Kong, Hong Kong. jiming@comp.hkbu.edu.hk.
authors: Jiming
authors: J
authors: Liu
mesh_terms: D000465:Algorithms; D063990:Gene Ontology; D006801:Humans; D058977:Molecular Sequence Annotation; D011506:Proteins / Q000737:chemistry / Q000378:metabolism*; D040901:Proteomics / Q000379:methods*; D015003:Yeasts / Q000378:metabolism
chemical_list: D011506:Proteins