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.


Two groups of nodes: 2, 4 and 1, 3, 5. The tablet is storage format of network after compression.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig5: Two groups of nodes: 2, 4 and 1, 3, 5. The tablet is storage format of network after compression.

Mentions: In FigureĀ 5, v1, v2 represent vertex 1 and 2, respectively, and they are the remaining vertex after compression, e1 is the edge linking v1 and v2. Gr, Gp, Gcv represent the nodes and edges that remain after compression, the parity nodes that are removed and the vertex and edges connected with the parity nodes, respectively. Upon finishing the compression, we conduct a sub-graph search. At this point, we shall see that the space we need to search is considerably reduced. If we want to search a sub-graph with a specific topological structure, for instance (1,2,5), we need not go through the whole graph to find all sub-graphs with this topology, meaning that searching for sub-graphs like (2,3,5), (1,2,2), (1,4,5), (3,4,5), (1,3,4) is unnecessary. The aforementioned sub-graphs can be stored in Gcv and Gp. What we need to do is replace the parity nodes correspondingly and make sure there is no repeating. In this way the searching time is reduced.Figure 5


Motif mining based on network space compression.

Zhang Q, Xu Y - BioData Min (2014)

Two groups of nodes: 2, 4 and 1, 3, 5. The tablet is storage format of network after compression.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig5: Two groups of nodes: 2, 4 and 1, 3, 5. The tablet is storage format of network after compression.
Mentions: In FigureĀ 5, v1, v2 represent vertex 1 and 2, respectively, and they are the remaining vertex after compression, e1 is the edge linking v1 and v2. Gr, Gp, Gcv represent the nodes and edges that remain after compression, the parity nodes that are removed and the vertex and edges connected with the parity nodes, respectively. Upon finishing the compression, we conduct a sub-graph search. At this point, we shall see that the space we need to search is considerably reduced. If we want to search a sub-graph with a specific topological structure, for instance (1,2,5), we need not go through the whole graph to find all sub-graphs with this topology, meaning that searching for sub-graphs like (2,3,5), (1,2,2), (1,4,5), (3,4,5), (1,3,4) is unnecessary. The aforementioned sub-graphs can be stored in Gcv and Gp. What we need to do is replace the parity nodes correspondingly and make sure there is no repeating. In this way the searching time is reduced.Figure 5

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.