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

Characterization of hybrid layout algorithms.(A) calculation speed, (B) ratio of edge-edge crossings, (C) ratio of node-edge crossings, (D) relative edge length, (E) connectivity F-measure, and (F) functional F-measure. Four types of the hybrid layout algorithms (SA, KK, FR, and GA) are used. As reference methods, a random layout (R), our original grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368000&req=5

pone-0037739-g003: Characterization of hybrid layout algorithms.(A) calculation speed, (B) ratio of edge-edge crossings, (C) ratio of node-edge crossings, (D) relative edge length, (E) connectivity F-measure, and (F) functional F-measure. Four types of the hybrid layout algorithms (SA, KK, FR, and GA) are used. As reference methods, a random layout (R), our original grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed.

Mentions: First, the calculation speed for the hybrid algorithms was evaluated as shown in Figure 3A. GL required lots of calculation time and could practically not calculate any map with more than several hundred nodes, while its topological performances were very good (Figure 3B, C, D, E, F). LD, an improved version of GL, calculated layouts faster than GL, but it was still slower than the hybrid layout algorithms. The two hybrid grid layout algorithms (FR and GA) were faster than CE or comparable to it, indicating that the hybrid algorithms can greatly increase the calculation speed. Although a random layout algorithm (R) was very fast, the geometric performance was very poor (Figure 3B, C, D, E, F). The approximate pattern matching for KK, FR, and GA was very fast, thus their calculation time depended on selection of the preprocessors (Figure 4). FR presented the highest calculation speed. On the other hand, SA was slowest and its pattern matching required a long time. It is because the spectral analysis provided highly heterogeneous node distributions (Figure 2), which make it hard to find vacant grid points. The speed of the pattern matching is suggested to be fast for the homogeneous node distributions generated by FR (Figure 2, Figure 4).


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)

Characterization of hybrid layout algorithms.(A) calculation speed, (B) ratio of edge-edge crossings, (C) ratio of node-edge crossings, (D) relative edge length, (E) connectivity F-measure, and (F) functional F-measure. Four types of the hybrid layout algorithms (SA, KK, FR, and GA) are used. As reference methods, a random layout (R), our original grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037739-g003: Characterization of hybrid layout algorithms.(A) calculation speed, (B) ratio of edge-edge crossings, (C) ratio of node-edge crossings, (D) relative edge length, (E) connectivity F-measure, and (F) functional F-measure. Four types of the hybrid layout algorithms (SA, KK, FR, and GA) are used. As reference methods, a random layout (R), our original grid layout (GL), LucidDraw (LD), and Cerebral (CE) are employed.
Mentions: First, the calculation speed for the hybrid algorithms was evaluated as shown in Figure 3A. GL required lots of calculation time and could practically not calculate any map with more than several hundred nodes, while its topological performances were very good (Figure 3B, C, D, E, F). LD, an improved version of GL, calculated layouts faster than GL, but it was still slower than the hybrid layout algorithms. The two hybrid grid layout algorithms (FR and GA) were faster than CE or comparable to it, indicating that the hybrid algorithms can greatly increase the calculation speed. Although a random layout algorithm (R) was very fast, the geometric performance was very poor (Figure 3B, C, D, E, F). The approximate pattern matching for KK, FR, and GA was very fast, thus their calculation time depended on selection of the preprocessors (Figure 4). FR presented the highest calculation speed. On the other hand, SA was slowest and its pattern matching required a long time. It is because the spectral analysis provided highly heterogeneous node distributions (Figure 2), which make it hard to find vacant grid points. The speed of the pattern matching is suggested to be fast for the homogeneous node distributions generated by FR (Figure 2, Figure 4).

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