Limits...
Application of approximate pattern matching in two dimensional spaces to grid layout for biochemical network maps.

Inoue K, Shimozono S, Yoshida H, Kurata H - PLoS ONE (2012)

Bottom Line: 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.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.

View Article: PubMed Central - PubMed

Affiliation: Department of Bioscience and Bioinformatics, Kyushu Institute of Technology, Iizuka, Fukuoka, Japan.

ABSTRACT

Background: 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.

Results: 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.

Conclusions: 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.

Show MeSH

Related in: MedlinePlus

The metabolic network maps drawn by hybrid grid layout algorithms.A: The nucleotide metabolism network maps (Nodes: 160, Edges: 236). B: The amino acid and nucleotide metabolic network maps (Nodes: 922, Edges: 1290). Four types of the hybrid layout algorithms (SA, KK, FR, and GA) are used. Random layout (R), our grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed as reference algorithms. Here, their network maps are drawn by simple representation using circles and lines in the MATLAB program. GL in the network (B) does not build any network map due to the calculation complexity.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368000&req=5

pone-0037739-g002: The metabolic network maps drawn by hybrid grid layout algorithms.A: The nucleotide metabolism network maps (Nodes: 160, Edges: 236). B: The amino acid and nucleotide metabolic network maps (Nodes: 922, Edges: 1290). Four types of the hybrid layout algorithms (SA, KK, FR, and GA) are used. Random layout (R), our grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed as reference algorithms. Here, their network maps are drawn by simple representation using circles and lines in the MATLAB program. GL in the network (B) does not build any network map due to the calculation complexity.

Mentions: To investigate the performance of the hybrid layout algorithms with different preprocessors, SA, KK, FR and GA, they are applied to drawing of metabolic network maps with different sizes, as shown in Figure 2. As reference methods, a random layout (R), our original grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed. In the random layout algorithm, nodes are uniformly and randomly distributed in the given square area, as expected. On the other hand, the node distributions by the hybrid algorithms and reference ones show specific topological features, such as heterogeneous distributions and modular structures, respectively. Selection of the preprocessor algorithms, which calculate a coarse layout that gives a relative position to each node, affected the calculation speed and topology of the resultant layouts.


Application of approximate pattern matching in two dimensional spaces to grid layout for biochemical network maps.

Inoue K, Shimozono S, Yoshida H, Kurata H - PLoS ONE (2012)

The metabolic network maps drawn by hybrid grid layout algorithms.A: The nucleotide metabolism network maps (Nodes: 160, Edges: 236). B: The amino acid and nucleotide metabolic network maps (Nodes: 922, Edges: 1290). Four types of the hybrid layout algorithms (SA, KK, FR, and GA) are used. Random layout (R), our grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed as reference algorithms. Here, their network maps are drawn by simple representation using circles and lines in the MATLAB program. GL in the network (B) does not build any network map due to the calculation complexity.
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3368000&req=5

pone-0037739-g002: The metabolic network maps drawn by hybrid grid layout algorithms.A: The nucleotide metabolism network maps (Nodes: 160, Edges: 236). B: The amino acid and nucleotide metabolic network maps (Nodes: 922, Edges: 1290). Four types of the hybrid layout algorithms (SA, KK, FR, and GA) are used. Random layout (R), our grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed as reference algorithms. Here, their network maps are drawn by simple representation using circles and lines in the MATLAB program. GL in the network (B) does not build any network map due to the calculation complexity.
Mentions: To investigate the performance of the hybrid layout algorithms with different preprocessors, SA, KK, FR and GA, they are applied to drawing of metabolic network maps with different sizes, as shown in Figure 2. As reference methods, a random layout (R), our original grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed. In the random layout algorithm, nodes are uniformly and randomly distributed in the given square area, as expected. On the other hand, the node distributions by the hybrid algorithms and reference ones show specific topological features, such as heterogeneous distributions and modular structures, respectively. Selection of the preprocessor algorithms, which calculate a coarse layout that gives a relative position to each node, affected the calculation speed and topology of the resultant layouts.

Bottom Line: 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.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.

View Article: PubMed Central - PubMed

Affiliation: Department of Bioscience and Bioinformatics, Kyushu Institute of Technology, Iizuka, Fukuoka, Japan.

ABSTRACT

Background: 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.

Results: 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.

Conclusions: 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.

Show MeSH
Related in: MedlinePlus