TY - JOUR A1 - Angeleska, Angela A1 - Omranian, Sara A1 - Nikoloski, Zoran T1 - Coherent network partitions BT - Characterizations with cographs and prime graphs JF - Theoretical computer science : the journal of the EATCS N2 - We continue to study coherent partitions of graphs whereby the vertex set is partitioned into subsets that induce biclique spanned subgraphs. The problem of identifying the minimum number of edges to obtain biclique spanned connected components (CNP), called the coherence number, is NP-hard even on bipartite graphs. Here, we propose a graph transformation geared towards obtaining an O (log n)-approximation algorithm for the CNP on a bipartite graph with n vertices. The transformation is inspired by a new characterization of biclique spanned subgraphs. In addition, we study coherent partitions on prime graphs, and show that finding coherent partitions reduces to the problem of finding coherent partitions in a prime graph. Therefore, these results provide future directions for approximation algorithms for the coherence number of a given graph. KW - Graph partitions KW - Network clustering KW - Cographs KW - Coherent partition KW - Prime graphs Y1 - 2021 U6 - https://doi.org/10.1016/j.tcs.2021.10.002 SN - 0304-3975 VL - 894 SP - 3 EP - 11 PB - Elsevier CY - Amsterdam [u.a.] ER - TY - JOUR A1 - Calderan-Rodrigues, Maria Juliana A1 - Luzarowski, Marcin A1 - Monte-Bello, Carolina Cassano A1 - Minen, Romina Ines A1 - Zühlke, Boris M. A1 - Nikoloski, Zoran A1 - Skirycz, Aleksandra A1 - Caldana, Camila T1 - Proteogenic dipeptides are characterized by diel fluctuations and target of rapamycin complex-signaling dependency in the model plant Arabidopsis thaliana JF - Frontiers in plant science : FPLS N2 - As autotrophic organisms, plants capture light energy to convert carbon dioxide into ATP, nicotinamide adenine dinucleotide phosphate (NADPH), and sugars, which are essential for the biosynthesis of building blocks, storage, and growth. At night, metabolism and growth can be sustained by mobilizing carbon (C) reserves. In response to changing environmental conditions, such as light-dark cycles, the small-molecule regulation of enzymatic activities is critical for reprogramming cellular metabolism. We have recently demonstrated that proteogenic dipeptides, protein degradation products, act as metabolic switches at the interface of proteostasis and central metabolism in both plants and yeast. Dipeptides accumulate in response to the environmental changes and act via direct binding and regulation of critical enzymatic activities, enabling C flux distribution. Here, we provide evidence pointing to the involvement of dipeptides in the metabolic rewiring characteristics for the day-night cycle in plants. Specifically, we measured the abundance of 13 amino acids and 179 dipeptides over short- (SD) and long-day (LD) diel cycles, each with different light intensities. Of the measured dipeptides, 38 and eight were characterized by day-night oscillation in SD and LD, respectively, reaching maximum accumulation at the end of the day and then gradually falling in the night. Not only the number of dipeptides, but also the amplitude of the oscillation was higher in SD compared with LD conditions. Notably, rhythmic dipeptides were enriched in the glucogenic amino acids that can be converted into glucose. Considering the known role of Target of Rapamycin (TOR) signaling in regulating both autophagy and metabolism, we subsequently investigated whether diurnal fluctuations of dipeptides levels are dependent on the TOR Complex (TORC). The Raptor1b mutant (raptor1b), known for the substantial reduction of TOR kinase activity, was characterized by the augmented accumulation of dipeptides, which is especially pronounced under LD conditions. We were particularly intrigued by the group of 16 dipeptides, which, based on their oscillation under SD conditions and accumulation in raptor1b, can be associated with limited C availability or photoperiod. By mining existing protein-metabolite interaction data, we delineated putative protein interactors for a representative dipeptide Pro-Gln. The obtained list included enzymes of C and amino acid metabolism, which are also linked to the TORC-mediated metabolic network. Based on the obtained results, we speculate that the diurnal accumulation of dipeptides contributes to its metabolic adaptation in response to changes in C availability. We hypothesize that dipeptides would act as alternative respiratory substrates and by directly modulating the activity of the focal enzymes. KW - dipeptide KW - diel cycle KW - metabolism KW - TOR signaling KW - protein-metabolite KW - interactions KW - carbon limitation KW - amino acid Y1 - 2021 U6 - https://doi.org/10.3389/fpls.2021.758933 SN - 1664-462X VL - 12 PB - Frontiers Media CY - Lausanne ER - TY - JOUR A1 - Hashemi, Seirana A1 - Razaghi-Moghadam, Zahra A1 - Nikoloski, Zoran T1 - Identification of flux trade-offs in metabolic networks JF - Scientific reports N2 - Trade-offs are inherent to biochemical networks governing diverse cellular functions, from gene expression to metabolism. Yet, trade-offs between fluxes of biochemical reactions in a metabolic network have not been formally studied. Here, we introduce the concept of absolute flux trade-offs and devise a constraint-based approach, termed FluTO, to identify and enumerate flux trade-offs in a given genome-scale metabolic network. By employing the metabolic networks of Escherichia coli and Saccharomyces cerevisiae, we demonstrate that the flux trade-offs are specific to carbon sources provided but that reactions involved in the cofactor and prosthetic group biosynthesis are present in trade-offs across all carbon sources supporting growth. We also show that absolute flux trade-offs depend on the biomass reaction used to model the growth of Arabidopsis thaliana under different carbon and nitrogen conditions. The identified flux trade-offs reflect the tight coupling between nitrogen, carbon, and sulphur metabolisms in leaves of C-3 plants. Altogether, FluTO provides the means to explore the space of alternative metabolic routes reflecting the constraints imposed by inherent flux trade-offs in large-scale metabolic networks. Y1 - 2021 U6 - https://doi.org/10.1038/s41598-021-03224-9 SN - 2045-2322 VL - 11 IS - 1 PB - Macmillan Publishers Limited, part of Springer Nature CY - London ER - TY - JOUR A1 - Küken, Anika A1 - Wendering, Philipp A1 - Langary, Damoun A1 - Nikoloski, Zoran T1 - A structural property for reduction of biochemical networks JF - Scientific reports N2 - Large-scale biochemical models are of increasing sizes due to the consideration of interacting organisms and tissues. Model reduction approaches that preserve the flux phenotypes can simplify the analysis and predictions of steady-state metabolic phenotypes. However, existing approaches either restrict functionality of reduced models or do not lead to significant decreases in the number of modelled metabolites. Here, we introduce an approach for model reduction based on the structural property of balancing of complexes that preserves the steady-state fluxes supported by the network and can be efficiently determined at genome scale. Using two large-scale mass-action kinetic models of Escherichia coli, we show that our approach results in a substantial reduction of 99% of metabolites. Applications to genome-scale metabolic models across kingdoms of life result in up to 55% and 85% reduction in the number of metabolites when arbitrary and mass-action kinetics is assumed, respectively. We also show that predictions of the specific growth rate from the reduced models match those based on the original models. Since steady-state flux phenotypes from the original model are preserved in the reduced, the approach paves the way for analysing other metabolic phenotypes in large-scale biochemical networks. Y1 - 2021 U6 - https://doi.org/10.1038/s41598-021-96835-1 SN - 2045-2322 VL - 11 IS - 1 PB - Macmillan Publishers Limited, part of Springer Nature CY - London ER - TY - JOUR A1 - Mbebi, Alain J. A1 - Tong, Hao A1 - Nikoloski, Zoran T1 - L-2,L-1-norm regularized multivariate regression model with applications to genomic prediction JF - Bioinformatics N2 - Motivation: Genomic selection (GS) is currently deemed the most effective approach to speed up breeding of agricultural varieties. It has been recognized that consideration of multiple traits in GS can improve accuracy of prediction for traits of low heritability. However, since GS forgoes statistical testing with the idea of improving predictions, it does not facilitate mechanistic understanding of the contribution of particular single nucleotide polymorphisms (SNP). Results: Here, we propose a L-2,L-1-norm regularized multivariate regression model and devise a fast and efficient iterative optimization algorithm, called L-2,L-1-joint, applicable in multi-trait GS. The usage of the L-2,L-1-norm facilitates variable selection in a penalized multivariate regression that considers the relation between individuals, when the number of SNPs is much larger than the number of individuals. The capacity for variable selection allows us to define master regulators that can be used in a multi-trait GS setting to dissect the genetic architecture of the analyzed traits. Our comparative analyses demonstrate that the proposed model is a favorable candidate compared to existing state-of-the-art approaches. Prediction and variable selection with datasets from Brassica napus, wheat and Arabidopsis thaliana diversity panels are conducted to further showcase the performance of the proposed model. Y1 - 2021 U6 - https://doi.org/10.1093/bioinformatics/btab212 SN - 1367-4803 SN - 1460-2059 VL - 37 IS - 18 SP - 2896 EP - 2904 PB - Oxford Univ. Press CY - Oxford ER - TY - JOUR A1 - Omranian, Sara A1 - Angeleska, Angela A1 - Nikoloski, Zoran T1 - PC2P BT - parameter-free network-based prediction of protein complexes JF - Bioinformatics N2 - Motivation: Prediction of protein complexes from protein-protein interaction (PPI) networks is an important problem in systems biology, as they control different cellular functions. The existing solutions employ algorithms for network community detection that identify dense subgraphs in PPI networks. However, gold standards in yeast and human indicate that protein complexes can also induce sparse subgraphs, introducing further challenges in protein complex prediction. Results: To address this issue, we formalize protein complexes as biclique spanned subgraphs, which include both sparse and dense subgraphs. We then cast the problem of protein complex prediction as a network partitioning into biclique spanned subgraphs with removal of minimum number of edges, called coherent partition. Since finding a coherent partition is a computationally intractable problem, we devise a parameter-free greedy approximation algorithm, termed Protein Complexes from Coherent Partition (PC2P), based on key properties of biclique spanned subgraphs. Through comparison with nine contenders, we demonstrate that PC2P: (i) successfully identifies modular structure in networks, as a prerequisite for protein complex prediction, (ii) outperforms the existing solutions with respect to a composite score of five performance measures on 75% and 100% of the analyzed PPI networks and gold standards in yeast and human, respectively, and (iii,iv) does not compromise GO semantic similarity and enrichment score of the predicted protein complexes. Therefore, our study demonstrates that clustering of networks in terms of biclique spanned subgraphs is a promising framework for detection of complexes in PPI networks. Y1 - 2021 U6 - https://doi.org/10.1093/bioinformatics/btaa1089 SN - 1367-4803 SN - 1460-2059 VL - 37 IS - 1 SP - 73 EP - 81 PB - Oxford Univ. Press CY - Oxford ER - TY - JOUR A1 - Omranian, Sara A1 - Angeleska, Angela A1 - Nikoloski, Zoran T1 - Efficient and accurate identification of protein complexes from protein-protein interaction networks based on the clustering coefficient JF - Computational and structural biotechnology journal N2 - Identification of protein complexes from protein-protein interaction (PPI) networks is a key problem in PPI mining, solved by parameter-dependent approaches that suffer from small recall rates. Here we introduce GCC-v, a family of efficient, parameter-free algorithms to accurately predict protein complexes using the (weighted) clustering coefficient of proteins in PPI networks. Through comparative analyses with gold standards and PPI networks from Escherichia coli, Saccharomyces cerevisiae, and Homo sapiens, we demonstrate that GCC-v outperforms twelve state-of-the-art approaches for identification of protein complexes with respect to twelve performance measures in at least 85.71% of scenarios. We also show that GCC-v results in the exact recovery of similar to 35% of protein complexes in a pan-plant PPI network and discover 144 new protein complexes in Arabidopsis thaliana, with high support from GO semantic similarity. Our results indicate that findings from GCC-v are robust to network perturbations, which has direct implications to assess the impact of the PPI network quality on the predicted protein complexes. (C) 2021 The Author(s). Published by Elsevier B.V. on behalf of Research Network of Computational and Structural Biotechnology. KW - Protein complexes KW - Protein-protein interaction KW - Network clustering KW - Species comparison Y1 - 2021 U6 - https://doi.org/10.1016/j.csbj.2021.09.014 SN - 2001-0370 VL - 19 SP - 5255 EP - 5263 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Pries, Christopher A1 - Razaghi-Moghadam, Zahra A1 - Kopka, Joachim A1 - Nikoloski, Zoran T1 - Integration of relative metabolomics and transcriptomics time-course data in a metabolic model pinpoints effects of ribosome biogenesis defects on Arabidopsis thaliana metabolism JF - Scientific reports N2 - Ribosome biogenesis is tightly associated to plant metabolism due to the usage of ribosomes in the synthesis of proteins necessary to drive metabolic pathways. Given the central role of ribosome biogenesis in cell physiology, it is important to characterize the impact of different components involved in this process on plant metabolism. Double mutants of the Arabidopsis thaliana cytosolic 60S maturation factors REIL1 and REIL2 do not resume growth after shift to moderate 10 degrees C chilling conditions. To gain mechanistic insights into the metabolic effects of this ribosome biogenesis defect on metabolism, we developed TC-iReMet2, a constraint-based modelling approach that integrates relative metabolomics and transcriptomics time-course data to predict differential fluxes on a genome-scale level. We employed TC-iReMet2 with metabolomics and transcriptomics data from the Arabidopsis Columbia 0 wild type and the reil1-1 reil2-1 double mutant before and after cold shift. We identified reactions and pathways that are highly altered in a mutant relative to the wild type. These pathways include the Calvin-Benson cycle, photorespiration, gluconeogenesis, and glycolysis. Our findings also indicated differential NAD(P)/NAD(P)H ratios after cold shift. TC-iReMet2 allows for mechanistic hypothesis generation and interpretation of system biology experiments related to metabolic fluxes on a genome-scale level. Y1 - 2021 U6 - https://doi.org/10.1038/s41598-021-84114-y SN - 2045-2322 VL - 11 IS - 1 PB - Macmillan Publishers Limited, part of Springer Nature CY - London ER - TY - JOUR A1 - Seep, Lea A1 - Razaghi-Moghadam, Zahra A1 - Nikoloski, Zoran T1 - Reaction lumping in metabolic networks for application with thermodynamic metabolic flux analysis JF - Scientific reports N2 - Thermodynamic metabolic flux analysis (TMFA) can narrow down the space of steady-state flux distributions, but requires knowledge of the standard Gibbs free energy for the modelled reactions. The latter are often not available due to unknown Gibbs free energy change of formation ,Delta fG0, of metabolites. To optimize the usage of data on thermodynamics in constraining a model, reaction lumping has been proposed to eliminate metabolites with unknown Delta fG0. However, the lumping procedure has not been formalized nor implemented for systematic identification of lumped reactions. Here, we propose, implement, and test a combined procedure for reaction lumping, applicable to genome-scale metabolic models. It is based on identification of groups of metabolites with unknown Delta fG0 whose elimination can be conducted independently of the others via: (1) group implementation, aiming to eliminate an entire such group, and, if this is infeasible, (2) a sequential implementation to ensure that a maximal number of metabolites with unknown Delta fG0 are eliminated. Our comparative analysis with genome-scale metabolic models of Escherichia coli, Bacillus subtilis, and Homo sapiens shows that the combined procedure provides an efficient means for systematic identification of lumped reactions. We also demonstrate that TMFA applied to models with reactions lumped according to the proposed procedure lead to more precise predictions in comparison to the original models. The provided implementation thus ensures the reproducibility of the findings and their application with standard TMFA. Y1 - 2021 U6 - https://doi.org/10.1038/s41598-021-87643-8 SN - 2045-2322 VL - 11 IS - 1 PB - Macmillan Publishers Limited, part of Springer Nature CY - London ER - TY - JOUR A1 - Tong, Hao A1 - Küken, Anika A1 - Razaghi-Moghadam, Zahra A1 - Nikoloski, Zoran T1 - Characterization of effects of genetic variants via genome-scale metabolic modelling JF - Cellular and molecular life sciences : CMLS N2 - Genome-scale metabolic networks for model plants and crops in combination with approaches from the constraint-based modelling framework have been used to predict metabolic traits and design metabolic engineering strategies for their manipulation. With the advances in technologies to generate large-scale genotyping data from natural diversity panels and other populations, genome-wide association and genomic selection have emerged as statistical approaches to determine genetic variants associated with and predictive of traits. Here, we review recent advances in constraint-based approaches that integrate genetic variants in genome-scale metabolic models to characterize their effects on reaction fluxes. Since some of these approaches have been applied in organisms other than plants, we provide a critical assessment of their applicability particularly in crops. In addition, we further dissect the inferred effects of genetic variants with respect to reaction rate constants, abundances of enzymes, and concentrations of metabolites, as main determinants of reaction fluxes and relate them with their combined effects on complex traits, like growth. Through this systematic review, we also provide a roadmap for future research to increase the predictive power of statistical approaches by coupling them with mechanistic models of metabolism. KW - Single-nucleotide polymorphisms KW - Metabolic models KW - Genome-wide KW - association studies KW - Genomic selection Y1 - 2021 U6 - https://doi.org/10.1007/s00018-021-03844-4 SN - 1420-682X SN - 1420-9071 VL - 78 IS - 12 SP - 5123 EP - 5138 PB - Springer International Publishing AG CY - Cham ER -