TY - JOUR A1 - Nikoloski, Zoran A1 - Grimbs, Sergio A1 - Klie, Sebastian A1 - Selbig, Joachim T1 - Complexity of automated gene annotation JF - Biosystems : journal of biological and information processing sciences N2 - 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 of heuristic or approximation algorithms a priority for additional research. KW - Complexity KW - Gene function prediction KW - External structural measures KW - Transductive learning Y1 - 2011 U6 - https://doi.org/10.1016/j.biosystems.2010.12.003 SN - 0303-2647 VL - 104 IS - 1 SP - 1 EP - 8 PB - Elsevier CY - Oxford ER - TY - JOUR A1 - Töpfer, Nadine A1 - Caldana, Camila A1 - Grimbs, Sergio A1 - Willmitzer, Lothar A1 - Fernie, Alisdair R. A1 - Nikoloski, Zoran T1 - Integration of genome-scale modeling and transcript profiling reveals metabolic pathways underlying light and temperature acclimation in arabidopsis JF - The plant cell N2 - Understanding metabolic acclimation of plants to challenging environmental conditions is essential for dissecting the role of metabolic pathways in growth and survival. As stresses involve simultaneous physiological alterations across all levels of cellular organization, a comprehensive characterization of the role of metabolic pathways in acclimation necessitates integration of genome-scale models with high-throughput data. Here, we present an integrative optimization-based approach, which, by coupling a plant metabolic network model and transcriptomics data, can predict the metabolic pathways affected in a single, carefully controlled experiment. Moreover, we propose three optimization-based indices that characterize different aspects of metabolic pathway behavior in the context of the entire metabolic network. We demonstrate that the proposed approach and indices facilitate quantitative comparisons and characterization of the plant metabolic response under eight different light and/or temperature conditions. The predictions of the metabolic functions involved in metabolic acclimation of Arabidopsis thaliana to the changing conditions are in line with experimental evidence and result in a hypothesis about the role of homocysteine-to-Cys interconversion and Asn biosynthesis. The approach can also be used to reveal the role of particular metabolic pathways in other scenarios, while taking into consideration the entirety of characterized plant metabolism. Y1 - 2013 U6 - https://doi.org/10.1105/tpc.112.108852 SN - 1040-4651 VL - 25 IS - 4 SP - 1197 EP - 1211 PB - American Society of Plant Physiologists CY - Rockville ER -