Inoue Kentaro, Shimozono Shinichi, Yoshida Hideaki, Kurata Hiroyuki
Department of Bioscience and Bioinformatics, Kyushu Institute of Technology, Iizuka, Fukuoka, Japan.
PLoS One. 2012;7(6):e37739. doi: 10.1371/journal.pone.0037739. Epub 2012 Jun 5.
For visualizing large-scale biochemical network maps, it is important to calculate the coordinates of molecular nodes quickly and to enhance the understanding or traceability of them. The grid layout is effective in drawing compact, orderly, balanced network maps with node label spaces, but existing grid layout algorithms often require a high computational cost because they have to consider complicated positional constraints through the entire optimization process.
We propose a hybrid grid layout algorithm that consists of a non-grid, fast layout (preprocessor) algorithm and an approximate pattern matching algorithm that distributes the resultant preprocessed nodes on square grid points. To demonstrate the feasibility of the hybrid layout algorithm, it is characterized in terms of the calculation time, numbers of edge-edge and node-edge crossings, relative edge lengths, and F-measures. The proposed algorithm achieves outstanding performances compared with other existing grid layouts.
Use of an approximate pattern matching algorithm quickly redistributes the laid-out nodes by fast, non-grid algorithms on the square grid points, while preserving the topological relationships among the nodes. The proposed algorithm is a novel use of the pattern matching, thereby providing a breakthrough for grid layout. This application program can be freely downloaded from http://www.cadlive.jp/hybridlayout/hybridlayout.html.
为了可视化大规模生化网络图谱，快速计算分子节点的坐标并增强对它们的理解或可追溯性非常重要。网格布局在绘制具有节点标签空间的紧凑、有序、平衡的网络图谱方面很有效，但现有的网格布局算法通常需要很高的计算成本，因为它们在整个优化过程中必须考虑复杂的位置约束。
我们提出了一种混合网格布局算法，它由非网格快速布局（预处理程序）算法和将预处理后的节点分布在正方形网格点上的近似模式匹配算法组成。为了证明混合布局算法的可行性，从计算时间、边与边以及节点与边的交叉数、相对边长和F值等方面对其进行了表征。与其他现有的网格布局相比，该算法具有出色的性能。
使用近似模式匹配算法可以通过快速的非网格算法将布局好的节点快速重新分布在正方形网格点上，同时保留节点之间的拓扑关系。该算法是模式匹配的一种新颖应用，从而为网格布局提供了突破。此应用程序可从http://www.cadlive.jp/hybridlayout/hybridlayout.html免费下载。
