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 image of the hybrid grid layout algorithm.A. An ordinary or preprocessor algorithm draws a network map where the node labels may overlap. B. An approximate pattern matching algorithm finds a one-to-one, exclusive correspondence between a set (pattern) of graph nodes and a set of the grid points with the minimum axis-parallel insertions and deletions of space. C. The spaces of text labels are ensured.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368000&req=5

pone-0037739-g001: An image of the hybrid grid layout algorithm.A. An ordinary or preprocessor algorithm draws a network map where the node labels may overlap. B. An approximate pattern matching algorithm finds a one-to-one, exclusive correspondence between a set (pattern) of graph nodes and a set of the grid points with the minimum axis-parallel insertions and deletions of space. C. The spaces of text labels are ensured.

Mentions: A biochemical network map can generally be converted into a graph to calculate the geometric coordinates of the molecules (nodes). The network graph consisting of N nodes and undirected edges (interactions) are described by an N by N adjacency matrix (, ). When there is an edge from a node i to another node j, then its element is 1, otherwise . To draw the network map, it is necessary to calculate the x-y coordinates of N nodes . Practically, the text labels showing molecular names are critically important to trace the pathways of interest. It is important to secure the space necessary for node labels, but ordinary layout algorithms do not consider the label space. To obtain a view of a large-scale network graph whose nodes have text labels without any overlaps of them in a compact space, we propose the hybrid layout algorithm that maps molecular nodes on the grid points, while enhancing their topological quality, as shown in Figure 1 and Table 1.


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 image of the hybrid grid layout algorithm.A. An ordinary or preprocessor algorithm draws a network map where the node labels may overlap. B. An approximate pattern matching algorithm finds a one-to-one, exclusive correspondence between a set (pattern) of graph nodes and a set of the grid points with the minimum axis-parallel insertions and deletions of space. C. The spaces of text labels are ensured.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037739-g001: An image of the hybrid grid layout algorithm.A. An ordinary or preprocessor algorithm draws a network map where the node labels may overlap. B. An approximate pattern matching algorithm finds a one-to-one, exclusive correspondence between a set (pattern) of graph nodes and a set of the grid points with the minimum axis-parallel insertions and deletions of space. C. The spaces of text labels are ensured.
Mentions: A biochemical network map can generally be converted into a graph to calculate the geometric coordinates of the molecules (nodes). The network graph consisting of N nodes and undirected edges (interactions) are described by an N by N adjacency matrix (, ). When there is an edge from a node i to another node j, then its element is 1, otherwise . To draw the network map, it is necessary to calculate the x-y coordinates of N nodes . Practically, the text labels showing molecular names are critically important to trace the pathways of interest. It is important to secure the space necessary for node labels, but ordinary layout algorithms do not consider the label space. To obtain a view of a large-scale network graph whose nodes have text labels without any overlaps of them in a compact space, we propose the hybrid layout algorithm that maps molecular nodes on the grid points, while enhancing their topological quality, as shown in Figure 1 and Table 1.

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