Total ancestry measure: quantifying the similarity in tree-like classification, with genomic applications
Authors:
Open Access
- 31 May 2007
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 23 (16) , 2163-2173
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@yale.edu Supplementary information: Supplementary data are available at Bioinformatics online.Keywords
This publication has 27 references indexed in Scilit:
- MIPS: analysis and annotation of proteins from whole genomes in 2005Nucleic Acids Research, 2006
- Prediction of yeast protein-protein interaction network: insights from the Gene Ontology and annotationsNucleic Acids Research, 2006
- The FunCat, a functional annotation scheme for systematic classification of proteins from whole genomesNucleic Acids Research, 2004
- Toward a systematic definition of protein function that scales to the genome level: defining function in terms of interactionsProceedings of the IEEE, 2002
- Complex transcriptional circuitry at the G1/S transition in Saccharomyces cerevisiaeGenes & Development, 2002
- Systematic Learning of Gene Functional Classes From DNA Array Expression Data by Using Multilayer PerceptronsGenome Research, 2002
- Transcriptional Regulatory Networks in Saccharomyces cerevisiaeScience, 2002
- The Hsp70-Ydj1 Molecular Chaperone Represses the Activity of the Heme Activator Protein Hap1 in the Absence of HemeMolecular and Cellular Biology, 2001
- Assessing annotation transfer for genomics: quantifying the relations between protein sequence, structure and function through traditional and probabilistic scoresJournal of Molecular Biology, 2000
- A Novel Mechanism for Regulating Activity of a Transcription Factor That Controls the Unfolded Protein ResponseCell, 1996