Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2010 Jun 18:11:335.
doi: 10.1186/1471-2105-11-335.

An efficient biological pathway layout algorithm combining grid-layout and spring embedder for complicated cellular location information

Kaname Kojima  1 , Masao Nagasaki, Satoru Miyano
Affiliations

An efficient biological pathway layout algorithm combining grid-layout and spring embedder for complicated cellular location information

Kaname Kojima et al. BMC Bioinformatics. .

Abstract

Background: Graph drawing is one of the important techniques for understanding biological regulations in a cell or among cells at the pathway level. Among many available layout algorithms, the spring embedder algorithm is widely used not only for pathway drawing but also for circuit placement and www visualization and so on because of the harmonized appearance of its results. For pathway drawing, location information is essential for its comprehension. However, complex shapes need to be taken into account when torus-shaped location information such as nuclear inner membrane, nuclear outer membrane, and plasma membrane is considered. Unfortunately, the spring embedder algorithm cannot easily handle such information. In addition, crossings between edges and nodes are usually not considered explicitly.

Results: We proposed a new grid-layout algorithm based on the spring embedder algorithm that can handle location information and provide layouts with harmonized appearance. In grid-layout algorithms, the mapping of nodes to grid points that minimizes a cost function is searched. By imposing positional constraints on grid points, location information including complex shapes can be easily considered. Our layout algorithm includes the spring embedder cost as a component of the cost function. We further extend the layout algorithm to enable dynamic update of the positions and sizes of compartments at each step.

Conclusions: The new spring embedder-based grid-layout algorithm and a spring embedder algorithm are applied to three biological pathways; endothelial cell model, Fas-induced apoptosis model, and C. elegans cell fate simulation model. From the positional constraints, all the results of our algorithm satisfy location information, and hence, more comprehensible layouts are obtained as compared to the spring embedder algorithm. From the comparison of the number of crossings, the results of the grid-layout-based algorithm tend to contain more crossings than those of the spring embedder algorithm due to the positional constraints. For a fair comparison, we also apply our proposed method without positional constraints. This comparison shows that these results contain less crossings than those of the spring embedder algorithm. We also compared layouts of the proposed algorithm with and without compartment update and verified that latter can reach better local optima.

PubMed Disclaimer

Figures

Figure 1
Figure 1
Resulting layouts of Fas-induced apoptosis model obtained from Grid Layout (a) and Spring (b). Because the spring embedder algorithm does not consider location information, this location information is not shown in its resulting layout.
Figure 2
Figure 2
Resulting layouts of cell fate simulation model of C. elegans obtained from Grid Layout (a) and Spring (b). Because the spring embedder algorithm does not consider location information, this location information is not shown in its resulting layout.
Figure 3
Figure 3
Resulting layouts of endothelial cell model obtained from Grid Layout (a) and Spring (b). Because the spring embedder algorithm does not consider location information, this location information is not shown in its resulting layout.
Figure 4
Figure 4
Comparisons of number of edge-edge crossings (left), number of node-edge crossings (middle), and running time (right) for Fas-induced apoptosis model. Numbers of edge-edge intersections and node-edge intersections and running time for Grid Layout, Spring, and Grid Layout NL (Grid Layout considering no location information) are compared using box plots. These indicators are obtained by applying these three algorithms to ten randomly obtained layouts of the Fas-induced apoptosis model.
Figure 5
Figure 5
Comparisons of number of edge-edge crossings (left), number of node-edge crossings (middle), and running time (right) for cell fate simulation model of C. elegans. Numbers of edge-edge intersections and node-edge intersections and running time for Grid Layout, Spring, and Grid Layout NL (Grid Layout considering no location information) are compared using box plots. These indicators are obtained by applying these three algorithms to ten randomly obtained layouts of the cell fate simulation model C. elegans.
Figure 6
Figure 6
Comparisons of number of edge-edge crossings (left), number of node-edge crossings (middle), and running time (right) for endothelial cell model. Numbers of edge-edge intersections and node-edge intersections and running time for Grid Layout, Spring, and Grid Layout NL (Grid Layout considering no location information) are compared using box plots. These indicators are obtained by applying these three algorithms to ten randomly obtained layouts of the endothelial cell model.
Figure 7
Figure 7
Resulting layouts of Fas-induced apoptosis model obtained from GDC (Grid Layout with dynamic compartment update). Iterative update of the sizes and positions of nucleus and mitochondria is considered at each step.
Figure 8
Figure 8
Resulting layouts of cell fate simulation model of C. elegans obtained from GDC (Grid Layout with dynamic compartment update). Iterative update of the size and position of nucleus is considered at each step.
Figure 9
Figure 9
Resulting layouts of endothelial cell model obtained from GDC (Grid Layout with dynamic compartment update). Iterative update of the sizes and positions of nucleus, mitochondria, and Gologi apparatus are considered at each step.
Figure 10
Figure 10
Comparisons of total cost (left), number of edge-edge crossings (middle left), number of node-edge crossings (middle right), and running time (right) for Fas-induced apoptosis model. Total costs, Numbers of edge-edge intersections and node-edge intersections and running time for Grid Layout and GDC (Grid Layout with dynamic compartment update) are compared using box plots. These indicators are obtained by applying these two algorithms to ten randomly obtained layouts of the Fas-induced apoptosis model.
Figure 11
Figure 11
Comparisons of total cost (left), number of edge-edge crossings (middle left), number of node-edge crossings (middle right), and running time (right) for cell fate simulation model of C. elegans. Total costs, Numbers of edge-edge intersections and node-edge intersections and running time for Grid Layout and GDC (Grid Layout with dynamic compartment update) are compared using box plots. These indicators are obtained by applying these two algorithms to ten randomly obtained layouts of the cell fate simulation model C. elegans.
Figure 12
Figure 12
Comparisons of total cost (left), number of edge-edge crossings (middle left), number of node-edge crossings (middle right), and running time (right) for endothelial cell model. Total costs, Numbers of edge-edge intersections and node-edge intersections and running time for Grid Layout and GDC (Grid Layout with dynamic compartment update) are compared using box plots. These indicators are obtained by applying these two algorithms to ten randomly obtained layouts of the endothelial cell model.
See this image and copyright information in PMC

Similar articles

See all similar articles

Cited by

References

    1. Kanehisa M. The KEGG database. Novartis Found Symposium. 2002;247:91–101. full_text. - PubMed
    1. Schacherer F, Choi C, Götze U, Krull M, Pistor S, Wingender E. The TRANSPATH signal transduction database: a knowledge base on signal transduction networks. Bioinformatics. 2001;17(11):1053–1057. doi: 10.1093/bioinformatics/17.11.1053. - DOI - PubMed
    1. Doi A, Nagasaki M, Fujita S, Matsuno H, Miyano S. Genomic Object Net: II. Modelling biopathways by hybrid functional Petri net with extension. Applied Bioinformatics. 2003;2(3):185–188. - PubMed
    1. Nagasaki M, Doi A, Matsuno H, Miyano S. Genomic Object Net: I. A platform for modelling and simulating biopathways. Applied Bioinformatics. 2003;2(3):181–184. - PubMed
    1. Shannon P, Markiel A, Ozier O, Baliga NS, Wang JT, Ramage D, Amin N, Schwikowski B, Ideker T. Cytoscape: a software environment for integrated models of biomolecular interaction networks. Genome Research. 2003;13(11):2498–2504. doi: 10.1101/gr.1239303. - DOI - PMC - PubMed