BACKGROUND
in recent years, small- and large-scale experiments have produced a considerable wealth of information about the physical interactions of thousands of molecules.
proteins, in particular, have been reported to interact physically with other proteins, as well as with genes, transcripts and metabolites.
various types of protein-protein interactions  have been documented, ranging from ppi that bring about assembly of stable protein complexes to ppi that cause transient modifications  of target proteins.
retrieving ppi from available databases enables system-level analysis of protein interactomes in various model organisms.
furthermore, suitable tools are available for representing the interactomes, including the ppi networks, which display proteins and ppi as nodes and edges, respectively  <cit> .
in addition to the interactions, also the functions of numerous proteins have been characterized broadly.
evidence about protein function can be retrieved  from the vocabularies of gene ontology , which annotate each protein with its contribution to biological processes, localization to cellular components and performance of molecular functions.
each go vocabulary is hierarchically structured according to ontological relations among the annotations, with the terms ‘biological process’, ‘cellular component’ and ‘molecular function’ being the roots of each graph  <cit> .
to find out which functions are associated with the proteins of a ppi network, a common approach is gene annotation enrichment analysis, which identifies the functional annotations that are significantly more frequent in the ppi network than in a reference set of proteins  <cit> .
however, it is not the purpose of traditional enrichment analysis either to consider the interactions among proteins or to define the relationships among biological functions.
yet, this information is essential to address issues that are better analyzed in functional than molecular terms .
ideally, a graph that represents functions and their hypothetical causal relations  would be useful in designing experiments aimed at testing whether the manipulation of a function  affects other functions.
thus, we devised a method to elaborate ppi networks towards a functional synthesis that might be regarded to as one of the typical goals of systems biology.
actually, mapping relationships among the functions that annotate physically interacting proteins is not an unprecedented attempt  <cit> .
nevertheless, current algorithms for mining biochemical data are not designed to distinguish direct functional relations from functional relations that are mediated by other functions.
in addition, they are not designed to control the level of details of the final representation, which greatly impacts on the represented steps through which a functional relation is obtained.
on the other hand, no systematic analysis has been performed so far, to arrive at a graphical representation of relationships among functions that takes into account the inherent limitations of the evidence exploited.
first and foremost, go annotations refer to functions that are impacted by the manipulation of a gene or a gene product , without referring to how direct the impact is.
second, annotations are heterogeneous with respect to the method, which can be based on experimental evidence, computational inference or author statement.
third, also the experimental assays used for discovering ppi are dissimilar, as ‘binary’ assays  report bona fide direct ppi, whereas ‘cluster’ assays  establish the existence of ppi among all the proteins that belong to the same complex  <cit> .
finally, edges in the ppi networks are often assumed as transitive .
while the assumption is essential to interpret the ppi network as an ordered layout of interacting molecules, it does not exclude the possibility that different copies of the same protein might engage in different ppi.
thus, starting from a ppi network, our goal is to elaborate a graph g = , herein called process graph , where v is a set of function nodes  that indicate biological functions and e is a set of edges that portray relations among functions.
as long as information about the direction of the relations is not available, the relations cannot be characterized fully as ‘causal’, leaving g as an undirected graph rather than a more easily interpretable directed acyclic graph   <cit> .
nevertheless, dependencies can be read off from the whole ensemble of edges even in undirected graphs  <cit> .
for instance, suppose that observing a is irrelevant to make an inference about c, if b is observed.
in this case, to represent the transitivity of these dependencies, a should be graphically linked to b and b to c, but a should not be linked to c. in general, to signify that the presence of a variable makes it irrelevant to observe another variable, a graph must comply with the markov property: all information about a phenomenon is contained in the impact of its adjacent neighbours in the graph  <cit> .
hereafter, we provide the rational basis for automatically inferring such pg representation from the topological information that is included in the ppi network.
given that fn are defined as annotations of proteins and that relationships among proteins are assumed to be transitive, one way to make the pg comply with the markov property is to generate fn that are defined by distinct subsets of proteins without overlaps.
however, as anticipated, the individual proteins are often annotated with several functions, which makes frequent the occurrence of several functions covering the same set of proteins.
to tackle the issue, it was further assumed that a protein the more likely belongs to a fn, the more interactions it has with the other proteins of the fn  <cit> .
on these grounds, topological analysis was applied to discriminate between proteins supporting a function directly and proteins acting through a path of intermediate functions.
this way, by approaching the goal of the markov property, isolated findings can be understood within a coherent representation of the whole biological phenomenon under scrutiny.
to test our method, we have exploited available knowledge about protein interactions and annotations.
as domain of biological interest, we first focused on a cellular component  of the eukaryotic model organism saccharomyces cerevisiae, selected its annotated proteins together with the corresponding ppi network and applied our algorithm to define the relevant pg of peroxisomal functions.
then, to focus on two additional domains, i.e., another cellular component and a biological process, we have applied a similar procedure to other ppi networks composed of yeast proteins that localize to the cellular bud and that contribute to cell budding, respectively.
the choice of well known domains offers the opportunity to exploit additional information about the directionality of causal relations, so that the undirected edges of the pg can be turned into directed edges and be more easily confirmed by the current biological knowledge.
we argue that a successful validation of the pg obtained from well known domains would make a pg obtained from less known domains particularly useful in defining a restricted class of markov equivalent dag  <cit> .
in turn, each dag would correspond to an experimentally testable hypothesis representing a fully causal explanation of the investigated domain  <cit> .
RESULTS
the protein-protein interaction network of the s. cerevisiae peroxisome
to assemble the ppi network of the s. cerevisiae peroxisome, we identified first the peroxisomal core proteins and then their mutual ppi.
in addition, the ppi network was extended to include the first-degree neighbors .
all the proteins of the yeast peroxisome network are listed in additional file  <dig>  while the ppi network is shown in additional file  <dig>
the network consists of  <dig> proteins  and  <dig>  ppi , which have been detected by binary or cluster assays .
the network has average connectivity of  <dig> , average clustering coefficient of  <dig>  and characteristic path length of  <dig> .
together with the protein annotations in go, the ppi network is the starting point to assemble the pg of the yeast peroxisome.
for each assay, the ppi detections are shown as total number and percentage.
the total number of ppi detections exceeds the actual number of ppi , because  <dig> ppi were detected with two methods.
see also additional file  <dig>  and additional file  <dig> .
from protein interactions and annotations to the function nodes
the algorithm initially defines as many fn as are the terms  that are shared by at least two interacting proteins within a ppi network .
this way, several fn are generated, each with a distinct protein content .
frequently, however, a protein is annotated with more terms and is therefore assigned to more fn .
for instance, among the fn of the yeast peroxisome, the nodes that represent membrane assembly  and the docking step of matrix assembly  have distinct protein contents , while the nodes that represent membrane assembly  and inheritance  have a partially overlapping content, i.e., the protein pex3p .
on one side, the multiplicity of annotations per protein may reflect the biological reality, in which the correspondence between functions and structures is commonly not a one-to-one relation.
rather, the same function can be supported by more structures and, conversely, the same structure can be devoted to more functions.
even at the molecular level, the same molecular structure  may participate in different functions, either because one copy of that protein encompasses functionally distinct domains or because more copies of that protein serve distinct functions .
on the other side, most experimental procedures do not reliably guarantee that a function is affected by the annotated protein in a direct way .
in addition, in the hierarchical structure of go, a protein is annotated not only with the specific term that defines a given function, but also with the more general parent terms of that function.
criteria for non-redundant protein-to-function assignment
the algorithm takes several actions to decide whether the multiple annotations of a given protein do reflect its real participation in the annotating functions.
the issue is critical, because redundant protein-to-function assignments would undermine our major aim to comply with the markov property, thus ensuring that the final pg is a coherent and structured representation of functions.
a fairly obvious action is to select the most specific annotation out of a set of hierarchically ordered go terms .
the most important action, however, is to select only plausible inclusions of a protein into the fn, based on the topology of the ppi network .
the rationale is that biological functions are based on the topological organization of their molecular components into modules, i.e., groups of molecules devoted to the same function, which are more densely connected among themselves than with the rest of the network  <cit> .
thus, the algorithm exploits a protein membership score , ranging from 0% to 100%, to measure the plausibility that a protein is member of the protein content of a fn .
specifically, the pms reflects the ability of a fn to discriminate among distinct topological patterns of the ppi network, such as k-cliques  and communities of k-cliques , as defined in  <cit> .
in practice, a protein is excluded from a fn, when another fn better overlaps the topological patterns to which the protein belongs , unless its pms is higher than a previously specified satisfactory threshold .
for instance, the peroxisomal catalase cta1p is annotated with fn that refer to cellular metabolic processes , responses to stress  and responses to chemical stimuli .
however, cta1p is excluded from nodes  <dig> and  <dig>  but retained in node  <dig>  which likely represents the function most directly associated with cta1p .
it should be noted that the procedure reduces, but does not exclude, fn with partly overlapping protein contents.
after these operations, it may happen that more fn have identical protein contents.
in this case, the nodes are merged into one fn, and only the most specific term  is retained as label.
otherwise, if the terms have the same specificity, they are all retained as label, with the resulting fn representing the union of the merged functions .
for instance, the tdh1p-2p-3p isozymes, which originate three fn with identical protein contents, are merged into one fn that retains the two most specific labels , while the most generic term  is excluded.
it is also possible that a protein subset within a fn matches the protein content of another fn.
in this case, the function associated with that protein subset is enucleated from the former fn, which should be viewed as excluding the enucleated function .
for instance, a fn is annotated initially with term go: <dig>  which refers to protein targeting to the peroxisomes .
however, a subset of its proteins  matches the content of the fn annotated with term go: <dig>  which refers to the peroxisomal membrane assembly.
thus, the function of membrane assembly is enucleated from node  <dig> and retained in node  <dig>
in the end, not all the fn have a highly connected protein content.
to focus on functions that correspond to the best defined structures of interacting proteins, each fn is given a node topological score , based on its ability to overlap a k-clique of proteins or a community of k-cliques .
the nts can be exploited to find an optimal threshold, below which a non linear marginal increment occurs in the number of edges or fn in the pg .
adapting the label of the function nodes to their biological meaning
the go terms provide each fn with an initial label.
eventually, however, the label of each fn must be adapted to the functional role of its actual protein content and to its relations with other fn, to ensure specificity of definition .
in general, go terms must be adapted to the protein content of each fn, not only because the fn may undergo several procedures that modify its own original protein content, but also because the ppi network  provides just a partial coverage of the whole interactome of the organism under study .
as an example of the impact of the applied procedure, after enucleation of pex3p and pex19p, the residual protein content of node  <dig> refers more specifically to the translocation of cytosolic enzymes into the peroxisomal matrix.
thus, the original label of node  <dig> ‘protein targeting to peroxisome’  was changed into the new label ‘translocation into the peroxisome matrix’ .
from the function nodes to the process graph
on one hand, fn derive from annotations representing random variables that refer implicitly to an exhaustive set of alternative states, like ‘present’/‘absent’, ‘active’/‘inactive’ or a richer set of values.
therefore, a relation between two fn refers to a possible co-variation of their states.
on the other hand, ppi link proteins that belong to either the same fn  or different fn .
while the former were used for defining the fn, the latter provide information about the mutual relations of the fn.
thus, an edge is initially established between two fn, if they are linked by a crossing ppi, provided that it was detected by a binary assay .
however, while the occurrence of a ppi provides evidence of a biochemical reaction, per se it is not deemed sufficient to infer a relation at a functional level.
actually, to focus on the biochemical reactions that more specifically support the hypothetical link between any two functions, functional links based on only one ppi are discarded .
furthermore, an edge is established between two fn, if they have a partially overlapping protein content.
however, a single shared protein is not deemed sufficient to infer a relation between functions, mostly because more copies of the same protein might independently support the functions .
for instance, no link is established between the fn representing peroxisome fission  and fatty acid oxidation , because the two fn share only the pex11p protein .
hereafter, we provide a description of three pg representations of well known cellular domains to systematically assess their validity.
specifically, each pg is revised to unveil both false and lacking relationships among any two fn, as well as to emphasize the compliance of larger portions of the graph with the markov property.
for a detailed information and biochemical explanations, the reader is referred to the additional file  <dig> and additional file  <dig>
the process graph of the s. cerevisiae peroxisome
the pg of the yeast peroxisome comprises  <dig> fn and  <dig>  edges.
among the fn,  <dig> contain exclusively core proteins,  <dig> exclusively neighbor proteins, while  <dig> contain both core and neighbor proteins.
for ease of analysis, fn have been selected based on nts  and protein type .
specifically, to focus on peroxisome-specific functions, fn were selected with nts ≥  <dig> and a core protein content of at least two thirds.
furthermore, to focus on other functions that may establish relations with the peroxisomal functions, fn were selected with nts ≥  <dig> and a core protein content of no more than one third.
the resulting pg  consists of  <dig> fn  and  <dig> edges .
a process graph-based overview of peroxisome function
a brief description of the peroxisome pg shown in figure  <dig> is provided here, while a detailed analysis can be found in the additional file  <dig>  first, it is known that the metabolic activity of the peroxisomal enzymes must be localized to the peroxisome matrix.
accordingly, the pg portrays the conditions that enable these activities and, in particular, the import of the enzymes from the cytosol  into the peroxisome matrix, i.e., the process of matrix assembly.
specifically, the enzymes are first recognized and bound by receptors in the cytosol , so that the receptor-enzyme complexes can then dock onto the peroxisomal membrane .
in turn, docking allows the translocation of the enzymes into the matrix, across the peroxisomal membrane .
once the enzymes are imported, the receptor is recycled back to the cytosol  for another round of import.
the graph also indicates that matrix assembly depends on membrane assembly, i.e., the insertion of peroxisomal membrane proteins  into the peroxisome membrane .
actually, once inserted, the pmp assemble to form the docking , translocation  and receptor recycling  complexes.
second, membrane assembly  is also required for inserting pmp that mediate peroxisome fission  and inheritance .
fission  refers to the elongation and subsequent division of the organelle, which requires the dynamin dnm1p .
the same division factor is responsible for mitochondrion fission  and is similarly controlled in both peroxisomes and mitochondria .
an unrelated system, which requires the dynamin vps1p, controls selectively fission in peroxisomes .
both division machineries  may influence cell aging .
as most of the fission-related factors must be imported into the peroxisomes, nodes  <dig>   <dig> and  <dig> depend on protein import .
the pg also portrays the dependence of inheritance  on fission .
actually, inheritance is the function whereby peroxisomes, which have been duplicated by fission, are delivered from the mother to the bud cell.
third, the graph also captures regulatory functions, in particular of protein localization and stability.
thus, localization signals  regulate peroxisome fission, by targeting to the peroxisomes regulators of elongation , of dnm1p  and of cortical actin .
also, stability regulation involves the proteasome , with possible effects on peroxisome fission  and matrix assembly .
finally, the pg highlights links between peroxisomes and metabolic functions, including fatty acid oxidation , which depends again on membrane assembly .
in addition, other links, which involve dnm1p regulation , suggest coordinated regulation of peroxisome fission  and glycogen biosynthesis , possibly in response to glucose availability.
presence of dubious edges and absence of expected edges in the peroxisome process graph
some edges portray plausible  dependencies among functions, which call for experimental validation .
few other edges, however, remain of dubious interpretation, as it may occur when a protein, which participates in different functions, is linked to proteins that participate in an additional function.
for instance, pex3p, which participates in membrane assembly  and inheritance , is linked to proteins that participate in docking .
as docking requires membrane assembly , only the edge between nodes  <dig> and  <dig>  seems plausible .
in contrast, some dependencies  are not portrayed by the edges of the pg, as it may occur when information is incomplete about protein interactions and/or annotations.
for instance, concerning the interactions, even though it is established that peroxisomes can be formed from the er , the ppi underlying the er-to-peroxisome connection are incompletely characterized.
as a consequence, no edges in the pg link directly the peroxisomal nodes with node  <dig>  furthermore, concerning the annotations, defective annotation of pex5p with the term go: <dig> results in the absence from the pg of an expected edge linking receptor recycling  with receptor-dependent enzyme recognition , as discussed in additional file  <dig>
formulating experimentally testable hypotheses
suggesting the direction of an edge between any two fn in a pg implies hypothesizing a causal dependence between the two represented functions.
for instance, if node a points to node b, then function b depends on function a. given that the primary source of evidence, i.e., the ppi network, offers several clues on the occurrence, but not the direction of causality, the algorithm elaborates an undirected graph that still requires additional biological knowledge to be fully specified as a directed graph.
when specification of direction would yield directed cycles, standard techniques can be applied to obtain a dag, leading to elimination of recursive relations, by redefining nodes as temporally ordered sequences of variables  <cit> .
converting an undirected graph into a dag requires not only attributing directionality to the undirected edges but also removing those undirected edges that portray dependencies among two or more causal explanations, as long as they are deemed to be merely induced by the observation of common effects  <cit> .
edges, whose direction remains undetermined, originate multiple hypothetical markov equivalent dag, each representing an experimentally testable conjecture.
whether a larger or smaller part of the dag should be exploited to represent the experimental design, is a matter of convenience, as it is not always easy to assess the functional state of some nodes  <cit> .
here, we focus on undirected sub-graphs consisting of three nodes and two edges, which originate four hypothetical and testable dag .
the experimental strategy requires manipulating one of the fn  and assessing the state of the other two fn .
provided that specific manipulation and assessment are both feasible, the result allows selecting one of the possible dag .
the following examples from the peroxisome pg indicate how our approach can be used to plan novel experiments .
first, to confirm the established sequence of events in peroxisome matrix assembly , one might devise an experiment consisting of the manipulation  of docking , which is expected to affect translocation , while leaving enzyme recognition  unaffected.
second, other experiments might be conceived to test the likely dependence of peroxisomal receptor recycling and fatty acid oxidation on membrane assembly .
in this case, available data might be used to corroborate the experimental design.
actually, manipulation of membrane assembly , for instance by null mutation of pex <dig>  primarily results in cytosolic mislocalization of several pmp, including pex15p  <cit> , which mediates receptor recycling .
similarly, null mutation of pex <dig>  affects fatty acid oxidation , possibly by altering localization of the pmp pex11p  <cit> .
conversely, manipulation of nodes  <dig> and  <dig>  leaves pmp localization unaffected  <cit> , thus strengthening the likely dependence of nodes  <dig> and  <dig> on node  <dig>  third, other experiments might be devised to test the hypothetical dependence of the vps1p-mediated fission of peroxisomes on the dnm1p-mediated fission of both peroxisomes and mitochondria .
in partial support of this hypothesis, known genetic interactions  already suggest dependences among the fission-related fn.
specifically, manipulation of vps1p-dependent fission , by means of vps1p over-expression, does not restore the fission defects  of dnm <dig> mutants, whereas manipulation of nodes  <dig> and  <dig>  by means of dnm1p over-expression, does restore the fission defect of peroxisomes in vps <dig> mutants  <cit> .
process graph-based overview of the cellular bud
lastly, in addition to the peroxisome, we have applied our method to other examples of ppi networks in the budding yeast.
the proteins in these networks either localize to the cellular bud  or participate in the process of cell budding .
from a ppi network composed of  <dig> ppi and  <dig> proteins with the annotation ‘cellular bud’ , a pg of  <dig> fn and  <dig> edges is generated.
setting a threshold nts ≥  <dig> produces a pg of  <dig> fn and  <dig> edges , which is described briefly here .
the pg represents functions that take place at the cellular bud in association with the polarization of the mother cell .
specifically, the cdc42p-mediated establishment of polarity , which depends on the selection of the bud site , activates in turn a kinase-based centre of regulation for polarity-related responses , such as cytoskeleton remodelling along the mother-bud axis , ring formation at the bud neck  and cell division .
first, polarity induces both spindle reorientation and actin organization , so that actin may assemble into filaments , which in turn favours polarized transport to the bud .
transport also depends on the polarisome  and on actin bundling  for the correct orientation and strengthening of the filaments, respectively.
second, polarity, via the phosphorylation of septins, induces the assembly of a septin-based contractile ring around the neck of the bud .
third, the pg shows that polarity is coordinated with the cell cycle in several ways.
on one side, in g <dig> phase, polarity depends on the cell cycle, because cdc28p  inactivates the cdc42p inhibitor rga2p .
on the other side, in late g2/m phase, the cell cycle depends on polarity to allow entry in mitosis, because the cdc42p effector cla4p  induces phosphorylation-mediated degradation of the cdc28p inhibitor swe1p .
the pg also shows that the cell cycle is regulated by polarity-related checkpoints for septin ring organization , spindle assembly  and spindle alignment .
other accessory functions, such as dna replication  and cell wall remodelling  are also shown.
process graph-based overview of cell budding
from a ppi network composed of  <dig> ppi and  <dig> proteins with the annotation ‘cell budding’ , a pg of  <dig> fn and  <dig> edges is generated.
setting a threshold nts ≥  <dig> produces a pg of  <dig> fn and  <dig> edges, which is fragmented into three clusters.
the domain represented by the largest cluster  is shown in figure 5b and described briefly here .
the pg represents one of the key events of cell budding  as a fn , together with its dependence on other fn, which are related to the underlying mechanisms of transport.
first, polarized transport of vesicles  depends on the fusion of post-golgi exocytic vesicles with the plasma membrane , as well as on the establishment of a specific site of fusion at the plasma membrane, where the exocyst complex localizes .
exocyst localization depends on the cdc42p-mediated establishment of polarity , which depends on upstream regulators .
in turn, polarity establishment  regulates other budding-related responses, such as the assembly of a septin-based ring around the bud neck .
second, polarized transport of organelles requires the formation of polymeric actin cables along the mother-bud axis and their anchoring at a cortical actin patch in the bud.
specifically, nucleation of actin monomers  depends on the assembly of the polarisome complex at the site of bud emergence .
then, actin polymerization induces the assembly of both actin bundles  and a patch of cortical actin .
the patch also depends on additional upstream regulators , as well as on the growth of the bud , which in turn depends on membrane fusion events .
finally, these actin structures enable the polarized transport .
given that polarity establishment is known to induce actin polarization  <cit> , an edge from node  <dig> to node  <dig> , as well as an edge from node  <dig> to node  <dig>  was expected.
the edge, however, cannot be but missing, since polarity-dependent regulators of actin, like arp2p , were not annotated with the polarity-related go terms used to select the proteins of the ppi networks, despite the fact that arp2p is an effector of the polarity regulator las17p  <cit> .
this observation might suggest the usefulness of extending the ppi selection to the first degree neighbours of the core proteins of the domain of interest, as likely means to reducing missing annotations, even though the extension likely increases the density of the edges in the pg .
discussion
this method combines information on the interactions and functions of the proteins that belong to a domain of biological interest , with the goal of converting a functionally annotated ppi network into a pg, i.e., a compact and coherently structured representation of dependencies among biological functions.
the goal is challenging, as available information about the protein-to-function relations does not guarantee that a protein under examination does indeed participate directly in the annotated function.
as edges between functions are based on the ppi among the proteins that these functions annotate, it follows that redundant protein-to-function assignment inevitably produces redundant edges among the corresponding fn.
thus, throughout the study, it has been our main concern to ensure that a direct edge between two fn could be established, only if intermediate functions were unlikely to occur.
otherwise, the resulting pg would be a mere assembly of coupled functions and not a coherent and compact representation of the way functions cooperate in supporting complex biological activities.
in addition, a redundant pg would be of limited usefulness for planning the smallest set of experimental interventions that can be made on a function, when one desires to impact on target functions.
to achieve compact representations, we took the following considerations into account.
first, fn are expected to map onto a ppi network the correspondence between proteins and annotations.
second, such mapping is expected to represent the most extensive coverage of the ppi network with the least degree of overlap between fn, provided that one can exclude the annotations of those proteins that support only indirectly the annotated functions.
third, molecules more typically contribute to biological functions as highly inter-connected  assemblies, rather than as unconnected elements  <cit> .
within ppi networks, for instance, functional and topological modules display significant overlap  <cit> .
thus, based on these considerations, the algorithm we have devised introduces a topologically-driven prioritization that selects only plausible inclusions of a protein into a fn, as quantified by its pms, i.e., a score that reflects the ability of a fn to discriminate among the topological patterns of the ppi network, to which the protein belongs.
the method has been applied to two cellular components  and one biological process  in s. cerevisiae, which are well characterized domains and thus suitable for validation purposes.
on one hand, well characterized causal dependencies among functions  have confirmed that the method specifically highlights important relations.
on the other hand, less obvious dependencies  have revealed the heuristic power of this method and its usefulness in formulating testable hypotheses.
it should be noted that the peroxisome-centered ppi network has been extended to the first neighbors of the peroxisome core proteins, because we wanted to highlight the wider biological landscape that ideally surrounds the organelle.
the inclusion of non-peroxisomal proteins is justified by the observation that almost half of the core proteins are annotated  with terms related not only to the peroxisome but also to mitochondrion, er and nucleus , the organelles that interact functionally with the peroxisome  <cit> .
clearly, some multiple annotations of the same protein simply refer to the existence of sub-cellular distinct  pools, such as the peroxisomal and nuclear pools of the dynamin dyn2p.
nevertheless, other multiple annotations suggest that a protein may change its sub-cellular location, at least under specific conditions.
for instance, pex11p relocates from the er to the peroxisome, when peroxisomes are induce to proliferate in response to oleate  <cit> .
numerous studies have analyzed the relation between molecules and functions.
in particular, one of the major aims of many bioinformatics studies has been to infer the function of uncharacterized genes based on comparisons with characterized genes, such as sequence similarity  <cit> , co-occurrence in genomic clusters  <cit> , co-evolution in different species  <cit>  and co-expression patterns  <cit> .
also the ppi have been used to infer the function of uncharacterized proteins, based on the most frequent annotations of their protein interactors  <cit> .
like these ‘guilt by association’ methods, also our approach builds on the assumption that proteins often interact mutually to contribute to the same function.
furthermore, all these studies  deploy a non-directional annotated network as input, sometimes designed ‘functional linkage network’  <cit> , in which nodes correspond to molecules, while edges correspond to different types of functional connection between molecules  <cit> .
few studies, however, have moved beyond the immediate aim of inferring protein-function binary associations to the ultimate aim of inferring structured dependencies among functions, which can be displayed in a markov graph of connected functions.
an earlier study established a link between a given pair of functions, anytime a ppi had been detected between the proteins annotated with the two functions  <cit> .
a more recent study has elaborated on this method, by selecting statistically enriched pairs of functions, as defined by the probability that two sets of proteins  establish more ppi between themselves than it can be expected by chance  <cit> .
our method differs considerably from these earlier studies, as it retains any annotation that is shared by two interacting proteins within the ppi network, leaving to the topological analysis the task to define the fn, whose relationships may satisfy the markov property.
this way, the selected and prioritized protein assignments to the fn are expected to refer truly to the functions that are directly impacted by the protein.
as an example of how our approach differs from the previous studies, consider a 3-node sub-graph composed of fn related to the go functional annotations of protein import , pmp insertion into the peroxisome membrane  and peroxisome organization .
while a previous study linked the three nodes with three edges  <cit> , our algorithm establishes only two edges , but not the edge between nodes  <dig> and  <dig>  because it would violate the markov assumption, given that protein import  contributes to peroxisome organization  only indirectly, i.e., by enabling pmp insertion .
furthermore, our study also contrasts with an important implication of the earlier study, which advocated re-engineering the go database by complementing the go hierarchy with the links inferred from the functional linkage graphs  <cit> .
alternatively, we propose to adapt the semantics of the go annotations to the level of detail that characterizes the domain of interest, mostly based on the real protein content of the fn.
a more detailed comparison of graphs that represent similar domains but are obtained with different methods can be found in additional file  <dig>
clearly, our method can be applied to different domains of biological interest in different model organisms, even though some words of caution should be added.
first and foremost, inaccurate and/or defective datasets of protein interactions and functions will certainly affect the quality of the pg representation.
in our experience with s. cerevisiae, even after revising carefully the pg, we found just a limited number of false positives and false negatives.
nevertheless, we cannot exclude that results might be less accurate, should the algorithm be applied to other organisms that are not so extensively and accurately characterized as the budding yeast.
second, other features of the starting ppi network should be taken into account, including the choice of a cell type-specific repertoire of proteins  and the size of the ppi .
third, it should be pointed out that labor-intensive analysis is required to verify the consistency of the pg with current biological knowledge and to define the causal directionality of its undirected edges.
it should also be taken into account that just a minor fraction of the physical interactions that are reported in the ppi databases have an annotation of biochemical directionality .
for instance, out of  <dig>  ppi reported as ‘physical interactions’ in the  <dig> .
<dig> release of biogrid, more than 94% of ppi  has no annotation.
only less than 6% of the remaining ppi has the annotation ‘phosphorylation’ or other types of modifications.
furthermore, in many of these cases, the annotated modification has been detected in a biochemical assay without functional characterization.
finally, many ppi refer to physical interactions that are non-directional in nature .
in conclusion, with all the caveats related to incomplete knowledge, the herein reported data suggest that, even when the ppi structures that underlie a function are only partially known, it is nevertheless possible to regard functions as black boxes with only known inputs and outputs, to obtain non-redundant graphical representations of complex biological systems.
in addition, our efforts indicate that the graph we obtain can be helpful in carefully designing experimental studies, provided that specific manipulation and measurement of the portrayed functions are feasible.
CONCLUSIONS
the major problem with the idea of converting ppi networks  into pg  is that several proteins have multiple annotations.
faced with this challenge, we reasoned that the final pg could be non-redundant, if only the proteins that participate directly in a given function are included in the related fn.
furthermore, we surmised that topological features  might help approaching structured and non-redundant understanding of molecular function.
thus, an algorithm was developed that prioritizes inclusion of proteins into the fn that best overlap protein clusters.
specifically, the algorithm identifies fn , based on the topological analysis of the starting ppi network.
applying the algorithm to different domains of biological interest  has shown that the method is suitable for formulating testable and mechanistic hypotheses about the existence of dependencies among functions.

 in recent years, small- and large-scale experiments have produced a considerable wealth of information about the physical interactions of thousands of molecules. proteins, in particular, have been reported to interact physically with other proteins, as well as with genes, transcripts and metabolites. various types of protein-protein interactions have been documented, ranging from ppi that bring about assembly of stable protein complexes to ppi that cause transient modifications of target proteins. retrieving ppi from available databases enables system-level analysis of protein interactomes in various model organisms. furthermore, suitable tools are available for representing the interactomes, including the ppi networks, which display proteins and ppi as nodes and edges, respectively. in addition to the interactions, also the functions of numerous proteins have been characterized broadly. evidence about protein function can be retrieved from the vocabularies of gene ontology, which annotate each protein with its contribution to biological processes, localization to cellular components and performance of molecular functions. each go vocabulary is hierarchically structured according to ontological relations among the annotations, with the terms ‘biological process’, ‘cellular component’ and ‘molecular function’ being the roots of each graph. to find out which functions are associated with the proteins of a ppi network, a common approach is gene annotation enrichment analysis, which identifies the functional annotations that are significantly more frequent in the ppi network than in a reference set of proteins. however, it is not the purpose of traditional enrichment analysis either to consider the interactions among proteins or to define the relationships among biological functions. yet, this information is essential to address issues that are better analyzed in functional than molecular terms. ideally, a graph that represents functions and their hypothetical causal relations would be useful in designing experiments aimed at testing whether the manipulation of a function affects other functions. thus, we devised a method to elaborate ppi networks towards a functional synthesis that might be regarded to as one of the typical goals of systems biology. actually, mapping relationships among the functions that annotate physically interacting proteins is not an unprecedented attempt. nevertheless, current algorithms for mining biochemical data are not designed to distinguish direct functional relations from functional relations that are mediated by other functions. in addition, they are not designed to control the level of details of the final representation, which greatly impacts on the represented steps through which a functional relation is obtained. on the other hand, no systematic analysis has been performed so far, to arrive at a graphical representation of relationships among functions that takes into account the inherent limitations of the evidence exploited. first and foremost, go annotations refer to functions that are impacted by the manipulation of a gene or a gene product, without referring to how direct the impact is. second, annotations are heterogeneous with respect to the method, which can be based on experimental evidence, computational inference or author statement. third, also the experimental assays used for discovering ppi are dissimilar, as ‘binary’ assays report bona fide direct ppi, whereas ‘cluster’ assays establish the existence of ppi among all the proteins that belong to the same complex. finally, edges in the ppi networks are often assumed as transitive. while the assumption is essential to interpret the ppi network as an ordered layout of interacting molecules, it does not exclude the possibility that different copies of the same protein might engage in different ppi. thus, starting from a ppi network, our goal is to elaborate a graph g =, herein called process graph, where v is a set of function nodes that indicate biological functions and e is a set of edges that portray relations among functions. as long as information about the direction of the relations is not available, the relations cannot be characterized fully as ‘causal’, leaving g as an undirected graph rather than a more easily interpretable directed acyclic graph. nevertheless, dependencies can be read off from the whole ensemble of edges even in undirected graphs. for instance, suppose that observing a is irrelevant to make an inference about c, if b is observed. in this case, to represent the transitivity of these dependencies, a should be graphically linked to b and b to c, but a should not be linked to c. in general, to signify that the presence of a variable makes it irrelevant to observe another variable, a graph must comply with the markov property: all information about a phenomenon is contained in the impact of its adjacent neighbours in the graph. hereafter, we provide the rational basis for automatically inferring such pg representation from the topological information that is included in the ppi network. given that fn are defined as annotations of proteins and that relationships among proteins are assumed to be transitive, one way to make the pg comply with the markov property is to generate fn that are defined by distinct subsets of proteins without overlaps. however, as anticipated, the individual proteins are often annotated with several functions, which makes frequent the occurrence of several functions covering the same set of proteins. to tackle the issue, it was further assumed that a protein the more likely belongs to a fn, the more interactions it has with the other proteins of the fn. on these grounds, topological analysis was applied to discriminate between proteins supporting a function directly and proteins acting through a path of intermediate functions. this way, by approaching the goal of the markov property, isolated findings can be understood within a coherent representation of the whole biological phenomenon under scrutiny. to test our method, we have exploited available knowledge about protein interactions and annotations. as domain of biological interest, we first focused on a cellular component of the eukaryotic model organism saccharomyces cerevisiae, selected its annotated proteins together with the corresponding ppi network and applied our algorithm to define the relevant pg of peroxisomal functions. then, to focus on two additional domains, i.e., another cellular component and a biological process, we have applied a similar procedure to other ppi networks composed of yeast proteins that localize to the cellular bud and that contribute to cell budding, respectively. the choice of well known domains offers the opportunity to exploit additional information about the directionality of causal relations, so that the undirected edges of the pg can be turned into directed edges and be more easily confirmed by the current biological knowledge. we argue that a successful validation of the pg obtained from well known domains would make a pg obtained from less known domains particularly useful in defining a restricted class of markov equivalent dag. in turn, each dag would correspond to an experimentally testable hypothesis representing a fully causal explanation of the investigated domain.  the protein-protein interaction network of the s. cerevisiae peroxisome to assemble the ppi network of the s. cerevisiae peroxisome, we identified first the peroxisomal core proteins and then their mutual ppi. in addition, the ppi network was extended to include the first-degree neighbors. all the proteins of the yeast peroxisome network are listed in additional file while the ppi network is shown in additional file the network consists of proteins and ppi, which have been detected by binary or cluster assays. the network has average connectivity of, average clustering coefficient of and characteristic path length of. together with the protein annotations in go, the ppi network is the starting point to assemble the pg of the yeast peroxisome. for each assay, the ppi detections are shown as total number and percentage. the total number of ppi detections exceeds the actual number of ppi, because ppi were detected with two methods. see also additional file and additional file. from protein interactions and annotations to the function nodes the algorithm initially defines as many fn as are the terms that are shared by at least two interacting proteins within a ppi network. this way, several fn are generated, each with a distinct protein content. frequently, however, a protein is annotated with more terms and is therefore assigned to more fn. for instance, among the fn of the yeast peroxisome, the nodes that represent membrane assembly and the docking step of matrix assembly have distinct protein contents, while the nodes that represent membrane assembly and inheritance have a partially overlapping content, i.e., the protein pex3p. on one side, the multiplicity of annotations per protein may reflect the biological reality, in which the correspondence between functions and structures is commonly not a one-to-one relation. rather, the same function can be supported by more structures and, conversely, the same structure can be devoted to more functions. even at the molecular level, the same molecular structure may participate in different functions, either because one copy of that protein encompasses functionally distinct domains or because more copies of that protein serve distinct functions. on the other side, most experimental procedures do not reliably guarantee that a function is affected by the annotated protein in a direct way. in addition, in the hierarchical structure of go, a protein is annotated not only with the specific term that defines a given function, but also with the more general parent terms of that function. criteria for non-redundant protein-to-function assignment the algorithm takes several actions to decide whether the multiple annotations of a given protein do reflect its real participation in the annotating functions. the issue is critical, because redundant protein-to-function assignments would undermine our major aim to comply with the markov property, thus ensuring that the final pg is a coherent and structured representation of functions. a fairly obvious action is to select the most specific annotation out of a set of hierarchically ordered go terms. the most important action, however, is to select only plausible inclusions of a protein into the fn, based on the topology of the ppi network. the rationale is that biological functions are based on the topological organization of their molecular components into modules, i.e., groups of molecules devoted to the same function, which are more densely connected among themselves than with the rest of the network. thus, the algorithm exploits a protein membership score, ranging from 0% to 100%, to measure the plausibility that a protein is member of the protein content of a fn. specifically, the pms reflects the ability of a fn to discriminate among distinct topological patterns of the ppi network, such as k-cliques and communities of k-cliques, as defined in. in practice, a protein is excluded from a fn, when another fn better overlaps the topological patterns to which the protein belongs, unless its pms is higher than a previously specified satisfactory threshold. for instance, the peroxisomal catalase cta1p is annotated with fn that refer to cellular metabolic processes, responses to stress and responses to chemical stimuli. however, cta1p is excluded from nodes and but retained in node which likely represents the function most directly associated with cta1p. it should be noted that the procedure reduces, but does not exclude, fn with partly overlapping protein contents. after these operations, it may happen that more fn have identical protein contents. in this case, the nodes are merged into one fn, and only the most specific term is retained as label. otherwise, if the terms have the same specificity, they are all retained as label, with the resulting fn representing the union of the merged functions. for instance, the tdh1p-2p-3p isozymes, which originate three fn with identical protein contents, are merged into one fn that retains the two most specific labels, while the most generic term is excluded. it is also possible that a protein subset within a fn matches the protein content of another fn. in this case, the function associated with that protein subset is enucleated from the former fn, which should be viewed as excluding the enucleated function. for instance, a fn is annotated initially with term go: which refers to protein targeting to the peroxisomes. however, a subset of its proteins matches the content of the fn annotated with term go: which refers to the peroxisomal membrane assembly. thus, the function of membrane assembly is enucleated from node and retained in node in the end, not all the fn have a highly connected protein content. to focus on functions that correspond to the best defined structures of interacting proteins, each fn is given a node topological score, based on its ability to overlap a k-clique of proteins or a community of k-cliques. the nts can be exploited to find an optimal threshold, below which a non linear marginal increment occurs in the number of edges or fn in the pg. adapting the label of the function nodes to their biological meaning the go terms provide each fn with an initial label. eventually, however, the label of each fn must be adapted to the functional role of its actual protein content and to its relations with other fn, to ensure specificity of definition. in general, go terms must be adapted to the protein content of each fn, not only because the fn may undergo several procedures that modify its own original protein content, but also because the ppi network provides just a partial coverage of the whole interactome of the organism under study. as an example of the impact of the applied procedure, after enucleation of pex3p and pex19p, the residual protein content of node refers more specifically to the translocation of cytosolic enzymes into the peroxisomal matrix. thus, the original label of node ‘protein targeting to peroxisome’ was changed into the new label ‘translocation into the peroxisome matrix’. from the function nodes to the process graph on one hand, fn derive from annotations representing random variables that refer implicitly to an exhaustive set of alternative states, like ‘present’/‘absent’, ‘active’/‘inactive’ or a richer set of values. therefore, a relation between two fn refers to a possible co-variation of their states. on the other hand, ppi link proteins that belong to either the same fn or different fn. while the former were used for defining the fn, the latter provide information about the mutual relations of the fn. thus, an edge is initially established between two fn, if they are linked by a crossing ppi, provided that it was detected by a binary assay. however, while the occurrence of a ppi provides evidence of a biochemical reaction, per se it is not deemed sufficient to infer a relation at a functional level. actually, to focus on the biochemical reactions that more specifically support the hypothetical link between any two functions, functional links based on only one ppi are discarded. furthermore, an edge is established between two fn, if they have a partially overlapping protein content. however, a single shared protein is not deemed sufficient to infer a relation between functions, mostly because more copies of the same protein might independently support the functions. for instance, no link is established between the fn representing peroxisome fission and fatty acid oxidation, because the two fn share only the pex11p protein. hereafter, we provide a description of three pg representations of well known cellular domains to systematically assess their validity. specifically, each pg is revised to unveil both false and lacking relationships among any two fn, as well as to emphasize the compliance of larger portions of the graph with the markov property. for a detailed information and biochemical explanations, the reader is referred to the additional file and additional file the process graph of the s. cerevisiae peroxisome the pg of the yeast peroxisome comprises fn and edges. among the fn, contain exclusively core proteins, exclusively neighbor proteins, while contain both core and neighbor proteins. for ease of analysis, fn have been selected based on nts and protein type. specifically, to focus on peroxisome-specific functions, fn were selected with nts ≥  and a core protein content of at least two thirds. furthermore, to focus on other functions that may establish relations with the peroxisomal functions, fn were selected with nts ≥  and a core protein content of no more than one third. the resulting pg consists of fn and edges. a process graph-based overview of peroxisome function a brief description of the peroxisome pg shown in figure is provided here, while a detailed analysis can be found in the additional file first, it is known that the metabolic activity of the peroxisomal enzymes must be localized to the peroxisome matrix. accordingly, the pg portrays the conditions that enable these activities and, in particular, the import of the enzymes from the cytosol into the peroxisome matrix, i.e., the process of matrix assembly. specifically, the enzymes are first recognized and bound by receptors in the cytosol, so that the receptor-enzyme complexes can then dock onto the peroxisomal membrane. in turn, docking allows the translocation of the enzymes into the matrix, across the peroxisomal membrane. once the enzymes are imported, the receptor is recycled back to the cytosol for another round of import. the graph also indicates that matrix assembly depends on membrane assembly, i.e., the insertion of peroxisomal membrane proteins into the peroxisome membrane. actually, once inserted, the pmp assemble to form the docking, translocation and receptor recycling complexes. second, membrane assembly is also required for inserting pmp that mediate peroxisome fission and inheritance. fission refers to the elongation and subsequent division of the organelle, which requires the dynamin dnm1p. the same division factor is responsible for mitochondrion fission and is similarly controlled in both peroxisomes and mitochondria. an unrelated system, which requires the dynamin vps1p, controls selectively fission in peroxisomes. both division machineries may influence cell aging. as most of the fission-related factors must be imported into the peroxisomes, nodes and depend on protein import. the pg also portrays the dependence of inheritance on fission. actually, inheritance is the function whereby peroxisomes, which have been duplicated by fission, are delivered from the mother to the bud cell. third, the graph also captures regulatory functions, in particular of protein localization and stability. thus, localization signals regulate peroxisome fission, by targeting to the peroxisomes regulators of elongation, of dnm1p and of cortical actin. also, stability regulation involves the proteasome, with possible effects on peroxisome fission and matrix assembly. finally, the pg highlights links between peroxisomes and metabolic functions, including fatty acid oxidation, which depends again on membrane assembly. in addition, other links, which involve dnm1p regulation, suggest coordinated regulation of peroxisome fission and glycogen biosynthesis, possibly in response to glucose availability. presence of dubious edges and absence of expected edges in the peroxisome process graph some edges portray plausible dependencies among functions, which call for experimental validation. few other edges, however, remain of dubious interpretation, as it may occur when a protein, which participates in different functions, is linked to proteins that participate in an additional function. for instance, pex3p, which participates in membrane assembly and inheritance, is linked to proteins that participate in docking. as docking requires membrane assembly, only the edge between nodes and seems plausible. in contrast, some dependencies are not portrayed by the edges of the pg, as it may occur when information is incomplete about protein interactions and/or annotations. for instance, concerning the interactions, even though it is established that peroxisomes can be formed from the er, the ppi underlying the er-to-peroxisome connection are incompletely characterized. as a consequence, no edges in the pg link directly the peroxisomal nodes with node furthermore, concerning the annotations, defective annotation of pex5p with the term go: results in the absence from the pg of an expected edge linking receptor recycling with receptor-dependent enzyme recognition, as discussed in additional file formulating experimentally testable hypotheses suggesting the direction of an edge between any two fn in a pg implies hypothesizing a causal dependence between the two represented functions. for instance, if node a points to node b, then function b depends on function a. given that the primary source of evidence, i.e., the ppi network, offers several clues on the occurrence, but not the direction of causality, the algorithm elaborates an undirected graph that still requires additional biological knowledge to be fully specified as a directed graph. when specification of direction would yield directed cycles, standard techniques can be applied to obtain a dag, leading to elimination of recursive relations, by redefining nodes as temporally ordered sequences of variables. converting an undirected graph into a dag requires not only attributing directionality to the undirected edges but also removing those undirected edges that portray dependencies among two or more causal explanations, as long as they are deemed to be merely induced by the observation of common effects. edges, whose direction remains undetermined, originate multiple hypothetical markov equivalent dag, each representing an experimentally testable conjecture. whether a larger or smaller part of the dag should be exploited to represent the experimental design, is a matter of convenience, as it is not always easy to assess the functional state of some nodes. here, we focus on undirected sub-graphs consisting of three nodes and two edges, which originate four hypothetical and testable dag. the experimental strategy requires manipulating one of the fn and assessing the state of the other two fn. provided that specific manipulation and assessment are both feasible, the result allows selecting one of the possible dag. the following examples from the peroxisome pg indicate how our approach can be used to plan novel experiments. first, to confirm the established sequence of events in peroxisome matrix assembly, one might devise an experiment consisting of the manipulation of docking, which is expected to affect translocation, while leaving enzyme recognition unaffected. second, other experiments might be conceived to test the likely dependence of peroxisomal receptor recycling and fatty acid oxidation on membrane assembly. in this case, available data might be used to corroborate the experimental design. actually, manipulation of membrane assembly, for instance by null mutation of pex primarily results in cytosolic mislocalization of several pmp, including pex15p, which mediates receptor recycling. similarly, null mutation of pex affects fatty acid oxidation, possibly by altering localization of the pmp pex11p. conversely, manipulation of nodes and leaves pmp localization unaffected, thus strengthening the likely dependence of nodes and on node third, other experiments might be devised to test the hypothetical dependence of the vps1p-mediated fission of peroxisomes on the dnm1p-mediated fission of both peroxisomes and mitochondria. in partial support of this hypothesis, known genetic interactions already suggest dependences among the fission-related fn. specifically, manipulation of vps1p-dependent fission, by means of vps1p over-expression, does not restore the fission defects of dnm mutants, whereas manipulation of nodes and by means of dnm1p over-expression, does restore the fission defect of peroxisomes in vps mutants. process graph-based overview of the cellular bud lastly, in addition to the peroxisome, we have applied our method to other examples of ppi networks in the budding yeast. the proteins in these networks either localize to the cellular bud or participate in the process of cell budding. from a ppi network composed of ppi and proteins with the annotation ‘cellular bud’, a pg of fn and edges is generated. setting a threshold nts ≥  produces a pg of fn and edges, which is described briefly here. the pg represents functions that take place at the cellular bud in association with the polarization of the mother cell. specifically, the cdc42p-mediated establishment of polarity, which depends on the selection of the bud site, activates in turn a kinase-based centre of regulation for polarity-related responses, such as cytoskeleton remodelling along the mother-bud axis, ring formation at the bud neck and cell division. first, polarity induces both spindle reorientation and actin organization, so that actin may assemble into filaments, which in turn favours polarized transport to the bud. transport also depends on the polarisome and on actin bundling for the correct orientation and strengthening of the filaments, respectively. second, polarity, via the phosphorylation of septins, induces the assembly of a septin-based contractile ring around the neck of the bud. third, the pg shows that polarity is coordinated with the cell cycle in several ways. on one side, in g phase, polarity depends on the cell cycle, because cdc28p inactivates the cdc42p inhibitor rga2p. on the other side, in late g2/m phase, the cell cycle depends on polarity to allow entry in mitosis, because the cdc42p effector cla4p induces phosphorylation-mediated degradation of the cdc28p inhibitor swe1p. the pg also shows that the cell cycle is regulated by polarity-related checkpoints for septin ring organization, spindle assembly and spindle alignment. other accessory functions, such as dna replication and cell wall remodelling are also shown. process graph-based overview of cell budding from a ppi network composed of ppi and proteins with the annotation ‘cell budding’, a pg of fn and edges is generated. setting a threshold nts ≥  produces a pg of fn and edges, which is fragmented into three clusters. the domain represented by the largest cluster is shown in figure 5b and described briefly here. the pg represents one of the key events of cell budding as a fn, together with its dependence on other fn, which are related to the underlying mechanisms of transport. first, polarized transport of vesicles depends on the fusion of post-golgi exocytic vesicles with the plasma membrane, as well as on the establishment of a specific site of fusion at the plasma membrane, where the exocyst complex localizes. exocyst localization depends on the cdc42p-mediated establishment of polarity, which depends on upstream regulators. in turn, polarity establishment regulates other budding-related responses, such as the assembly of a septin-based ring around the bud neck. second, polarized transport of organelles requires the formation of polymeric actin cables along the mother-bud axis and their anchoring at a cortical actin patch in the bud. specifically, nucleation of actin monomers depends on the assembly of the polarisome complex at the site of bud emergence. then, actin polymerization induces the assembly of both actin bundles and a patch of cortical actin. the patch also depends on additional upstream regulators, as well as on the growth of the bud, which in turn depends on membrane fusion events. finally, these actin structures enable the polarized transport. given that polarity establishment is known to induce actin polarization, an edge from node to node, as well as an edge from node to node was expected. the edge, however, cannot be but missing, since polarity-dependent regulators of actin, like arp2p, were not annotated with the polarity-related go terms used to select the proteins of the ppi networks, despite the fact that arp2p is an effector of the polarity regulator las17p. this observation might suggest the usefulness of extending the ppi selection to the first degree neighbours of the core proteins of the domain of interest, as likely means to reducing missing annotations, even though the extension likely increases the density of the edges in the pg. discussion this method combines information on the interactions and functions of the proteins that belong to a domain of biological interest, with the goal of converting a functionally annotated ppi network into a pg, i.e., a compact and coherently structured representation of dependencies among biological functions. the goal is challenging, as available information about the protein-to-function relations does not guarantee that a protein under examination does indeed participate directly in the annotated function. as edges between functions are based on the ppi among the proteins that these functions annotate, it follows that redundant protein-to-function assignment inevitably produces redundant edges among the corresponding fn. thus, throughout the study, it has been our main concern to ensure that a direct edge between two fn could be established, only if intermediate functions were unlikely to occur. otherwise, the resulting pg would be a mere assembly of coupled functions and not a coherent and compact representation of the way functions cooperate in supporting complex biological activities. in addition, a redundant pg would be of limited usefulness for planning the smallest set of experimental interventions that can be made on a function, when one desires to impact on target functions. to achieve compact representations, we took the following considerations into account. first, fn are expected to map onto a ppi network the correspondence between proteins and annotations. second, such mapping is expected to represent the most extensive coverage of the ppi network with the least degree of overlap between fn, provided that one can exclude the annotations of those proteins that support only indirectly the annotated functions. third, molecules more typically contribute to biological functions as highly inter-connected assemblies, rather than as unconnected elements. within ppi networks, for instance, functional and topological modules display significant overlap. thus, based on these considerations, the algorithm we have devised introduces a topologically-driven prioritization that selects only plausible inclusions of a protein into a fn, as quantified by its pms, i.e., a score that reflects the ability of a fn to discriminate among the topological patterns of the ppi network, to which the protein belongs. the method has been applied to two cellular components and one biological process in s. cerevisiae, which are well characterized domains and thus suitable for validation purposes. on one hand, well characterized causal dependencies among functions have confirmed that the method specifically highlights important relations. on the other hand, less obvious dependencies have revealed the heuristic power of this method and its usefulness in formulating testable hypotheses. it should be noted that the peroxisome-centered ppi network has been extended to the first neighbors of the peroxisome core proteins, because we wanted to highlight the wider biological landscape that ideally surrounds the organelle. the inclusion of non-peroxisomal proteins is justified by the observation that almost half of the core proteins are annotated with terms related not only to the peroxisome but also to mitochondrion, er and nucleus, the organelles that interact functionally with the peroxisome. clearly, some multiple annotations of the same protein simply refer to the existence of sub-cellular distinct pools, such as the peroxisomal and nuclear pools of the dynamin dyn2p. nevertheless, other multiple annotations suggest that a protein may change its sub-cellular location, at least under specific conditions. for instance, pex11p relocates from the er to the peroxisome, when peroxisomes are induce to proliferate in response to oleate. numerous studies have analyzed the relation between molecules and functions. in particular, one of the major aims of many bioinformatics studies has been to infer the function of uncharacterized genes based on comparisons with characterized genes, such as sequence similarity, co-occurrence in genomic clusters, co-evolution in different species and co-expression patterns. also the ppi have been used to infer the function of uncharacterized proteins, based on the most frequent annotations of their protein interactors. like these ‘guilt by association’ methods, also our approach builds on the assumption that proteins often interact mutually to contribute to the same function. furthermore, all these studies deploy a non-directional annotated network as input, sometimes designed ‘functional linkage network’, in which nodes correspond to molecules, while edges correspond to different types of functional connection between molecules. few studies, however, have moved beyond the immediate aim of inferring protein-function binary associations to the ultimate aim of inferring structured dependencies among functions, which can be displayed in a markov graph of connected functions. an earlier study established a link between a given pair of functions, anytime a ppi had been detected between the proteins annotated with the two functions. a more recent study has elaborated on this method, by selecting statistically enriched pairs of functions, as defined by the probability that two sets of proteins establish more ppi between themselves than it can be expected by chance. our method differs considerably from these earlier studies, as it retains any annotation that is shared by two interacting proteins within the ppi network, leaving to the topological analysis the task to define the fn, whose relationships may satisfy the markov property. this way, the selected and prioritized protein assignments to the fn are expected to refer truly to the functions that are directly impacted by the protein. as an example of how our approach differs from the previous studies, consider a 3-node sub-graph composed of fn related to the go functional annotations of protein import, pmp insertion into the peroxisome membrane and peroxisome organization. while a previous study linked the three nodes with three edges, our algorithm establishes only two edges, but not the edge between nodes and because it would violate the markov assumption, given that protein import contributes to peroxisome organization only indirectly, i.e., by enabling pmp insertion. furthermore, our study also contrasts with an important implication of the earlier study, which advocated re-engineering the go database by complementing the go hierarchy with the links inferred from the functional linkage graphs. alternatively, we propose to adapt the semantics of the go annotations to the level of detail that characterizes the domain of interest, mostly based on the real protein content of the fn. a more detailed comparison of graphs that represent similar domains but are obtained with different methods can be found in additional file clearly, our method can be applied to different domains of biological interest in different model organisms, even though some words of caution should be added. first and foremost, inaccurate and/or defective datasets of protein interactions and functions will certainly affect the quality of the pg representation. in our experience with s. cerevisiae, even after revising carefully the pg, we found just a limited number of false positives and false negatives. nevertheless, we cannot exclude that results might be less accurate, should the algorithm be applied to other organisms that are not so extensively and accurately characterized as the budding yeast. second, other features of the starting ppi network should be taken into account, including the choice of a cell type-specific repertoire of proteins and the size of the ppi. third, it should be pointed out that labor-intensive analysis is required to verify the consistency of the pg with current biological knowledge and to define the causal directionality of its undirected edges. it should also be taken into account that just a minor fraction of the physical interactions that are reported in the ppi databases have an annotation of biochemical directionality. for instance, out of ppi reported as ‘physical interactions’ in the. release of biogrid, more than 94% of ppi has no annotation. only less than 6% of the remaining ppi has the annotation ‘phosphorylation’ or other types of modifications. furthermore, in many of these cases, the annotated modification has been detected in a biochemical assay without functional characterization. finally, many ppi refer to physical interactions that are non-directional in nature. in conclusion, with all the caveats related to incomplete knowledge, the herein reported data suggest that, even when the ppi structures that underlie a function are only partially known, it is nevertheless possible to regard functions as black boxes with only known inputs and outputs, to obtain non-redundant graphical representations of complex biological systems. in addition, our efforts indicate that the graph we obtain can be helpful in carefully designing experimental studies, provided that specific manipulation and measurement of the portrayed functions are feasible.  the major problem with the idea of converting ppi networks into pg is that several proteins have multiple annotations. faced with this challenge, we reasoned that the final pg could be non-redundant, if only the proteins that participate directly in a given function are included in the related fn. furthermore, we surmised that topological features might help approaching structured and non-redundant understanding of molecular function. thus, an algorithm was developed that prioritizes inclusion of proteins into the fn that best overlap protein clusters. specifically, the algorithm identifies fn, based on the topological analysis of the starting ppi network. applying the algorithm to different domains of biological interest has shown that the method is suitable for formulating testable and mechanistic hypotheses about the existence of dependencies among functions. 
reasoning that topological features might help approaching structured and non-redundant understanding of molecular function, an algorithm was developed that prioritizes inclusion of proteins into the function nodes that best overlap protein clusters. the examples we have described show that the resulting graph allows researchers to formulate testable hypotheses about dependencies among functions and the underlying mechanisms. specifically, the algorithm identifies function nodes, based on the topological analysis of a protein interaction network, which can be related to various biological domains, such as cellular components or biological processes of the model organism s. cerevisiae. as protein-protein interactions connect proteins that participate in either the same or different functions, networks of interacting and functionally annotated proteins can be converted into process graphs of inter-dependent function nodes. the method we have described allows converting a protein interaction network into a non-redundant process graph of inter-dependent function nodes. however, as proteins have multiple annotations, the process graph is non-redundant, if only proteins participating directly in a given function are included in the related function node.
 as protein-protein interactions connect proteins that participate in either the same or different functions, networks of interacting and functionally annotated proteins can be converted into process graphs of inter-dependent function nodes. however, as proteins have multiple annotations, the process graph is non-redundant, if only proteins participating directly in a given function are included in the related function node.  reasoning that topological features might help approaching structured and non-redundant understanding of molecular function, an algorithm was developed that prioritizes inclusion of proteins into the function nodes that best overlap protein clusters. specifically, the algorithm identifies function nodes, based on the topological analysis of a protein interaction network, which can be related to various biological domains, such as cellular components or biological processes of the model organism s. cerevisiae.  the method we have described allows converting a protein interaction network into a non-redundant process graph of inter-dependent function nodes. the examples we have described show that the resulting graph allows researchers to formulate testable hypotheses about dependencies among functions and the underlying mechanisms. protein interaction networksbiological functionsmarkov representationsperoxisomescell buddingpolarized growthsaccharomyces cerevisiae 