Diff for "HyperEdgeAPI"

<<TableOfContents: execution failed [Argument "maxdepth" must be an integer value, not "[2]"] (see also the log)>>

About this document

This is an official Request for Comment (RFC) for supporting HyperEdges in Cytoscape.

For details on RFCs in general, check out the Wikipedia Entry: Request for Comments (RFCs)

Status

Open for public comment.

A reference implementation, the HyperEdge plugin, is available for use upon request.

How to Comment

To view/add 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. Be sure to include today's date and your name for each comment. Here is an example to get things started: /Comment.

Try to keep your comments as concrete and constructive as possible. For example, if you find a part of the RFC makes no sense, please say so, but don't stop there. Take the extra step and propose alternatives.

Proposal

A HyperEdge is an Edge that connects two or more Nodes. A HyperEdge consists of a set of Edges and a special Node referred to as a ConnectorNode. The ConnectorNode is a generated Node that serves as one endpoint for all Edges contained by a HyperEdge.

Some assumptions about HyperEdges are:

1. HyperEdges are mutable.

2. A HyperEdge may have more than one CyNode with the same CyEdge interaction type.

3. A HyperEdge may have more than one CyEdge to the same CyNode.

4. A HyperEdge has exactly one ConnectorNode.

5. A HyperEdge ConnectorNode may be used as a regular CyNode within another HyperEdge.

6. A HyperEdge is associated with one or more CyNetworks.

7. The only shared CyEdges in a HyperEdge are those connecting two ConnectorNodes (HyperEdges) that must exist in the same CyNetwork.

8. If HyperEdge A connects to HyperEdge B via a shared edge, both A and B can only exist in one (and the same) CyNetwork.

9. A regular Cytoscape Edge may directly connect to a HyperEdge ConnectorNode, but it will not be considered part of the HyperEdge.

10. 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.

See the Java HyperEdge API Java Documents for details on the API.

Biological Questions / Use Cases

The use case for HyperEdges is for representing structures like reactions and protein complexes. A simple example might be to represent a reaction what has a Substrate, Product and Mediator (e.g, Citrate, Isocitrate, and Aconitase). Such a reaction could be represented as a HyperEdge that contains three Edges that make up the Substrate, Product, and Mediator of the reaction. Here's a larger example of the Krebs Cycle that contains several reactions.

General Notes

Requirements

In order to understand our approach to HypeEdges, it is important to understand our overall requirements:

1. Allow the addition of HyperEdges to exist as a plugin without the need for changes to the Cytoscape core.

Since HyperEdges require testing and experimentation to validate the HyperEdge API, it is necessary to provide HyperEdge functionality without requiring Cytoscape core changes. To satisfy this requirement, we ensure an implementation is possible where only existing Cytoscape machinery is needed; all state information that defines HyperEdges is composed of existing Cytoscape Nodes, Edges, and Cytoscape attributes.

Open Issues

1. What should the behavior be for linking HyperEdges to other HyperEdges?

This is the case where one of the CyNodes of one HyperEdge is the ConnectorNode of another HyperEdge. There are several possible approaches, including restricting connections to one CyNetwork, tight sharing of connections, and always copying when connecting. For more details, see HyperEdge Linking Strategies.

2. How should HyperEdge persistence be handled?

Right now, the HyperEdge API includes nothing on how HyperEdges should be persistently stored (e.g., read and written in XGMML). This was intentional based on our requirement one and since a reference implementation can be created that simply uses Cytoscape's persistence. However, if there is a desire to generate HyperEdges outside of the Cytoscape environment, then some way may be needed to specify the format needed to create HyperEdges in XGMML. One possibility to to create a "reflection" for the HyperEdges API that allows access to the names and formats used for storing HyperEdge information.

3. Given that we want HyperEdges to be implemented thru a plugin, how do we keep HyperEdges up-to-date when CyNodes and CyEdges are hidden?

The most obvious approach is to monitor the hiding of CyNodes and CyEdges and update the HyperEdge data structures accordingly. However, there are various problems with this approach that are discussed in detail in How Do We Keep HyperEdge Structures Up-To-Date? (see Delayed CyNode Deletion, which is the approach taken for the 2.5 release of the HyperEdge plugin).

Closed Issues

1. What Cytoscape classes and interfaces should be referenced by the HyperEdge API?

Overall, the API would be most flexible referencing the most base interfaces possible (the most general interfaces, such as GraphPerspective, Node, and Edge); assuming these base interfaces are stable (e.g., not being removed). Intially using base interfaces has the added benefit of being much easier to migrate to one of its extensions in the future. For example, it is easy to change an API from using GraphPerspectives to using CyNetworks. But, it isn't easy to switch from using CyNetworks to GraphPerspectives.

If only Cyto-based classes and interfaces should be referenced, then Cytoscape should be changed to include interfaces for CyNodes and CyEdges (these are currently classes). This way, the HyperEdge API and other APIs, could be more flexible by sticking to referencing interfaces versus specific implementation objects.

[At the Oct 2006 Cyotscape Retreat, the decision was to only reference CyNodes, CyEdges, and CyNetworks.]

2. Should HyperEdges exist in only one CyNetwork?

If there are no compelling reasons for having a HyperEdge exist in multiple !CYNetworks this would help simplify the API and most implementations of HyperEdges.

If there are compelling reasons for having a HyperEdge exist in multiple CyNetworks, then there is the question of whether the HyperEdge is shared across CyNetworks? If shared, any change to the HyperEdge affects the HyperEdge in all CyNetworks in which it resides. If not shared, then a change to the HyperEdge in one CyNetwork doesn't affect the HyperEdge in other CyNetworks. Allowing unshared behavior implies added complexity in the APi and implementation in that the HyperEdge must manage its state for each CyNetwork in which it resides.

Currently, the behavior of Cytoscape CyNodes and CyEdges is that they can exist in multiple CyNetworks, but are not shared. However, Cytoscape CyNode and CyEdge attributes are shared.

[At the Oct 2006 Cyotscape Retreat, the decision was to allow HyperEdges to exist in multiple CyNetworks as a shared structure--a change to a HyperEdge will affect the HyperEdge in all CyNetworks to which it belongs.]

Backward Compatibility

References

This proposal complements the Group API (RFC 18) and there is a desire to have some consistent behavior at a general level in between Groups and HyperEdges (e.g., whether they can both exist in multiple GraphPerpsectives and can both be shared).

Implementation Plan

• /Implementation Plan

Comments

GaryBader - 2006-10-09 11:42:55

Should the sharing between CyNetworks policy be the same for the group API? I.e. no sharing, but shallow copy possible?

AdityaVailaya - 2006-10-30 15:59:38

Clarifying the current policy assumption: group API and HyperEdge API will by default be "shared" in multiple CyNetworks. Any change to a HyperEdge in one CyNetwork will affect/change all other Cynetworks having the same HyperEdge. A "copy" routine will be provided in the API for when sharing is not desired. All properties of the original HyperEdge will be copied into the new HyperEdge, but a new ConnectorNode and new edges incident on the ConnectorNode will be created.