{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:29:54Z","timestamp":1742387394118},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Clearly visualized biopathways provide a great help in understanding biological systems. However, manual drawing of large-scale biopathways is time consuming. We proposed a grid layout algorithm that can handle gene-regulatory networks and signal transduction pathways by considering edge-edge crossing, node-edge crossing, distance measure between nodes, and subcellular localization information from Gene Ontology. Consequently, the layout algorithm succeeded in drastically reducing these crossings in the apoptosis model. However, for larger-scale networks, we encountered three problems: (i) the initial layout is often very far from any local optimum because nodes are initially placed at random, (ii) from a biological viewpoint, human layouts still exceed automatic layouts in understanding because except subcellular localization, it does not fully utilize biological information of pathways, and (iii) it employs a local search strategy in which the neighborhood is obtained by moving one node at each step, and automatic layouts suggest that simultaneous movements of multiple nodes are necessary for better layouts, while such extension may face worsening the time complexity.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We propose a new grid layout algorithm. To address problem (i), we devised a new force-directed algorithm whose output is suitable as the initial layout. For (ii), we considered that an appropriate alignment of nodes having the same biological attribute is one of the most important factors of the comprehension, and we defined a new score function that gives an advantage to such configurations. For solving problem (iii), we developed a search strategy that considers swapping nodes as well as moving a node, while keeping the order of the time complexity. Though a na\u00efve implementation increases by one order, the time complexity, we solved this difficulty by devising a method that caches differences between scores of a layout and its possible updates.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>Layouts of the new grid layout algorithm are compared with that of the previous algorithm and human layout in an endothelial cell model, three times as large as the apoptosis model. The total cost of the result from the new grid layout algorithm is similar to that of the human layout. In addition, its convergence time is drastically reduced (40% reduction).<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-8-76","type":"journal-article","created":{"date-parts":[[2007,3,6]],"date-time":"2007-03-06T07:03:31Z","timestamp":1173164611000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["An efficient grid layout algorithm for biological networks utilizing various biological attributes"],"prefix":"10.1186","volume":"8","author":[{"given":"Kaname","family":"Kojima","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masao","family":"Nagasaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Euna","family":"Jeong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mitsuru","family":"Kato","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satoru","family":"Miyano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,3,6]]},"reference":[{"issue":"3","key":"1448_CR1","first-page":"181","volume":"2","author":"M Nagasaki","year":"2003","unstructured":"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\u2013184.","journal-title":"Applied Bioinformatics"},{"issue":"3","key":"1448_CR2","first-page":"185","volume":"2","author":"A Doi","year":"2003","unstructured":"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\u2013188.","journal-title":"Applied Bioinformatics"},{"issue":"11","key":"1448_CR3","doi-asserted-by":"publisher","first-page":"2498","DOI":"10.1101\/gr.1239303","volume":"13","author":"P Shannon","year":"2003","unstructured":"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\u20132504. 10.1101\/gr.1239303","journal-title":"Genome Research"},{"key":"1448_CR4","unstructured":"Networks\/Pajek[http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/pajek\/]"},{"issue":"7","key":"1448_CR5","doi-asserted-by":"publisher","first-page":"996","DOI":"10.1093\/bioinformatics\/18.7.996","volume":"18","author":"E Demir","year":"2002","unstructured":"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\u20131003. 10.1093\/bioinformatics\/18.7.996","journal-title":"Bioinformatics"},{"issue":"3","key":"1448_CR6","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1093\/bioinformatics\/bti776","volume":"22","author":"U Dogrusoz","year":"2006","unstructured":"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\u2013375. 10.1093\/bioinformatics\/bti776","journal-title":"Bioinformatics"},{"issue":"14","key":"1448_CR7","doi-asserted-by":"publisher","first-page":"4071","DOI":"10.1093\/nar\/gkg461","volume":"31","author":"H Kurata","year":"2003","unstructured":"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\u20134084. 10.1093\/nar\/gkg461","journal-title":"Nucleic Acids Research"},{"issue":"4","key":"1448_CR8","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1101\/gr.3463705","volume":"15","author":"H Kurata","year":"2005","unstructured":"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\u2013600. 10.1101\/gr.3463705","journal-title":"Genome Research"},{"key":"1448_CR9","first-page":"111","volume-title":"Proceedings of the 11th International Symposium on Graph Drawing","author":"U Brandes","year":"2003","unstructured":"Brandes U, Dwyer T, Schreiber F: Visualizing related metabolic pathways in two and a half dimensions. Proceedings of the 11th International Symposium on Graph Drawing 2003, 111\u2013122."},{"key":"1448_CR10","first-page":"225","volume-title":"Proceedings of the 3rd International Conference on Bioinformatics and Genome Research","author":"PD Karp","year":"1994","unstructured":"Karp PD, Paley SM: Automated drawing of metabolic pathways. Proceedings of the 3rd International Conference on Bioinformatics and Genome Research 1994, 225\u2013238."},{"issue":"5","key":"1448_CR11","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1093\/bioinformatics\/17.5.461","volume":"17","author":"MY Becker","year":"2001","unstructured":"Becker MY, Rojas I: A graph layout algorithm for drawing metabolic pathways. Bioinformatics 2001, 17(5):461\u2013467. 10.1093\/bioinformatics\/17.5.461","journal-title":"Bioinformatics"},{"issue":"Suppl 2","key":"1448_CR12","doi-asserted-by":"publisher","first-page":"S219","DOI":"10.1093\/bioinformatics\/18.suppl_2.S219","volume":"18","author":"M Sirava","year":"2002","unstructured":"Sirava M, Schafer T, Eiglsperger M, Kaufmann M, Kohlgacher O, Bornberg-Bauer E, Lenhof HP: BioMiner-modeling, analyzing, and visualizing biochemical pathways and networks. Bioinformatics 2002, 18(Suppl 2):S219\u2013230.","journal-title":"Bioinformatics"},{"key":"1448_CR13","volume-title":"BMC Bioinformatics","author":"K Wegner","year":"2005","unstructured":"Wegner K, Kummer U: A new dynamical layout algorithm for complex biochemical reaction networks. BMC Bioinformatics 2005., 6(212):"},{"issue":"9","key":"1448_CR14","doi-asserted-by":"publisher","first-page":"2036","DOI":"10.1093\/bioinformatics\/bti290","volume":"21","author":"W Li","year":"2005","unstructured":"Li W, Kurata H: A grid layout algorithm for automatic drawing of biochemical networks. Bioinformatics 2005, 21(9):2036\u20132042. 10.1093\/bioinformatics\/bti290","journal-title":"Bioinformatics"},{"issue":"2","key":"1448_CR15","first-page":"22","volume":"16","author":"M Kato","year":"2005","unstructured":"Kato M, Nagasaki M, Doi A, Miyano S: Automatic drawing of biological networks using cross cost and subcomponent data. Genome Informatics 2005, 16(2):22\u201331.","journal-title":"Genome Informatics"},{"key":"1448_CR16","first-page":"314","volume-title":"Proceedings of the 11th International Symposium on Graph Drawing","author":"B Genc","year":"2003","unstructured":"Genc B, Dogrusoz U: A constrained, force-directed layout algorithm for biological pathways. Proceedings of the 11th International Symposium on Graph Drawing 2003, 314\u2013319."},{"key":"1448_CR17","first-page":"442","volume-title":"Proceedings of the 12th International Symposium on Graph Drawing","author":"U Dogrusoz","year":"2004","unstructured":"Dogrusoz U, Gral E, Cetintas A, Civril A, Demir E: A compound graph layout algorithm for biological pathways. Proceedings of the 12th International Symposium on Graph Drawing 2004, 442\u2013447."},{"key":"1448_CR18","first-page":"149","volume":"42","author":"P Eades","year":"1984","unstructured":"Eades P: A heuristic for graph drawing. Congressus Nemerantium 1984, 42: 149\u2013160.","journal-title":"Congressus Nemerantium"},{"issue":"Suppl 3","key":"1448_CR19","doi-asserted-by":"publisher","first-page":"S109","DOI":"10.1186\/ar576","volume":"4","author":"JS Pober","year":"2002","unstructured":"Pober JS: Endothelial activation: Intracellular signaling pathways. Arthritis Research 2002, 4(Suppl 3):S109\u2013116. 10.1186\/ar576","journal-title":"Arthritis Research"},{"issue":"3","key":"1448_CR20","first-page":"389","volume":"3","author":"H Matsuno","year":"2003","unstructured":"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\u2013404.","journal-title":"In Silico Biology"},{"key":"1448_CR21","first-page":"100","volume":"17","author":"A Saito","year":"2006","unstructured":"Saito A, Nagasaki M, Doi A, Ueno K, Miyano S: Cell fate simulation model of gustatory nuerons with microRNAs double-negative feedback loop by hybrid functional Petri net with extension. Genome Informatics 2006, 17: 100\u2013111.","journal-title":"Genome Informatics"},{"key":"1448_CR22","unstructured":"[http:\/\/www.csml.org\/download\/SCCBLayout_BMC_inst.exe]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-8-76.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T01:36:53Z","timestamp":1630460213000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-8-76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3,6]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["1448"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-8-76","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,3,6]]},"assertion":[{"value":"23 October 2006","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"76"}}