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

An amino acid and nucleotide metabolism network map (Nodes: 922, Edges: 1290) drawn by BNV2.0.The node coordinates are calculated by the hybrid layout algorithm (GA), which presents the best score (0.49) of the functional F-measure. There are 24 modules in the map, where the nodes in each module are marked in different colors.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368000&req=5

pone-0037739-g005: An amino acid and nucleotide metabolism network map (Nodes: 922, Edges: 1290) drawn by BNV2.0.The node coordinates are calculated by the hybrid layout algorithm (GA), which presents the best score (0.49) of the functional F-measure. There are 24 modules in the map, where the nodes in each module are marked in different colors.

Mentions: Fifth, the connectivity F-measure was evaluated as shown in Figure 3E. R showed the lowest value for all the networks, as had been expected. LD presented the highest connectivity F-measure. For all the networks, the connectivity F-measures by FR and GA were comparable to it and higher than those by CE, respectively. Finally, the functional F-measure was evaluated in terms of biologically functional modules annotated by KEGG (Glycolysis, TCA cycle, Pentose phosphate, etc.), as shown in Figure 3F. For most of the networks, the functional F-measures by KK, FR and GA were higher than those by CE. GA presented the highest functional F-measure. To visually demonstrate how the drawn network maps by GA are related to biological functions, the amino acid and nucleotide metabolism network (the network of number 13 in the Table 2) was illustrated in Figure 5. The nodes are marked by BNV2.0 in different colors according to biological functions, clearly presenting biologically related cluster structures. It presents the highest score (0.49) for the functional F-measure.


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)

An amino acid and nucleotide metabolism network map (Nodes: 922, Edges: 1290) drawn by BNV2.0.The node coordinates are calculated by the hybrid layout algorithm (GA), which presents the best score (0.49) of the functional F-measure. There are 24 modules in the map, where the nodes in each module are marked in different colors.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037739-g005: An amino acid and nucleotide metabolism network map (Nodes: 922, Edges: 1290) drawn by BNV2.0.The node coordinates are calculated by the hybrid layout algorithm (GA), which presents the best score (0.49) of the functional F-measure. There are 24 modules in the map, where the nodes in each module are marked in different colors.
Mentions: Fifth, the connectivity F-measure was evaluated as shown in Figure 3E. R showed the lowest value for all the networks, as had been expected. LD presented the highest connectivity F-measure. For all the networks, the connectivity F-measures by FR and GA were comparable to it and higher than those by CE, respectively. Finally, the functional F-measure was evaluated in terms of biologically functional modules annotated by KEGG (Glycolysis, TCA cycle, Pentose phosphate, etc.), as shown in Figure 3F. For most of the networks, the functional F-measures by KK, FR and GA were higher than those by CE. GA presented the highest functional F-measure. To visually demonstrate how the drawn network maps by GA are related to biological functions, the amino acid and nucleotide metabolism network (the network of number 13 in the Table 2) was illustrated in Figure 5. The nodes are marked by BNV2.0 in different colors according to biological functions, clearly presenting biologically related cluster structures. It presents the highest score (0.49) for the functional F-measure.

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