Algebraic comparison of metabolic networks, phylogenetic inference, and metabolic innovation

MAPPS: A Web-Based Tool for Metabolic Pathway Prediction and Network Analysis in the Postgenomic Era

Comparative and evolutionary analyses of metabolic networks have a wide range of applications, ranging from research into metabolic evolution through to practical applications in drug development, synthetic biology, and biodegradation. We present MAPPS: Metabolic network Analysis and Pathway Prediction Server (https://mapps.lums.edu.pk), a web-based tool to study functions and evolution of metabolic networks using traditional and 'omics data sets. MAPPS provides diverse functionalities including an interactive interface, graphical visualization of results, pathway prediction and network comparison, identification of potential drug targets, in silico metabolic engineering, host-microbe interactions, and ancestral network building. Importantly, MAPPS also allows users to upload custom data, thus enabling metabolic analyses on draft and custom genomes, and has an 'omics pipeline to filter pathway results, making it relevant in today's postgenomic era.

Network Analyses in Plant Pathogens

Even in the age of big data in Biology, studying the connections between the biological processes and the molecular mechanisms behind them is a challenging task. Systems biology arose as a transversal discipline between biology, chemistry, computer science, mathematics, and physics to facilitate the elucidation of such connections. A scenario, where the application of systems biology constitutes a very powerful tool, is the study of interactions between hosts and pathogens using network approaches. Interactions between pathogenic bacteria and their hosts, both in agricultural and human health contexts are of great interest to researchers worldwide. Large amounts of data have been generated in the last few years within this area of research. However, studies have been relatively limited to simple interactions. This has left great amounts of data that remain to be utilized. Here, we review the main techniques in network analysis and their complementary experimental assays used to investigate bacterial-plant interactions. Other host-pathogen interactions are presented in those cases where few or no examples of plant pathogens exist. Furthermore, we present key results that have been obtained with these techniques and how these can help in the design of new strategies to control bacterial pathogens. The review comprises metabolic simulation, protein-protein interactions, regulatory control of gene expression, host-pathogen modeling, and genome evolution in bacteria. The aim of this review is to offer scientists working on plant-pathogen interactions basic concepts around network biology, as well as an array of techniques that will be useful for a better and more complete interpretation of their data.

Inferring phylogenetic trees from the knowledge of rare evolutionary events

Rare events have played an increasing role in molecular phylogenetics as potentially homoplasy-poor characters. In this contribution we analyze the phylogenetic information content from a combinatorial point of view by considering the binary relation on the set of taxa defined by the existence of a single event separating two taxa. We show that the graph-representation of this relation must be a tree. Moreover, we characterize completely the relationship between the tree of such relations and the underlying phylogenetic tree. With directed operations such as tandem-duplication-random-loss events in mind we demonstrate how non-symmetric information constrains the position of the root in the partially reconstructed phylogeny.

Evaluating multi-locus phylogenies for species boundaries determination in the genus Diaporthe

BACKGROUND

Species identification is essential for controlling disease, understanding epidemiology, and to guide the implementation of phytosanitary measures against fungi from the genus Diaporthe. Accurate Diaporthe species separation requires using multi-loci phylogenies. However, defining the optimal set of loci that can be used for species identification is still an open problem.

METHODS

Here we addressed that problem by identifying five loci that have been sequenced in 142 Diaporthe isolates representing 96 species: TEF1, TUB, CAL, HIS and ITS. We then used every possible combination of those loci to build, analyse, and compare phylogenetic trees.

RESULTS

As expected, species separation is better when all five loci are simultaneously used to build the phylogeny of the isolates. However, removing the ITS locus has little effect on reconstructed phylogenies, identifying the TEF1-TUB-CAL-HIS 4-loci tree as almost equivalent to the 5-loci tree. We further identify the best 3-loci, 2-loci, and 1-locus trees that should be used for species separation in the genus.

DISCUSSION

Our results question the current use of the ITS locus for DNA barcoding in the genus Diaporthe and suggest that TEF1 might be a better choice if one locus barcoding needs to be done.

Phylogeny of metabolic networks: a spectral graph theoretical approach

Many methods have been developed for finding the commonalities between different organisms in order to study their phylogeny. The structure of metabolic networks also reveals valuable insights into metabolic capacity of species as well as into the habitats where they have evolved. We constructed metabolic networks of 79 fully sequenced organisms and compared their architectures. We used spectral density of normalized Laplacian matrix for comparing the structure of networks. The eigenvalues of this matrix reflect not only the global architecture of a network but also the local topologies that are produced by different graph evolutionary processes like motif duplication or joining. A divergence measure on spectral densities is used to quantify the distances between various metabolic networks, and a split network is constructed to analyse the phylogeny from these distances. In our analysis, we focused on the species that belong to different classes, but appear more related to each other in the phylogeny. We tried to explore whether they have evolved under similar environmental conditions or have similar life histories. With this focus, we have obtained interesting insights into the phylogenetic commonality between different organisms.

Steady state analysis of the genetic regulatory network incorporating underlying molecular mechanisms for anaerobic metabolism in Escherichia coli

A Gene Regulatory Network (GRN) represents complex connections between genes in a cell which interact with each other through their RNA and protein expression products, thereby determining the expression levels of mRNA and proteins required for functioning of the cell. Microarray experiments yield the log fold change in mRNA abundance and quantify the expression levels for a GRN at the genome level. While Boolean or Bayesian modeling along with expression and location data are useful in analyzing microarray data, they lack underlying mechanistic details present in GRNs. Our objective is to understand the role of molecular mechanisms in quantifying a GRN. To that effect, we analyze under steady state, the complete GRN for the central metabolic pathway during anaerobiosis in Escherichia coli. We simulate the microarray experiments using a steady state gene expression simulator (SSGES) that models molecular mechanistic details such as dimerization, multiple-site binding, auto-regulation and feedback. Given a GRN, the SSGES provided the log fold change in mRNA expression values as the output, which can be compared to data from microarray experiments. We predict the log fold changes for mutants obtained by knocking out crucial transcriptional regulators such as FNR (F), ArcA (A), IHFA-B (I) and DpiA (D) and observe a high degree of correlation with previously reported experimental data. We also predict the microarray expression values for hitherto unknown combinations of deletion mutants. We hierarchically cluster the predicted log fold change values for these mutants and postulate that E. coli has evolved from a predominantly lactate secreting (FAID mutant) into a mixed acid secreting phenotype as seen in the wild type (WT) during anaerobiosis. Upon simulating a model without incorporating the mechanistic details, not only the correlation with the experimental data reduced considerably, but also the clustering of expression data indicated WT to be closer to the quadruple mutant FAID. This clearly demonstrates the significance of incorporating mechanistic data while quantifying the expression profile of a GRN which can help in predicting the effect of a gene mutant and understanding the evolution of transcriptional control.

An inferential framework for biological network hypothesis tests

BACKGROUND

Networks are ubiquitous in modern cell biology and physiology. A large literature exists for inferring/proposing biological pathways/networks using statistical or machine learning algorithms. Despite these advances a formal testing procedure for analyzing network-level observations is in need of further development. Comparing the behaviour of a pharmacologically altered pathway to its canonical form is an example of a salient one-sample comparison. Locating which pathways differentiate disease from no-disease phenotype may be recast as a two-sample network inference problem.

RESULTS

We outline an inferential method for performing one- and two-sample hypothesis tests where the sampling unit is a network and the hypotheses are stated via network model(s). We propose a dissimilarity measure that incorporates nearby neighbour information to contrast one or more networks in a statistical test. We demonstrate and explore the utility of our approach with both simulated and microarray data; random graphs and weighted (partial) correlation networks are used to form network models. Using both a well-known diabetes dataset and an ovarian cancer dataset, the methods outlined here could better elucidate co-regulation changes for one or more pathways between two clinically relevant phenotypes.

CONCLUSIONS

Formal hypothesis tests for gene- or protein-based networks are a logical progression from existing gene-based and gene-set tests for differential expression. Commensurate with the growing appreciation and development of systems biology, the dissimilarity-based testing methods presented here may allow us to improve our understanding of pathways and other complex regulatory systems. The benefit of our method was illustrated under select scenarios.

Structural distance and evolutionary relationship of networks

Exploring common features and universal qualities shared by a particular class of networks in biological and other domains is one of the important aspects of evolutionary study. In an evolving system, evolutionary mechanism can cause functional changes that forces the system to adapt to new configurations of interaction pattern between the components of that system (e.g. gene duplication and mutation play a vital role for changing the connectivity structure in many biological networks. The evolutionary relation between two systems can be retraced by their structural differences). The eigenvalues of the normalized graph Laplacian not only capture the global properties of a network, but also local structures that are produced by graph evolutions (like motif duplication or joining). The spectrum of this operator carries many qualitative aspects of a graph. Given two networks of different sizes, we propose a method to quantify the topological distance between them based on the contrasting spectrum of normalized graph Laplacian. We find that network architectures are more similar within the same class compared to between classes. We also show that the evolutionary relationships can be retraced by the structural differences using our method. We analyze 43 metabolic networks from different species and mark the prominent separation of three groups: Bacteria, Archaea and Eukarya. This phenomenon is well captured in our findings that support the other cladistic results based on gene content and ribosomal RNA sequences. Our measure to quantify the structural distance between two networks is useful to elucidate evolutionary relationships.

Properties of metabolic graphs: biological organization or representation artifacts?

Background

Standard graphs, where each edge links two nodes, have been extensively used to represent the connectivity of metabolic networks. It is based on this representation that properties of metabolic networks, such as hierarchical and small-world structures, have been elucidated and null models have been proposed to derive biological organization hypotheses. However, these graphs provide a simplistic model of a metabolic network's connectivity map, since metabolic reactions often involve more than two reactants. In other words, this map is better represented as a hypergraph. Consequently, a question that naturally arises in this context is whether these properties truly reflect biological organization or are merely an artifact of the representation.

Results

In this paper, we address this question by reanalyzing topological properties of the metabolic network of Escherichia coli under a hypergraph representation, as well as standard graph abstractions. We find that when clustering is properly defined for hypergraphs and subsequently used to analyze metabolic networks, the scaling of clustering, and thus the hierarchical structure hypothesis in metabolic networks, become unsupported. Moreover, we find that incorporating the distribution of reaction sizes into the null model further weakens the support for the scaling patterns.

Conclusions

These results combined suggest that the reported scaling of the clustering coefficients in the metabolic graphs and its specific power coefficient may be an artifact of the graph representation, and may not be supported when biochemical reactions are atomically treated as hyperedges. This study highlights the implications of the way a biological system is represented and the null model employed on the elucidated properties, along with their support, of the system.

Enzyme sequence similarity improves the reaction alignment method for cross-species pathway comparison

Pathway-based information has become an important source of information for both establishing evolutionary relationships and understanding the mode of action of a chemical or pharmaceutical among species. Cross-species comparison of pathways can address two broad questions: comparison in order to inform evolutionary relationships and to extrapolate species differences used in a number of different applications including drug and toxicity testing. Cross-species comparison of metabolic pathways is complex as there are multiple features of a pathway that can be modeled and compared. Among the various methods that have been proposed, reaction alignment has emerged as the most successful at predicting phylogenetic relationships based on NCBI taxonomy. We propose an improvement of the reaction alignment method by accounting for sequence similarity in addition to reaction alignment method. Using nine species, including human and some model organisms and test species, we evaluate the standard and improved comparison methods by analyzing glycolysis and citrate cycle pathways conservation. In addition, we demonstrate how organism comparison can be conducted by accounting for the cumulative information retrieved from nine pathways in central metabolism as well as a more complete study involving 36 pathways common in all nine species. Our results indicate that reaction alignment with enzyme sequence similarity results in a more accurate representation of pathway specific cross-species similarities and differences based on NCBI taxonomy.

A Bayesian approach to the evolution of metabolic networks on a phylogeny

The availability of genomes of many closely related bacteria with diverse metabolic capabilities offers the possibility of tracing metabolic evolution on a phylogeny relating the genomes to understand the evolutionary processes and constraints that affect the evolution of metabolic networks. Using simple (independent loss/gain of reactions) or complex (incorporating dependencies among reactions) stochastic models of metabolic evolution, it is possible to study how metabolic networks evolve over time. Here, we describe a model that takes the reaction neighborhood into account when modeling metabolic evolution. The model also allows estimation of the strength of the neighborhood effect during the course of evolution. We present Gibbs samplers for sampling networks at the internal node of a phylogeny and for estimating the parameters of evolution over a phylogeny without exploring the whole search space by iteratively sampling from the conditional distributions of the internal networks and parameters. The samplers are used to estimate the parameters of evolution of metabolic networks of bacteria in the genus Pseudomonas and to infer the metabolic networks of the ancestral pseudomonads. The results suggest that pathway maps that are conserved across the Pseudomonas phylogeny have a stronger neighborhood structure than those which have a variable distribution of reactions across the phylogeny, and that some Pseudomonas lineages are going through genome reduction resulting in the loss of a number of reactions from their metabolic networks.

Metabolic networks correspond to one of the most complex cellular processes. Most organisms have a common set of reactions as a part of their metabolic networks that relate to essential processes such as generation of energy and the synthesis of important biological molecules, which are required for their survival. However, a large proportion of the reactions present in different organisms are specific to the needs of individual organisms. The regions of metabolic networks corresponding to these non-essential reactions are under continuous evolution. Using different models of evolution, we can ask important biological questions about the ways in which the metabolic networks of different organisms enable them to be well-adapted to the environments in which they live, and how these metabolic adaptations have evolved. We use a stochastic approach to study the evolution of metabolic networks and show that evolutionary inferences can be made using the structure of these networks. Our results indicate that plant pathogenic Pseudomonas are going through genome reduction resulting in the loss of metabolic functionalities. We also show the potential of stochastic approaches to infer the networks present at ancestral levels of a given phylogeny compared to deterministic methods such as parsimony.

Comparative genomics of metabolic networks of free-living and parasitic eukaryotes

Background

Obligate endoparasites often lack particular metabolic pathways as compared to free-living organisms. This phenomenon comprises anabolic as well as catabolic reactions. Presumably, the corresponding enzymes were lost in adaptation to parasitism. Here we compare the predicted core metabolic graphs of obligate endoparasites and non-parasites (free living organisms and facultative parasites) in order to analyze how the parasites' metabolic networks shrunk in the course of evolution.

Results

Core metabolic graphs comprising biochemical reactions present in the presumed ancestor of parasites and non-parasites were reconstructed from the Kyoto Encyclopedia of Genes and Genomes. While the parasites' networks had fewer nodes (metabolites) and edges (reactions), other parameters such as average connectivity, network diameter and number of isolated edges were similar in parasites and non-parasites. The parasites' networks contained a higher percentage of ATP-consuming reactions and a lower percentage of NAD-requiring reactions. Control networks, shrunk to the size of the parasites' by random deletion of edges, were scale-free but exhibited smaller diameters and more isolated edges.

Conclusions

The parasites' networks were smaller than those of the non-parasites regarding number of nodes or edges, but not regarding network diameters. Network integrity but not scale-freeness has acted as a selective principle during the evolutionary reduction of parasite metabolism. ATP-requiring reactions in particular have been retained in the parasites' core metabolism while NADH- or NADPH-requiring reactions were lost preferentially.

Defining genes: a computational framework

The precise elucidation of the gene concept has become the subject of intense discussion in light of results from several, large high-throughput surveys of transcriptomes and proteomes. In previous work, we proposed an approach for constructing gene concepts that combines genomic heritability with elements of function. Here, we introduce a definition of the gene within a computational framework of cellular interactions. The definition seeks to satisfy the practical requirements imposed by annotation, capture logical aspects of regulation, and encompass the evolutionary property of homology.

Multimodal networks: structure and operations

A multimodal network (MMN) is a novel graph-theoretic formalism designed to capture the structure of biological networks and to represent relationships derived from multiple biological databases. MMNs generalize the standard notions of graphs and hypergraphs, which are the bases of current diagrammatic representations of biological phenomena and incorporate the concept of mode. Each vertex of an MMN is a biological entity, a biot, while each modal hyperedge is a typed relationship, where the type is given by the mode of the hyperedge. The current paper defines MMNs and concentrates on the structural aspects of MMNs. A companion paper develops MMNs as a representation of the semantics of biological networks and discusses applications of the MMNs in managing complex biological data. The MMN model has been implemented in a database system containing multiple kinds of biological networks.

Optimized ancestral state reconstruction using Sankoff parsimony

BACKGROUND

Parsimony methods are widely used in molecular evolution to estimate the most plausible phylogeny for a set of characters. Sankoff parsimony determines the minimum number of changes required in a given phylogeny when a cost is associated to transitions between character states. Although optimizations exist to reduce the computations in the number of taxa, the original algorithm takes time O(n(2)) in the number of states, making it impractical for large values of n.

RESULTS

In this study we introduce an optimization of Sankoff parsimony for the reconstruction of ancestral states when ultrametric or additive cost matrices are used. We analyzed its performance for randomly generated matrices, Jukes-Cantor and Kimura's two-parameter models of DNA evolution, and in the reconstruction of elongation factor-1alpha and ancestral metabolic states of a group of eukaryotes, showing that in all cases the execution time is significantly less than with the original implementation.

CONCLUSION

The algorithms here presented provide a fast computation of Sankoff parsimony for a given phylogeny. Problems where the number of states is large, such as reconstruction of ancestral metabolism, are particularly adequate for this optimization. Since we are reducing the computations required to calculate the parsimony cost of a single tree, our method can be combined with optimizations in the number of taxa that aim at finding the most parsimonious tree.

A topological approach to chemical organizations

Large chemical reaction networks often exhibit distinctive features that can be interpreted as higher-level structures. Prime examples are metabolic pathways in a biochemical context. We review mathematical approaches that exploit the stoichiometric structure, which can be seen as a particular directed hypergraph, to derive an algebraic picture of chemical organizations. We then give an alternative interpretation in terms of set-valued set functions that encapsulate the production rules of the individual reactions. From the mathematical point of view, these functions define generalized topological spaces on the set of chemical species. We show that organization-theoretic concepts also appear in a natural way in the topological language. This abstract representation in turn suggests the exploration of the chemical meaning of well-established topological concepts. As an example, we consider connectedness in some detail.

A method of biological pathway similarity search using high performance computing

Comparative study of biological pathway structures and composition can aid us in elucidating the functions of newly discovered pathways, understanding evolutionary traits, and determining missing pathway elements. A method has been developed to perform pair-wise comparison and similarity search of biological pathways. The comparison determines the differences of each pair of pathways represented in the XML format. The similarity search uses a scoring mechanism to rank the similarities of the pathway in question against those in the pathway repository. To achieve a reasonably good performance, the method is being implemented using the Condor high performance computing environment.

An introduction to metabolic networks and their structural analysis

There has been a renewed interest for metabolism in the computational biology community, leading to an avalanche of papers coming from methodological network analysis as well as experimental and theoretical biology. This paper is meant to serve as an initial guide for both the biologists interested in formal approaches and the mathematicians or computer scientists wishing to inject more realism into their models. The paper is focused on the structural aspects of metabolism only. The literature is vast enough already, and the thread through it difficult to follow even for the more experienced worker in the field. We explain methods for acquiring data and reconstructing metabolic networks, and review the various models that have been used for their structural analysis. Several concepts such as modularity are introduced, as are the controversies that have beset the field these past few years, for instance, on whether metabolic networks are small-world or scale-free, and on which model better explains the evolution of metabolism. Clarifying the work that has been done also helps in identifying open questions and in proposing relevant future directions in the field, which we do along the paper and in the conclusion.

Phylogenetic distances are encoded in networks of interacting pathways

MOTIVATION

Although metabolic reactions are unquestionably shaped by evolutionary processes, the degree to which the overall structure and complexity of their interconnections are linked to the phylogeny of species has not been evaluated in depth. Here, we apply an original metabolome representation, termed Network of Interacting Pathways or NIP, with a combination of graph theoretical and machine learning strategies, to address this question. NIPs compress the information of the metabolic network exhibited by a species into much smaller networks of overlapping metabolic pathways, where nodes are pathways and links are the metabolites they exchange.

RESULTS

Our analysis shows that a small set of descriptors of the structure and complexity of the NIPs combined into regression models reproduce very accurately reference phylogenetic distances derived from 16S rRNA sequences (10-fold cross-validation correlation coefficient higher than 0.9). Our method also showed better scores than previous work on metabolism-based phylogenetic reconstructions, as assessed by branch distances score, topological similarity and second cousins score. Thus, our metabolome representation as network of overlapping metabolic pathways captures sufficient information about the underlying evolutionary events leading to the formation of metabolic networks and species phylogeny. It is important to note that precise knowledge of all of the reactions in these pathways is not required for these reconstructions. These observations underscore the potential for the use of abstract, modular representations of metabolic reactions as tools in studying the evolution of species.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Comparative Pathway Analyzer--a web server for comparative analysis, clustering and visualization of metabolic networks in multiple organisms

In order to understand the phenotype of any living system, it is essential to not only investigate its genes, but also the specific metabolic pathway variant of the organism of interest, ideally in comparison with other organisms. The Comparative Pathway Analyzer, CPA, calculates and displays the differences in metabolic reaction content between two sets of organisms. Because results are highly dependent on the distribution of organisms into these two sets and the appropriate definition of these sets often is not easy, we provide hierarchical clustering methods for the identification of significant groupings. CPA also visualizes the reaction content of several organisms simultaneously allowing easy comparison. Reaction annotation data and maps for visualizing the results are taken from the KEGG database. Additionally, users can upload their own annotation data. This website is free and open to all users and there is no login requirement. It is available at https://www.cebitec.uni-bielefeld.de/groups/brf/software/cpa/index.html.

Metabolic reconstruction and analysis for parasite genomes

With the completion of sequencing projects for several parasite genomes, efforts are ongoing to make sense of this mass of information in terms of the gene products encoded and their interactions in the growth, development and survival of parasites. The emerging science of systems biology aims to explain the complex relationship between genotype and phenotype by using network models. One area in which this approach has been particularly successful is in the modeling of metabolism. With an accurate picture of the set of metabolic reactions encoded in a genome, it is now possible to identify enzymes or transporters that might be viable targets for new drugs. Because these predictions greatly depend on the quality and completeness of the genome annotation, there are substantial efforts in the scientific community to increase the numbers of metabolic enzymes identified. In this review, we discuss the opportunities for using metabolic reconstruction and analysis tools in parasitology research, and their applications to protozoan parasites.

Environmental variability and modularity of bacterial metabolic networks

BACKGROUND

Biological systems are often modular: they can be decomposed into nearly-independent structural units that perform specific functions. The evolutionary origin of modularity is a subject of much current interest. Recent theory suggests that modularity can be enhanced when the environment changes over time. However, this theory has not yet been tested using biological data.

RESULTS

To address this, we studied the relation between environmental variability and modularity in a natural and well-studied system, the metabolic networks of bacteria. We classified 117 bacterial species according to the degree of variability in their natural habitat. We find that metabolic networks of organisms in variable environments are significantly more modular than networks of organisms that evolved under more constant conditions.

CONCLUSION

This study supports the view that variability in the natural habitat of an organism promotes modularity in its metabolic network and perhaps in other biological systems.