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.


Related in: MedlinePlus

The nodes 2 and 4 are parity nodes. After exchanging their positions, the associated matrices remain similar and these two matrices can get into the same form by elementary transformation, thus possessing the same Code.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig4: The nodes 2 and 4 are parity nodes. After exchanging their positions, the associated matrices remain similar and these two matrices can get into the same form by elementary transformation, thus possessing the same Code.

Mentions: It appears that there is more than one parity node in a graph. The structure and function of these nodes are similar, and the topological network characteristics of these nodes are completely the same. According to the features of the parity nodes, exchanging two nodes doesn’t affect the topological structure of the whole network. This means that the corresponding associated matrices are similar after exchanging the parity nodes, as can be seen in Figure 4.Figure 4


Motif mining based on network space compression.

Zhang Q, Xu Y - BioData Min (2014)

The nodes 2 and 4 are parity nodes. After exchanging their positions, the associated matrices remain similar and these two matrices can get into the same form by elementary transformation, thus possessing the same Code.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig4: The nodes 2 and 4 are parity nodes. After exchanging their positions, the associated matrices remain similar and these two matrices can get into the same form by elementary transformation, thus possessing the same Code.
Mentions: It appears that there is more than one parity node in a graph. The structure and function of these nodes are similar, and the topological network characteristics of these nodes are completely the same. According to the features of the parity nodes, exchanging two nodes doesn’t affect the topological structure of the whole network. This means that the corresponding associated matrices are similar after exchanging the parity nodes, as can be seen in Figure 4.Figure 4

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.


Related in: MedlinePlus