Bioinformatics Advance Access originally published online on May 31, 2007
Bioinformatics 2007 23(16):2163-2173; doi:10.1093/bioinformatics/btm291
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Total ancestry measure: quantifying the similarity in tree-like classification, with genomic applications
1Department of Molecular Biophysics & Biochemistry, 2Department of Computer Science, 3Program in Computational Biology and Bioinformatics, 266 Whitney Avenue, Yale University, PO Box 208114, New Haven, CT 06520, 4Department of Genetics, Harvard University, 5Department of Cancer Biology, Dana-Farber Cancer Institute, 1 Jimmy Fund Way, Boston, MA 02115 and 6IBM Computational Biology Center, T.J. Watson Research Center, PO Box 704, Yorktown Heights, NY 10598
*To whom correspondence should be addressed.
 |
Abstract |
|---|
Motivation: Many classifications of protein function such as Gene Ontology (GO) are organized in directed acyclic graph (DAG) structures. In these classifications, the proteins are terminal leaf nodes; the categories ‘above’ them are functional annotations at various levels of specialization and the computation of a numerical measure of relatedness between two arbitrary proteins is an important proteomics problem. Moreover, analogous problems are important in other contexts in large-scale information organization—e.g. the Wikipedia online encyclopedia and the Yahoo and DMOZ web page classification schemes.
Results: Here we develop a simple probabilistic approach for computing this relatedness quantity, which we call the total ancestry method. Our measure is based on counting the number of leaf nodes that share exactly the same set of ‘higher up’ category nodes in comparison to the total number of classified pairs (i.e. the chance for the same total ancestry). We show such a measure is associated with a power-law distribution, allowing for the quick assessment of the statistical significance of shared functional annotations. We formally compare it with other quantitative functional similarity measures (such as, shortest path within a DAG, lowest common ancestor shared and Azuaje's information-theoretic similarity) and provide concrete metrics to assess differences. Finally, we provide a practical implementation for our total ancestry measure for GO and the MIPS functional catalog and give two applications of it in specific functional genomics contexts.
Availability: The implementations and results are available through our supplementary website at: http://gersteinlab.org/proj/funcsim
Contact: mark.gerstein{at}yale.edu
Supplementary information: Supplementary data are available at Bioinformatics online.
Associate Editor: Alex Bateman
The authors wish it to be known that, in their opinion, the first two authors should be regarded as joint First Authors.
Received on December 31, 2006; revised on May 2, 2007; accepted on May 22, 2007
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  H. Yu, P. Braun, M. A. Yildirim, I. Lemmens, K. Venkatesan, J. Sahalie, T. Hirozane-Kishikawa, F. Gebreab, N. Li, N. Simonis, et al. High-Quality Binary Protein Interaction Map of the Yeast Interactome Network Science, October 3, 2008; 322(5898): 104 - 110. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 I. V. Tetko, I. V. Rodchenkov, M. C. Walter, T. Rattei, and H.-W. Mewes Beyond the 'best' match: machine learning annotation of protein sequences by integration of different sources of information Bioinformatics, March 1, 2008; 24(5): 621 - 628. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Schlicker and M. Albrecht FunSimMat: a comprehensive functional similarity database Nucleic Acids Res., January 11, 2008; 36(suppl_1): D434 - D439. [Abstract] [Full Text] [PDF]
|
|