Complexity of automated gene annotation
- Integration of high-throughput data with functional annotation by graph-theoretic methods has been postulated as promising way to unravel the function of unannotated genes. Here, we first review the existing graph-theoretic approaches for automated gene function annotation and classify them into two categories with respect to their relation to two instances of transductive learning on networks - with dynamic costs and with constant costs - depending on whether or not ontological relationship between functional terms is employed. The determined categories allow to characterize the computational complexity of the existing approaches and establish the relation to classical graph-theoretic problems, such as bisection and multiway cut. In addition, our results point out that the ontological form of the structured functional knowledge does not lower the complexity of the transductive learning with dynamic costs - one of the key problems in modern systems biology. The NP-hardness of automated gene annotation renders the development ofIntegration of high-throughput data with functional annotation by graph-theoretic methods has been postulated as promising way to unravel the function of unannotated genes. Here, we first review the existing graph-theoretic approaches for automated gene function annotation and classify them into two categories with respect to their relation to two instances of transductive learning on networks - with dynamic costs and with constant costs - depending on whether or not ontological relationship between functional terms is employed. The determined categories allow to characterize the computational complexity of the existing approaches and establish the relation to classical graph-theoretic problems, such as bisection and multiway cut. In addition, our results point out that the ontological form of the structured functional knowledge does not lower the complexity of the transductive learning with dynamic costs - one of the key problems in modern systems biology. The NP-hardness of automated gene annotation renders the development of heuristic or approximation algorithms a priority for additional research.…
Author details: | Zoran NikoloskiORCiDGND, Sergio Grimbs, Sebastian Klie, Joachim SelbigGND |
---|---|
DOI: | https://doi.org/10.1016/j.biosystems.2010.12.003 |
ISSN: | 0303-2647 |
Title of parent work (English): | Biosystems : journal of biological and information processing sciences |
Publisher: | Elsevier |
Place of publishing: | Oxford |
Publication type: | Article |
Language: | English |
Year of first publication: | 2011 |
Publication year: | 2011 |
Release date: | 2017/03/26 |
Tag: | Complexity; External structural measures; Gene function prediction; Transductive learning |
Volume: | 104 |
Issue: | 1 |
Number of pages: | 8 |
First page: | 1 |
Last Page: | 8 |
Funding institution: | Federal Ministry of Education and Research [0313924]; IMPRS; German Federal Ministry of Education and Research by the MedSys/ColoNET BMBF [0315417F] |
Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Biochemie und Biologie |
Peer review: | Referiert |