Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für molekulare Genetik     Collection: Department of Computational Molecular Biology     Display Documents



  history
ID: 447551.0, MPI für molekulare Genetik / Department of Computational Molecular Biology
Exact Score Distribution Computation for Similarity Searches in Ontologies.
Authors:Schulz, Marcel H.; Köhler, Sebastian; Bauer, Sebastian; Vingron, Martin; Robinson, Peter N.
Language:English
Research Context:9th International Workshop, WABI 2009, Philadelphia, USA, September 12-13, 2009.
Place of Publication:New York [et al]
Publisher:Springer
Date of Publication (YYYY-MM-DD):2009-09-19
Title of Book:Algorithms in Bioinformatics
Start Page:298
End Page:309
Physical Description:430
Full Name of Book-Editor(s):Salzberg, Steven L.; Warnow, Tandy
Title of Series:Lecture Notes in Computer Science
Volume:5724
Full Name(s) of Series Editor(s):Hofmann, Alfred
Copyright:Springer. Part of Springer Science+Business Media
Review Status:not specified
Audience:Experts Only
Abstract / Description:Semantic similarity searches in ontologies are an important component of many bioinformatic algorithms, e.g., protein function prediction with the Gene Ontology. In this paper we consider the exact computation of score distributions for similarity searches in ontologies, and introduce a simple null hypothesis which can be used to compute a P-value for the statistical significance of similarity scores. We concentrate on measures based on Resnik’s definition of ontological similarity. A new algorithm is proposed that collapses subgraphs of the ontology graph and thereby allows fast score distribution computation. The new algorithm is several orders of magnitude faster than the naive approach, as we demonstrate by computing score distributions for similarity searches in the Human Phenotype Ontology.
Classification/Thesaurus:Computer science
External Publication Status:published
Document Type:InBook
Communicated by:Martin Vingron
Affiliations:MPI für molekulare Genetik
External Affiliations:1.International Max Planck Research School for Computational Biology and, Scientific Computing, Berlin, Germany;
2.Institute for Medical Genetics, Charité-Universitätsmedizin Berlin, Augustenburger Platz 1, 13353 Berlin, Germany;
3.Berlin-Brandenburg Center for Regenerative Therapies (BCRT), Charité-Universitätsmedizin Berlin, Berlin, Germany.
Identifiers:URL:http://www.springerlink.com/content/t47854g31w3688...
DOI:10.1007/978-3-642-04241-6_2
ISBN:978-3-642-04240-9
Full Text:
Sorry, no privileges
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.