-
Notifications
You must be signed in to change notification settings - Fork 0
/
sbgn_er.html
110 lines (104 loc) · 5.55 KB
/
sbgn_er.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
<!DOCTYPE html>
<html>
<head>
<title>biographer: Google Summer of Code 2012</title>
<link rel="stylesheet" href="main.css" type="text/css" />
</head>
<body>
<div>
<div>
<h1>Graph layout for Entity relationship diagrams</h1>
<h2>Motivation</h2>
<p>
Concise and clear visualisation has a great potential in helping us understand
complex biological reaction networks. However, the full potential in these
visualisations are only realised when the network is laid out in a format
accessible to the human reader. The objective of this project is to create a
layout algorithm for a specific type of such standardised networks.
</p>
<p>
The most challenging biological reaction networks are the cellular signal
transduction networks. These networks transmit information via reactions chains
that depend on state changes in the network components. While each such state is
typically a binary switch, they combine to define the components activity state
and hence the information transduction. Due to this combinatorial complexity,
such networks rapidly become very complex and detailed visualisation of even a
small signal transduction pathway is a daunting task<sup>1</sup>.
</p>
<p>
The entity relationship (ER) diagram is one of three standard graphical formats
developed as part of the Systems Biology Graphical Notation (SBGN) community<sup>2</sup>.
Of these three standards, ER deals best with the combinatorial complexity. ER
represents each component as a unique node, or entity, and surrounds each entity
with the reaction and (reaction) outcome markers pertaining to that entity
(Figure 1). The advantage of ER is that states are treated individually rather
than combinatorial, drastically reducing the number of nodes in the network.
However, each such network is currently a hand crafted creation due to the
complete lack of layout algorithms designed for SBGN-ER.
</p>
<div style="margin:auto;display:inline-block"><img style="margin:auto" src="images/sbgn_er.png"><br>
Figure 1: SBGN-ER. Entities are represented as black nodes, and the edges
indicate reactions the entities take part in. The small blue and red nodes
indicate assignments. The edges are either reaction edges (connecting entities
to assignments or other entities) or influence edges that affect the rate of
reactions. Small filled dots are outcome nodes that act as source for influence
edges when the outcome is required for the influence
(http://www.sbgn.org/Documents/ER_L1_Examples).
</div>
<p>
The layout of the entities as well as the layout of reactions and states around
entities could be achieved by available layout algorithms, but the combination
of the two and the advanced edge routing required poses a specific challenge.
This challenge is aggravated in larger networks as the connectivity typically
increases with increasing network size. Hence, the layout of entity relationship
diagrams of biological networks constitutes a unique challenge, justifying
layout algorithms optimized for this type of graph.
</p>
<h2>Suggested solution</h2>
<p>
The goal of this project is to develop a layout algorithm which specifically
addresses the challenges in entity relationship diagram. Specifically, this
means: (1) Combining a global layout of entity nodes with local layout of
reactions and states around entity nodes, (2) optimising the global layout to
emphasise the information flow in the pathway, (3) optimising the layout of
reaction and states around each entity to maximise the mechanistic clarity and
(4) to minimise the edge crossings to make the visualisation optimal for the
human reader.
</p>
<p>
The proposed algorithm would work on two levels; first it would apply a global
topological layout based on a hybrid between spring based and hierarchical
layout. The implementation should be based on minimizing forces as for classical
spring models. Different reaction types will give different spring strength, to
give preference for complex formation while modulation edges may be more
far-reaching. Each unidirectional reaction will get a direction assigned which
is also subject to force minimization (torque). This will put an extra force on
the alignment of directionality, which will also be subject to the general force
minimization. In that way, the resulting layout should have a strong
hierarchical component emphasising the information flow. Second, the detailed
local layout would add reactions, outcomes and influences; use a spring based
algorithm to organise the reaction and states around the entities; and will use
edge crossing minimisation and orthogonal edge routing to maximise readability.
These ideas will serve as the starting point for an iterative development
process in which we value inputs and ideas by our students.
</p>
<h2>Algorithm properties</h2>
<ol>
<li>optimised entity relationship diagrams
<li>create reduced graph containing only entities and their adjacencies
<li>classical layout (spring and / or hierarchical) on an reduced entity graph (could use existing C++ layout algorithm)
<li>advanced edge routing to find minimum edge crossings in complete graph (could be done on C++ level or in JavaScript)
<li>strict adherence to existing standards (i.e. SBGN-ER) and compatibility with
<li>integration into existing biographer-layout package (C++)
</ol>
<h2>Mentors:</h2>
<ul>
<li>Marcus Krantz
<li>Thomas Handorf
</ul>
1. Hlavacek, W.S., J.R. Faeder, M.L. Blinov, A.S. Perelson, and B. Goldstein, The complexity of complexes in signal transduction. Biotechnol Bioeng, 2003. 84(7): p. 783-94.<br>
2. Le Novere, N., et al., The Systems Biology Graphical Notation. Nat Biotechnol, 2009. 27(8): p. 735-41.
</div>
</div>
</body>
</html>