Limits...
Motif mining based on network space compression.

Zhang Q, Xu Y - BioData Min (2014)

Bottom Line: The considerable computational and spacial complexity also presents a significant challenge.According to the characteristic of the parity nodes, we cut down the searching space and storage space in real graphs and random graphs, thereby reducing the computational cost of verifying the isomorphism of sub-graphs.Experimental results show that this algorithm has higher speed and better stability than its alternatives.

View Article: PubMed Central - PubMed

Affiliation: Key Laboratory of Advanced Design and Intelligent Computing, (Dalian university), Ministry of Education, Dalian, 116622 China.

ABSTRACT
A network motif is a recurring subnetwork within a network, and it takes on certain functions in practical biological macromolecule applications. Previous algorithms have focused on the computational efficiency of network motif detection, but some problems in storage space and searching time manifested during earlier studies. The considerable computational and spacial complexity also presents a significant challenge. In this paper, we provide a new approach for motif mining based on compressing the searching space. According to the characteristic of the parity nodes, we cut down the searching space and storage space in real graphs and random graphs, thereby reducing the computational cost of verifying the isomorphism of sub-graphs. We obtain a new network with smaller size after removing parity nodes and the "repeated edges" connected with the parity nodes. Random graph structure and sub-graph searching are based on the Back Tracking Method; all sub-graphs can be searched for by adding edges progressively. Experimental results show that this algorithm has higher speed and better stability than its alternatives.

No MeSH data available.


Comparison of results from different algorithms. The height of the blue cuboid is the consumption time before compressing the network, while the green cuboid is the consumption time after compressing the network. They are compared with the red cuboid (Rand-ESU in paper [26]). The x-coordinate denotes the size of sub-graph, the y-coordinate denotes the searching time.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4269098&req=5

Fig6: Comparison of results from different algorithms. The height of the blue cuboid is the consumption time before compressing the network, while the green cuboid is the consumption time after compressing the network. They are compared with the red cuboid (Rand-ESU in paper [26]). The x-coordinate denotes the size of sub-graph, the y-coordinate denotes the searching time.

Mentions: In the previous sections, we have confirmed the effectiveness, accuracy and extensive applicability of our method. We have also confirmed the smaller search space and storage space obtained through the compression of parity nodes. In this section, we will compare the results obtained with our algorithm with those from alternative methods [5,7,17,26]. Due to the limitations of the Feature compression for clustering graphs (FCGI) algorithm [26], we only tested and compared the Yeast network, and due to the limitations of network data just the results obtained for the E. coli network were compared to the other algorithms [5,7,17]. The comparison results are displayed in Figure 6 and Table 4.Figure 6


Motif mining based on network space compression.

Zhang Q, Xu Y - BioData Min (2014)

Comparison of results from different algorithms. The height of the blue cuboid is the consumption time before compressing the network, while the green cuboid is the consumption time after compressing the network. They are compared with the red cuboid (Rand-ESU in paper [26]). The x-coordinate denotes the size of sub-graph, the y-coordinate denotes the searching time.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4269098&req=5

Fig6: Comparison of results from different algorithms. The height of the blue cuboid is the consumption time before compressing the network, while the green cuboid is the consumption time after compressing the network. They are compared with the red cuboid (Rand-ESU in paper [26]). The x-coordinate denotes the size of sub-graph, the y-coordinate denotes the searching time.
Mentions: In the previous sections, we have confirmed the effectiveness, accuracy and extensive applicability of our method. We have also confirmed the smaller search space and storage space obtained through the compression of parity nodes. In this section, we will compare the results obtained with our algorithm with those from alternative methods [5,7,17,26]. Due to the limitations of the Feature compression for clustering graphs (FCGI) algorithm [26], we only tested and compared the Yeast network, and due to the limitations of network data just the results obtained for the E. coli network were compared to the other algorithms [5,7,17]. The comparison results are displayed in Figure 6 and Table 4.Figure 6

Bottom Line: The considerable computational and spacial complexity also presents a significant challenge.According to the characteristic of the parity nodes, we cut down the searching space and storage space in real graphs and random graphs, thereby reducing the computational cost of verifying the isomorphism of sub-graphs.Experimental results show that this algorithm has higher speed and better stability than its alternatives.

View Article: PubMed Central - PubMed

Affiliation: Key Laboratory of Advanced Design and Intelligent Computing, (Dalian university), Ministry of Education, Dalian, 116622 China.

ABSTRACT
A network motif is a recurring subnetwork within a network, and it takes on certain functions in practical biological macromolecule applications. Previous algorithms have focused on the computational efficiency of network motif detection, but some problems in storage space and searching time manifested during earlier studies. The considerable computational and spacial complexity also presents a significant challenge. In this paper, we provide a new approach for motif mining based on compressing the searching space. According to the characteristic of the parity nodes, we cut down the searching space and storage space in real graphs and random graphs, thereby reducing the computational cost of verifying the isomorphism of sub-graphs. We obtain a new network with smaller size after removing parity nodes and the "repeated edges" connected with the parity nodes. Random graph structure and sub-graph searching are based on the Back Tracking Method; all sub-graphs can be searched for by adding edges progressively. Experimental results show that this algorithm has higher speed and better stability than its alternatives.

No MeSH data available.