An efficient grid layout algorithm for biological networks utilizing various biological attributesReport as inadecuate

An efficient grid layout algorithm for biological networks utilizing various biological attributes - Download this document for free, or read online. Document in PDF available to download.

BMC Bioinformatics

, 8:76

First Online: 06 March 2007Received: 23 October 2006Accepted: 06 March 2007


BackgroundClearly 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.

ResultsWe 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ïve 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.

ConclusionLayouts 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.

Electronic supplementary materialThe online version of this article doi:10.1186-1471-2105-8-76 contains supplementary material, which is available to authorized users.

Kaname Kojima, Masao Nagasaki contributed equally to this work.

Download fulltext PDF

Author: Kaname Kojima - Masao Nagasaki - Euna Jeong - Mitsuru Kato - Satoru Miyano



Related documents