Diff for "HyperEdgeAPI"

TableOfContents([2])

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 [http://www.answers.com/main/ntquery?method=4&dsid=2222&dekey=Request+for+Comments&gwp=8&curtab=2222_1&linktext=Request%20for%20Comments 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 Node with the same Edge interaction type.

3. A HyperEdge may have more than one Edge to the same Node.

4. A HyperEdge has exactly one ConnectorNode.

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

6. A HyperEdge is associated with exactly one GraphPerspective.

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

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

See the [attachment:hyperedge-2.0.03-docs.jar 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 [attachment:krebs-cycle.bmp 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 possibler 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 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.

2. Should HyperEdges exist in only one GraphPerspective?

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

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

Currently, the behavior of Cytoscape Nodes and Edges is that they can exist in multiple GraphPerspectives, but are not shared. However, Cytoscape Node and Edge attributes are shared.

3. 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 since a reference implementation can be created that... 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.

4. How do we connect one HyperEdge to another HyperEdge?

It appears there are use cases for wanting to connect one HyperEdge to another HyperEdge, via there ConnectorNodes. <NEED REASON FOR THESE TYPE OF CONNECTIONS>

If we desire to make such connections, do we want to have one edge that is shared across the two HyperEdges, or have two separate edges? Although having one shared Edge might seem best on the surface, the problem is that we have no way of having the one Edge play two different roles (e.g., Product and Substrate) within Cytoscape. For example, consider HyperEdge he1 which has a Substrate(S) and Mediator (M1) and HyperEdge he2 which has a Mediator (M2) and Product (P) and we want to connect he1 and he2 with an Edge so that he2 is the Product of he1 and he1 is the Substrate for he2. Right now, I can make one, or both, of these Edges as in:

     he1.addEdge (he2.getConnectorNode(),EdgeTypeMap.PRODUCT);

or

     he2.addEdge (he1.getConnectorNode(),EdgeTypeMap.SUBSTRATE);

But we can’t have just one Edge play both PRODUCT and SUBSTRATE. Given this restriction, would we always have two edges in between two HyperEdges; one from each HyperEdge? If so, then the Edges are still never shared and this simplifies the removal and addition of edges since we don’t have to remove an edge from both HyperEdges or add an Edge to both HyperEdges. This would also change HyperEdge assumption 7 (<link>) back to saying a HyperEdge edges are never shared.

Maybe we should make Connecting one HyperEdge to another an explicit operation in our API? This is assuming such a connection should exist bidirectionally (need to make two Edges) and that the "role" of the edge(s) may be different. If this is true, then we could add something like:

    public Edge[] HyperEdge.addEdgeToOtherHyperEdge(Node connectorNode, String ToEdgeIType, String FromEdgeIType);

This would return an array of two Edges, the first edge being the edge that belongs to this HyperEdge and the second being the edge that belongs to the HyperEdge represented by connectorNode. Another possibility is to have this be a HyperEdgeManager operation. Having an explicit operation for linking HyperEdges could also be used to channel all HyperEdge-HyperEdge linking thru one operation. Thus, all the other operations could throw an exception if given ConnectorNodes.

If in the future, if Edges can have multiple "roles", then the API could be simply changed to return one Edge versus the array of two Edges.

Backward Compatibility

References

This proposal complements the [:groupAPI: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

• [:HyperEdgeAPI/Implementation Plan:/Implementation Plan]

Comments

PageComment2