Discussion Title : Hyperedges |
Editor(s): Michael Creech |
<<TableOfContents: execution failed [Argument "maxdepth" must be an integer value, not "[2]"] (see also the log)>>
About this document
This document considers some of the issues with adding hyperedges to Cytoscape 3. These issues are presented by looking at the feedback and lessons learned in implementing the HyperEdgeEditor plugin.
Introduction and Terminology
A hyperedge is an Edge that connects two or more Nodes. Hyperedges may be useful for representing more complex structures like reactions and protein complexes.
Since this document makes heavy reference to the HyperEdgeAPI, a good familiarity with the existing HyperEdgeEditor plugin is essential. See the References section for information on how to familiarize yourself with this plugin.
The HyperEdgeEditor plugin, adds hyperedge functionality to Cytoscape 2.6 (referred to here as the plugin model). The future Cytoscape 3 hyperedge model will be referred to as the C3 model. There is a skeleton framework for the C3 model in fastGraphCy3 trunk (http://chianti.ucsd.edu/svn/csplugins/trunk/ucsd/mes/fastGraphCy3/src/org/cytoscape/model/).
How to Discuss
To view/add discussion comments, click on any of 'Comment' links below. By adding your ideas to the Wiki directly, we can more easily organize everyone's ideas, and keep clear records. Try to keep the discussion as concrete and constructive as possible. Be sure to include today's date and your name for each comment.
References
The HyperEdgeEditor plugin adds an underlying hyperedge model (the HyperEdge API) to Cytoscape 2.6, along with a very simple editor for creating and editing hyperedges. More information can be obtained on the HyperEdgeEditor plugin from the following sources:
See HyperEdgeAPI for more info about the underlying hyperedge model.
JavaDocs for the hyperedge model is available at Java HyperEdge API Java Documents.
Source code for the hyperedge model is available via SVN from grenache.ucsd.edu/cellar/common/svn/csplugins/trunk/agilent/creech/HyperEdge.
See cytoscape.hyperedge.HyperEdge for an overall description of terms and assumptions.
Source code for the hyperedge editor is available via SVN from grenache.ucsd.edu/cellar/common/svn/csplugins/trunk/agilent/creech/HyperEdgeEditor
Once the HyperEdgeEditor is loaded in Cytoscape, two sample hyperedge networks are available via File->Import->HyperEdge Sample Networks. This will build two hyperedge networks--Glycolysis Reaction network and a Krebs Cycle network. You can look at the source code that generates these two networks in cytoscape.hyperedge.editor.SampleNetworks.java
Discussion
Looking at the Plugin Model Assumptions
Following are a set of assumptions that were developed with the plugin model (we kept going around in circles on various issues until we wrote up a list of our assumptions). Each assumption is considered with respect to its implications on the C3 model:
Hyperedges are mutable.
The plugin model has mutable hyperedges with the ability to add and remove edges and nodes. Two situations where mutability is desired are:- when you don't have all the edges, nodes and other hyperedges defined to build the complete hyperedge (especially in the chicken-or-the-egg case of connecting two hyperedges).
- when editing hyperedges--incrementally adding, removing, and connecting hyperedges to other structures.
If the C3 model defines CyHyperEdges to be immutable, like CyEdges, then there must be a way to deal with a) and b) or there must be good evidence that a) and b) can be restricted.
A Hyperedge may have more than one CyNode with the same CyEdge interaction type.
First, a digression. This brings up the more fundamental question of how hyperedges are semantically structured--how are parts of the hyperedge defined, referenced, and traversed? Structure is obviously needed. For example, is you are building a Krebs Cycle, you might want to define hyperedges containing products, mediators, and substrates. If you are building something else, the structuring may be completely different. Without structure, how would you ask, if the 'product' of a given hyperedge was the CyNode 'CO2'?
The plugin model uses interaction types to define structure. An interaction type is just a String that represents the role a Node plays within a hyperedge (in the implementation, this translates to a CyEdge attribute named "interaction" being added to the CyEdge). These interaction types are used my many plugin model operations to allow construction and searches. For the C3 model, if no scheme is provided for structuring hyperedges, the API is certainly simplified. However, each set of users will be forced to come up with their own conventions for determining hyperedge structure and will also have to supply middleware code to construct, traverse, and search their hyperedges.
Back to this assumption, given this definition of interaction types, this assumption states that a hyperedge may have two different CyNodes with the same interaction type. This is needed to allow things like reactions to have multiple catalysts, inhibitors or activators in a reaction.
A Hyperedge may have more than one CyEdge to the same CyNode.
In some reactions, a component can play multiple roles in the same reaction. For example, in the Glycolysis reaction, Ca2+ acts as both an inhibiting and activating modulator for pyruvate kinase I.The plugin model handles this assumption by the fact that a hyperedge may contain two or more CyEdges to the same node--each with a different interaction type.
For the C3 model, this implies that a CyHyperEdge must be able to have duplicate source and target nodes and there must be a way to specify separate attributes for each sub-edge. So, in the above example, a hyperedge would have two (sub)edges to the CyNode Ca2+, one with one attribute type (e.g., inhibiting) and the other with a different attribute type (activating) and we would need to be able to choose one and manipulate it independent from the other.
A Hyperedge has exactly one ConnectorNode.
The plugin model uses existing CyEdges and CyNodes to construct hyperedges. On the surface, you might think that for the C3 model you'd want to throw out these ConnectorNodes and just have hyperedges contain lists of source and target nodes. However, there are some major advantages to keeping the ConnectorNodes and some challenges if we remove them:Advantage: Allows peaceful and incremental integration with CyNetworks, CyNodes, and CyEdges.
When using ConnectorNodes, there are no new fundamental structures that every mechanism within Cytoscape needs to handle before hyperedges are integrated into Cytoscape. This is because the components of every hyperedge are just common CyNodes and CyEdges. The level of integration of the ConnectorNode-based hyperedges can be slowly increased, starting with low-level integration for tracking hyperedges (creation and deletion) and then adding visual style, filtering, layout, and any other additions required.
- Challenge: How do we connect hyperedges together?
ConnectorNodes are like any other node and can be used to connect one hyperedge to another. One situation where this is needed is where one or more hyperedges represent a reaction that is the catalyst of another reaction (see Glycolysis Reaction example in the HyperEdgeEditor plugin).
A hyperedge ConnectorNode may be used as a regular CyNode within another hyperedge.
In the plugin model, this is fundamental to linking one hyperedge to another. This also gives an existing object from which to hang attributes that represent the entire hyperedge without having to create a new category of attributes (those hanging on hyperedge objects).A hyperedge is associated with one or more CyNetworks.
If hyperedge's follow the rest of the Cytoscape 3.0, then they would not be shared across CyNetworks. This would simplify this assumption to:
A hyperedge is associated with one CyNetwork.
This would simplify the existing plugin model API by removing or reducing various methods dealing with hyperedges within CyNetworks.The only shared CyEdges in a hyperedge are those connecting two ConnectorNodes (hyperedges) that must exist in the same CyNetwork.
Since for Cytoscape 3.0 , hyperedges would not be shared across networks, this could be simplified to:
The only shared CyEdges in a hyperedge are those connecting two ConnectorNodes (hyperedges).
In the plugin model, there is an important implicit assumption here, in that there is only one shared CyEdge that connects two hyperedges--each hyperedge doesn't hold its own separate instance of a CyEdge that connects the other hyperedges. This was found to be more managable then having two separate CyEdges for the connection.If hyperedge A connects to hyperedge B via a shared edge, both A and B can only exist in one (and the same) CyNetwork.
For the C3 model, this is implied since hyperedges are not shared (see #6).A regular Cytoscape CyEdge may directly connect to a hyperedge ConnectorNode, but it will not be considered part of the hyperedge.
In the plugin model, we allow ConnectorNodes to be like any other node and have CyEdges connecting them. Is there really a good case for users wanting to connect ConnectorNodes with regular CyEdges, or should this sort of operation be banned? If banned and if ConnectorNodes are used in the C3 model, then checks will need to be made concerning hyperedges in the regular CyEdge creation code.Hyperedges are shared, in that any change to a hyperedge existing in more than one CyNetwork is reflected in all CyNetworks to which the hyperedge belongs.
For the C3 model, this is implied since hyperedges are not shared (see #6).Hyperedges can co-exist with CyEdges and CyNodes in CyNetworks.
For the plugin model, this is implicitly true. As for the C3 model, how important is it that hyperedges co-exist with regular edges in networks?
Integrating Hyperedges into Cytoscape
How should hyperedges appear in the API within Cytoscape? A few possibilities are:
- Integrate the plugin model's API into the Cytoscape 3.0 core.
This has some advantages as discusses in Assumption 4. Required changes to the plugin model would include:Updating the API to remove sharing of hyperedges across CyNetworks.
- Removing complex event handling that allows tracking of deleted hyperedges within the plugin.
- Reviewing and possibly removing other secondary state and methods deemed uneeded for the C3 model.
Various package and naming changes (e.g., HyperEdge-->CyHyperEdge).
Segregate hyperedges from regular networks and have them available only in special CyHyperEdgeNetworks.
These networks would allow CyNodes and CyHyperEdges. This would help localize the complexity of hyperedges by confining them to special networks. This does complicate things in that there would be two types of CyNetworks and the various operations for copying things from one network to another are more complex. There is also a major user question as to whether hyperedge users would require mixing of the hyperedges with reqular nodes and edges.Create a new CyHyperEdge that does not use plugin model-type ConnectorNodes or regular CyEdges
If an attempt is made in this direction, it should address the various issues discussed in this document.Variation: Define a CyHyperEdge that extends CyEdge.
We feel this would be a mistake from a design standpoint since hyperedges are generalizations of CyEdges, not specializations. Also, we think it would be confusing in that getSource(), getTarget() don't really make sense (would have to return an arbitrary value).