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.


An example of an associate matrix, showing the corresponding relationship between a graph and a form of storage.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig3: An example of an associate matrix, showing the corresponding relationship between a graph and a form of storage.

Mentions: An associated matrix M(G) shows the connection between the nodes and edges of G. It is usually not a square matrix, shown as Figure 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ M(G)=\begin{array}{lllll}\hfill & {e}_1\hfill & {e}_2\hfill & {e}_3\hfill & {e}_4\hfill \\ {}{v}_1\hfill & 1\hfill & 1\hfill & 0\hfill & 1\hfill \\ {}{\mathrm{V}}_2\hfill & -1\hfill & 0\hfill & 0\hfill & 0\hfill \\ {}{v}_3\hfill & 0\hfill & -1\hfill & 1\hfill & 1\hfill \\ {}{v}_4\hfill & 0\hfill & 0\hfill & -1\hfill & -1\hfill \end{array} $$\end{document}MG=e1e2e3e4v11101V2−1000v30−111v400−1−1Figure 3


Motif mining based on network space compression.

Zhang Q, Xu Y - BioData Min (2014)

An example of an associate matrix, showing the corresponding relationship between a graph and a form of storage.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig3: An example of an associate matrix, showing the corresponding relationship between a graph and a form of storage.
Mentions: An associated matrix M(G) shows the connection between the nodes and edges of G. It is usually not a square matrix, shown as Figure 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ M(G)=\begin{array}{lllll}\hfill & {e}_1\hfill & {e}_2\hfill & {e}_3\hfill & {e}_4\hfill \\ {}{v}_1\hfill & 1\hfill & 1\hfill & 0\hfill & 1\hfill \\ {}{\mathrm{V}}_2\hfill & -1\hfill & 0\hfill & 0\hfill & 0\hfill \\ {}{v}_3\hfill & 0\hfill & -1\hfill & 1\hfill & 1\hfill \\ {}{v}_4\hfill & 0\hfill & 0\hfill & -1\hfill & -1\hfill \end{array} $$\end{document}MG=e1e2e3e4v11101V2−1000v30−111v400−1−1Figure 3

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.