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

BMC Bioinformatics

Satoru Miyano¹  Masao Nagasaki¹  Kaname Kojima¹ 

[1]Human Genome Center, Institute of Medical Science, University of Tokyo, 4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan

Others  :  1165097
DOI  :  10.1186/1471-2105-11-335

 received in 2009-12-01, accepted in 2010-06-18,  发布年份 2010

【 摘 要 】

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.

【 授权许可】

   
2010 Kojima et al; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Figure 9.

Figure 10.

Figure 11.

Figure 12.

【 参考文献 】

• [1]Kanehisa M: The KEGG database. Novartis Found Symposium 2002, 247:91-101.
• [2]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.
• [3]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.
• [4]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.
• [5]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.
• [6]Demir E, Babur O, Dogrusoz U, Gursoy A, Nisanci G, Atalay RC, Ozturk M: PATIKA: an integrated visual environment for collaborative construction and analysis of cellular pathways. Bioinformatics 2002, 18(7):996-1003.
• [7]Dogrusoz U, Erson EZ, Giral E, Demir E, Babur O, Cetintas A, Colak R: PATIKAweb: a Web interface for analyzing biological pathways through advanced querying and visualization. Bioinformatics 2006, 22(3):374-375.
• [8]Kurata H, Matoba N, Shimizu N: CADLIVE for constructing a large-scale biochemical network based on a simulation-directed notation and its application to yeast cell cycle. Nucleic Acids Research 2003, 31(14):4071-4084.
• [9]Kurata H, Masaki K, Sumida Y, Iwasaki R: CADLIVE dynamic simulator: direct link of biochemical networks to dynamic models. Genome Research 2005, 15(4):590-600.
• [10]Karp PD, Paley SM: Automated drawing of metabolic pathways. Proceedings of the 3rd International Conference on Bioinformatics and Genome Research 1994, 225-238.
• [11]Becker MY, Rojas I: A graph layout algorithm for drawing metabolic pathways. Bioinformatics 2001, 17(5):461-467.
• [12]Wegner K, Kummer U: A new dynamical layout algorithm for complex biochemical reaction networks. BMC Bioinformatics 2005., 6(212)
• [13]Gauges R, Rost U, Sahle S, Wegner K: A model diagram layout extension for SBML. Bioinformatics 2006, 22(15):1879-1885.
• [14]Genc B, Dogrusoz U: A constrained, force-directed layout algorithm for biological pathways. Graph Drawing 2003, 314-319.
• [15]Dogrusoz U, Gral E, Cetintas A, Civril A, Demir E: A compound graph layout algorithm for biological pathways. Graph Drawing 2004, 442-447.
• [16]Garcia O, Saveanu C, Cline M, Fromont-Racine M, Jacquier A, Schwikowski B, Aittokallio T: GOlorize: a Cytoscape plug-in for network visualization with Gene Ontology-based layout and coloring. Bioinformatics 2007, 23(3):394-396.
• [17]Deckard A, Bergmann FT, Sauro HM: Supporting the SBML layout extension. Bioinformatics 2006, 22(23):2966-2967.
• [18]Schreiber F, Dwyer T, Marriott K, Wybrow M: A generic algorithm for layout of biological networks. BMC Bioinformatics 2009., 10(375)
• [19]Li W, Kurata H: A grid layout algorithm for automatic drawing of biochemical networks. Bioinformatics 2005, 21(9):2036-2042.
• [20]Kato K, Nagasaki M, Doi A, Miyano S: Automatic drawing of biological networks using cross cost and subcomponent data. Genome Informatics 2005, 16(2):22-31.
• [21]Kojima K, Nagasaki M, Jeong E, Kato M, Miyano S: An efficient grid layout algorithm for biological networks utilizing various biological attributes. BMC Bioinformatics 2007., 8(76)
• [22]Kojima K, Nagasaki M, Miyano S: Fast grid layout algorithm with sweep calculation. Bioinformatics 2008, 24(12):1433-1441.
• [23]Gary MR, Johnson DS: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods 1983, 4:312-316.
• [24]Barsky A, Gardy JL, Hancock REW, Munzner T: Cerebral: a Cytoscape plugin for layout of and interaction with biological networks using subcellular localization annotation. Bioinformatics 2007, 23:1040-1042.
• [25]Tunkelang D: JIGGLE: Java interactive graph layout environment. Graph Drawing 1998, 412-422.
• [26]Pober JS: Endothelial activation: Intracellular signaling pathways. Arthritis Research 2002, 4(Suppl 3):S109-116. BioMed Central Full Text
• [27]Matsuno H, Tanaka Y, Aoshima H, Doi A, Matsui M, Miyano S: Biopathways representation and simulation on hybrid functional Petri net. In Silico Biology 2003, 3(3):389-404.
• [28]Saito A, Nagasaki M, Doi A, Ueno K, Miyano S: Cell fate simulation model of gustatory neurons with microRNAs double-negative feedback loop by hybrid functional Petri net with extension. Genome Informatics 2006, 17:100-111.
• [29]Chazelle B: Reporting and counting segment intersections. Journal of Computer and System Sciences 1986, 32:156-182.
• [30]Palazzi L, Snoeyink J: Counting and reporting red/blue segment intersections. CVGIP: Graphical Models and Image Processing 1993, 56:304-310.
• [31]Cheng SW, Janardan R: Space-efficient ray-shooting and intersection searching: Algorithms, dynamization, and applications. 2nd annual ACM-SIAM symposium on Discrete algorithms 1991, 7-16.
• [32]Jeong L, Mason S, Barabási AL, Oltvai NZ: Lethality and centrality in protein networks. Nature 2001, 411:41-42.