In our previous work we developed CoMeta, a tool for comparing metabolic pathways of di erent organisms, using the KEGG database as data source. The similarity measure adopted combines homology of reactions and functional aspects of the pathways. The latter are captured by T-invariants in the Petri net representation, which correspond to potential uxes in the pathways. A Petri net can model a metabolic pathway of an organism either in isolation, focussing on its internal behaviour (isolated net), or as an interactive subsystem of the full metabolic network (open net). Modelling a pathway as an isolated net normally works ne for comparison purposes, but unsatisfactory results can arise as it supplies a partial view on internal uxes. A representation as an open net makes additional information available, but the choice of the interactions of the pathway with the environment is non-trivial. Considering all possible interactions with the environment (an information automatically retrieved from KEGG) is not appropriate. Some interactions may add noise to the model, the size of invariants bases grows up to an order of magnitude and the comparison results might be less precise than with the isolated representation. Here we propose an extension of CoMeta which allows the user to select which metabolites should be considered as interactions of interest, discriminating between input and output metabolites. We illustrate some experiments which show the advantages of this more exible approach. Our experience suggests that in general a good choice is to take as open metabolites those which are the input and output compounds for the pathway.
Subsystems of metabolism dealing with some speci c function are called metabolic pathways. Comparing metabolic pathways of di erent species yields interesting information on their evolution and it may help in understanding metabolic functions. This is important for metabolic engineering and for studying diseases and drugs design.
In [
We developed CoMeta, a tool implementing our proposal. Given a set of
organisms and a set of metabolic pathways, CoMeta automatically gets the
corresponding data from the KEGG database [
The prototype version of CoMeta presented in [
In [
The new version of CoMeta presented in this paper extends the previous ones with the possibility, for the user, to selectively open the model. The set of potentially open compounds is proposed to the user, who can decide, on the basis of her/his knowledge, which should be the open input and output metabolites. Then, in addition to the internal uxes, potential uxes involving the chosen input/output metabolites will be considered in the comparison. From our experience it is always convenient to open the sources and the sinks in the networks. Hence currently in CoMeta this is the default choice proposed to the user, which is however free to add or remove metabolites as open places.
The paper is organised as follows. In Section 2 we show how a Petri net can model a metabolic pathway in the isolated and open approach. In Section 3 we brie y illustrate the new version of CoMeta and in Section 4 we present some experiments with it. A short conclusion follows in Section 5. 2
PNs are a well known formalism originally introduced in computer science for
modelling discrete concurrent systems. PNs have a sound theory and many
applications both in computer science and in real life systems (see [
Starting with [
When metabolic pathways are represented as Petri nets, we may consider their behavioural aspects as captured by the T-invariants (transition invariants) of the nets which, roughly, represent potential cyclic behaviours in the system. More precisely a T-invariant is a multiset of transitions whose execution starting from a state will bring the system back to the same state. Therefore presence of T-invariants in a metabolic pathway is biologically of great interest as it can reveal the presence of steady states, in which concentrations of substances have reached a possibly dynamic equilibrium.
The set of semi-positive T-invariants of a nite PN N admits a nitary
representation by means of the so-called Hilbert basis [
In a PN model of a metabolic pathway, a minimal T-invariant corresponds to
an elementary ux mode, a term introduced in [
The Petri nets corresponding to the metabolic pathways of an organism are
subnets of a larger net representing its full metabolic network. They can be
considered as isolated subnets, by ignoring their interactions with the
environment, or as open subnets, i.e., interactive subsystems which exchange compounds
with the environment. This is obtained by taking their input/output metabolites
as open places, where the environment can freely put/remove substances. The
minimal T-invariants of these subnets have a clear relation with (minimal)
Tinvariants of the full network. It can be easily seen that modelling the pathway as
an isolated subsystem guarantees correctness: minimal T-invariants of the
pathway are minimal T-invariants of the full network, but they capture only internal
uxes. If, instead, we consider the pathway as an open subsystem, then we get
completeness: any invariant of the full network, once projected onto the
pathway, is an invariant of the open pathway. The converse does not hold, i.e., there
may be invariants of the open pathway which do not correspond to invariants of
the full network. Hence, in the open approach, we may loose correctness, but,
still, as shown in [
As an example, consider the simple Petri net in Fig. 1(a). It has two minimal invariants, namely I1 = fA; C; Eg and I2 = fC; Dg. Note that fB; C; Eg is not an invariant, since B requires two tokens in p1. Assume that the subnet of interest consists of the dark red transitions A, B, C, D (with their preand post-places, i.e., p1, p2 and p3). The isolated representation of this subnet is given in Fig. 1(b). It is obtained by just removing transition E. Note that invariant I2 is still there, while I1 is lost. In the open representation of Fig. 1(c), places p1 and p2 are opened in input and output, respectively, meaning that the environment can put and remove arbitrarily many tokens in such places. This is represented by inserting the transitions in and out. As a consequence, there are three invariants in the open subnet: I2, which was already in the original net, fin; A; C; outg, which is the projection of I1 over the subnet, and f2 in; B; C; outg which, instead, does not correspond to any invariant of the original net.
The present version of CoMeta allows the user to choose either the isolated or the open view, and, in the latter case, to nely tune the representation of the compounds on which the interaction with the environment takes place. 3
CoMeta, (COmparing METAbolic pathways) is a tool for comparing metabolic pathways in di erent organisms relying on their PN representation. The comparison is based on the combination of two distances, a \static" one, dR, taking into account the reactions in the pathways and a \behavioural" one, dI , taking into account potential uxes in the pathways at steady state, as expressed by the T-invariants of the corresponding PNs. Given two pathways represented as PNs, P1 and P2, each distance is derived from a corresponding similarity score: dX (P1; P2) = 1 scoreX (P1; P2), with X 2 fR; Ig.
When computing dR, scoreR(P1; P2) represents the similarity between the
reactions in P1 and the ones in P2. Each reaction is represented by the enzymes
which catalyse it and, in turn, each enzyme is identi ed by its EC number [
When computing dI , the sets of minimal T-invariants (Hilbert bases) B(P1)
and B(P2) of the two nets are compared. Each invariant is represented as a
multiset of EC numbers, corresponding to the reactions in the invariant, and the
similarity between two invariants is given, as before, by a similarity index. The
similarity score is computed through a heuristic match between the two Hilbert
bases and it represents the similarity of the matching pairs. In CoMeta the two
distances may be combined: dC (P1; P2) = dR(P1; P2) + (1 ) dI (P1; P2); with
2 [0; 1], to move the focus between reactions and functional components, and
two organisms can be compared on n metabolic pathways P1; : : : ; Pn by
considering their average distance on the n pathways. More details on the distances
may be found in [
CoMeta is a user-friendly tool written in Java and running under Linux and Mac. CoMeta o ers a set of integrated functionalities through a graphical user interface shown in Figure 2(a). In the upper part of the window the desired KEGG organisms and pathways can be selected. In the lower part a tabbed panel o ers the commands to be performed. The rst tab of the panel is shown in the main window, while the others are shown in Figure 2(b), 2(c), and 2(d), respectively. The main functionalities of the tool are the following ones: (a) CoMeta main window (b) Second tab: Generate PNs (c) Third tab: Compute Distances (d) Fourth tab: Combined Distance { Select organisms and pathways (Figure 2(a)): CoMeta proposes the lists of all KEGG organisms and pathways and allows the user to select the ones to be compared by double-clicking them. { Retrieve KEGG information: CoMeta automatically downloads from the
KEGG database the selected organisms and pathways.
{ Translate into PNs (Figure 2(b)): CoMeta translates the selected
organisms and pathways into corresponding PNs by using the tool MPath2PN [
Currently Cometa o ers the possibility of representing the pathways either
as an isolated or as an open subnet of the full metabolism. The user can
model the pathway as an isolated subsystem and focus only on internal
uxes, or he can consider an open net and choose the open places among the
compounds shared with the rest of the network and the compounds which
are sources/sinks for the pathway. To assist the user, the tool proposes a
canonical choice of open places, namely the sources and the sinks of the
net, but this choice can be modi ed by adding and removing places in the
list of potential open places of the speci c pathway and organism. Figure 3
shows the selectively open window for the organism Vitis vinifera wrt. the
Sulfate metabolism pathway. Note that the rst three checkbox columns in
the window specify which metabolites link to other pathways and which
ones are sources or sinks. By clicking on the checkboxes in the two rightmost
columns the user can select to open in input or in output any metabolite
in the pathway. The canonical choice, sources in input and sinks in output,
automatically selected and proposed to the user, is shown in Figure 3.
{ Compute Distances (Figure 2(c)): dR and dI are computed as previously
described. The user can select either the S rensen or the Tanimoto index. For
computing Hilbert bases CoMeta resorts to 4ti2 [
In this section we discuss some experiments performed with CoMeta in order to illustrate how the choice of the isolated or the open approach may a ect the results of the comparison of metabolic pathways. We consider a small group of organisms and analyse dI , the distance based on T-invariants, with the S rensen index, when modelling the pathways as isolated, fully open and selectively open PNs. By fully open we mean a model in which all potentially open places, namely the ones linking the pathway to the rest of the metabolic network and the ones which are only substrates (sources) or only products (sinks), are indeed open. In the selectively open approach we use the default choice, i.e., we open in input source places by adding an input transition to each source, and we open in output sink places by adding an output transition to each sink.
The following experiments have a common feature: the pathways of the organisms we compare have few reversible reactions and few internal cycles. As a consequence, the comparison of the isolated PN models is not very detailed because of the small number of internal T-invariants and it produces only a rough classi cation of the organisms. On the other hand, by considering fully open models the information on the links among pathways given by KEGG become mostly relevant in the comparison, even if they are imprecise or not so important for distinguihing the speci c functionalities. The classi cation of the organisms results distorted. In such cases, the selectively open approach seems to give the best results in the comparison, in fact it permits to add relevant information to the pathway model without overweighting boundary information. The resulting classi cation is more precise than in the other two approaches. In particular the canonical choice, i.e. opening in input source places and in output sink places, can be used with good results when no special knowledge on the pathway boundary is available. 4.1
Sulfur metabolism pathway The Sulfur metabolism pathway describes the sulfur metabolism, including reduction and xation processes. Sulfur enters in the composition of proteins (amino acids cysteine and methionine) and from the catabolism of these amino acids, it is liberated in the form of hydrogen sulphide (H2S). Bacteria in soils and waters oxidise hydrogen sul de in various steps, to its highest oxidation state sulphate (SO42 ). Algae, Plants and Bacteria are capable to take the sulfur as sulphate and to process it to the most reduced form (sul de) for incorporation into amino acids (cysteine and methionine). Animals are not able to synthesise methionine which is an essential amino acid to be assumed with the diet.
We report here on two di erent experiments performed with Sulfur metabolism. The rst experiment aims at evaluating the ability of dI to discriminate among very di erent groups of organisms. The second experiment aims at checking whether dI is able to identify ne-grained di erences among organisms. First experiment. For this experiment we consider Archaea, Bacteria, Fungi, Plants (that are able to utilise sulfur as sulphate), Birds and Mammals (Animals, other than ruminants, take up sulfate only in reduced form in amino acids). The organisms are therefore expected to show similarity within each group and strong dissimilarity between groups. The list of selected organisms is shown in the following table. Code Organism Reign hsa Homo sapiens Mammals ecb Equus caballus Mammals gga Gallus gallus Birds tgu Taeniopygia guttataa Birds ath Arabidopsis thaliana Plants osa Oryza sativa japonica Plants bdi Brachypodium distachyon Plants n Neosartorya scheri Fungi ang Aspergillus niger Fungi cpw Coccidioides posadasii Fungi cow Caldicellulosiruptor owensensis Bacteria toc Thermosediminibacter oceani Bacteria hsl Halobacterium salinarum R1 Archaea hvo Haloferax volcanii Archaea pto Picrophilus torridus Archaea By using CoMeta, we compute dI , the distance based on T-invariants, for the isolated, selectively open and fully open approaches. The Sulfur metabolism
Top: isolated approach Middle: canonical selectively open approach
Bottom: fully open approach pathway has very small PN models. Depending on the organism, in the isolated models there are at most 9 enzymes/reactions and at most 1 T-invariant, in the fully open models at most 19 enzymes/reactions and 6 invariants and in the canonical selectively open models at most 15 enzymes/reactions and 5 invariants. The selection is among 13 compounds at most.
Figure 4 shows the UPGMA tree corresponding to dI in the isolated (top tree), selectively open (middle tree) and fully open (bottom tree) approaches. Note that in the isolated approach (top tree) Archaea and Bacteria are rst discriminated from Fungi, Plants and Animals. At a second level, two out of three Fungi species are discriminated from Plants and Animals. No other grouping is evident and the classi cation is rather coarse. The selectively open approach (middle tree) discriminates at a rst level the Animals (Mammals and Birds) from other groups. At a lower classi cation level all the three Fungi species are grouped together, as well as the three Plants species and four out of ve Archaea and Bacteria species. Only the Archaea pto is not corectly grouped with the other Archaea (hsl and hvo) and Bacteria (cow, toc). Finally, with the fully open approach (bottom tree) the Archaea and Bacteria groups are not so well de ned as in the previous case, i.e. toc and cow are not grouped together. Hence, in this experiment, the selectively open approach seems to better identify and group together organisms according to major taxonomic groups. Second experiment We consider the Sulfur metabolism and the organisms in the following table.
Code Organism Reign pae Pseudomonas aeruginosa PAO1 Bacteria pfo Pseudomonas uorescens Pf0-1 Bacteria tin Thiomonas intermedia Bacteria tcx Thiomicrospira crunogena Bacteria cpr Clostridium perfringens SM101 Bacteria cst Clostridium stricklandii Bacteria ddn Desulfovibrio desulfuricans ND132 Bacteria vvi Vitis vinifera Plants zma Zea mays Plants For this experiment we select within the Bacteria Reign some species having different sulfur metabolism and playing di erent roles within the bio-geo-chemical cycle of sulfur. The organisms pae and pfo are capable to oxidize elemental sulfur to sulfate. Sulfate can be assimilated by Plants and by Bacteria, such as the Clostridium species considered in the experiment. The sulfate-reducing bacteria, as ddn, are able to reduce sulfate to sulphide and responsible of bio-corrosion. On the contrary, tin and tcx oxidize sulphide back to sulfur. By using CoMeta, we compute dI , the distance based on T-invariants. Figure 5 shows the UPGMA tree corresponding to dI in the isolated (top tree), selectively open (middle tree) and fully open (bottom tree) approaches. Note that with the isolated approach (top tree) Plants, which assimilate sulfur as sulphate from the soil, are classied together with Bacteria (Pseudomonas genus) which are capable of oxidising sulfur to sulphate. On the right side of the tree, decomposing Bacteria (cst and cpr ) are grouped together with other oxidising Bacteria (tcx and tin). The selectively open approach (middle tree) provides a better classi cation, with all the sulphide/sulfur oxidising Bacteria grouped together (tcx and tin; pfo and pae). Desulfovibrio desulfuricans (ddn), a sulfate-reducing Bacteria is also well discriminated, as well as the two Plant species (zma and vvi ), which assimilate sulphate, and the two decomposing Bacteria species (cpr and cst ). The fully open approach (bottom tree) does not provide a well de ned grouping of organisms as in the selectively open approach (e.g., cst and cpr are not grouped together; pae is erroneously grouped with ddn). In this experiment the canonical selectively open approach shows the ability to distinguish organisms at a ne classi cation level. In this case it is able to discriminate organisms belonging to the Bacteria Reign, having di erent ecological roles within the biological sulfur cycle.
Top: isolated approach.
Middle: canonical selectively open approach.
Bottom: fully open approach. Note that, by considering together all the organisms of the two experiments on the Sulfur metabolism the classi cation follows the same pattern: the more detailed classi cation is obtained by using the canonical selectively open approach, the isolated approach produces a rudimentary classi cation and the fully open approach does not produce a well de ned classi cation. We preferred to analyse the two groups separately in order to be able to show more precisely the granularity of the obtained classi cations. 4.2
Carbon
xation pathway In this experiment we consider the pathway Carbon xation in photosynthetic organisms. This cycle consists of a series of reactions that lead to the biosynthesis of carbohydrates in the so called \dark phase" of photosynthesis. In most photosynthetic organisms this cycle is denominated Calvin cycle or reductive pentose-phosphates cycle. Some plants, in relation to environmental adaptations, exhibit speci c variants of this cycle (C4 plants, CAM plants). A peculiarity of this pathway is that it is mainly composed by irreversible reactions.
We consider the organisms in Fig. 6 and we compute dI , with the S rensen index, for the isolated, selectively open and fully open approaches. Depending on the organism, the PN models contain at most 35 enzimes/reactions and 5 invariants in the isolated case, at most 52 enzimes/reactions and 42 invariants in the open case and at most 41 enzimes/reactions and 9 invariants in the canonical selectively open. In the selectively open approach the choice is among at most 34 compounds.
Code Organism Reign gmx Glycine max Plants, Eudicots pop Populus trichocarpa Plants, Eudicots vvi Vitis vinifera Plants, Eudicots osa Oryza sativa japonica Plants, Monocots zma Zea mays Plants, Monocots bdi Brachypodium distachyon Plants, Monocots cre Chlamydomonas reinhardtii Plants, green algae vcn Volvox carteri f. nagariensis Plants, green algae npu Nostoc punctiforme Bacteria acy Anabaena cilindrica Bacteria oni Oscillatoria nigro-viridis Bacteria mar Microcystis aeruginosa Bacteria
Figure 7 shows the UPGMA tree corresponding to dI in the isolated (top tree), canonical selectively open (middle tree) and fully open (bottom tree) approaches. Note that the isolated approach produces a rough classi cation, separating the bacteria from the other organisms. The selectively open approach permits the discrimination among the photosynthetic bacteria. The organism vcn is isolated due to its very simpli ed cycle, with a reduced number of intermediate products and enzymes involved. It is well-known that this genus is a very ancient group of organisms, originated from unicellular organisms. The
Fig. 7. Third experiment: UPGMA trees based on dI wrt. Carbon xation in photosynthetic organisms fully open approach gives similar results to the selectively open one, but it does not group all the photosynthetic Bacteria together (npu is separated from all other organisms). 5
Metabolic pathways are subsystems of the full metabolic network. When
constructing a model of a pathway this fact has to be taken into account and
it requires some choices: the pathway can be represented in isolation or as a
subsystem of the full network, interacting with its environment through some
common compounds. In [