Limits...
A new method for motif mining in biological networks.

Xu Y, Zhang Q, Zhou C - Evol. Bioinform. Online (2014)

Bottom Line: First, all sub-graphs can be enumerated by adding edges and nodes progressively, using the backtracking method based on the associated matrix.Taking advantage of the combination of the associated matrix and the backtracking method, our method reduces the complexity of enumerating sub-graphs, providing a more efficient solution for motif mining.From the results obtained, our method has shown higher speed and more extensive applicability than other similar methods.

View Article: PubMed Central - PubMed

Affiliation: Key Laboratory of Advanced Design and Intelligent Computing, Dalian University, Ministry of Education, Dalian, China.

ABSTRACT
Network motifs are overly represented as topological patterns that occur more often in a given network than in random networks, and take on some certain functions in practical biological applications. Existing methods of detecting network motifs have focused on computational efficiency. However, detecting network motifs also presents huge challenges in computational and spatial complexity. In this paper, we provide a new approach for mining network motifs. First, all sub-graphs can be enumerated by adding edges and nodes progressively, using the backtracking method based on the associated matrix. Then, the associated matrix is standardized and the isomorphism sub-graphs are marked uniquely in combination with symmetric ternary, which can simulate the elements (-1,0,1) in the associated matrix. Taking advantage of the combination of the associated matrix and the backtracking method, our method reduces the complexity of enumerating sub-graphs, providing a more efficient solution for motif mining. From the results obtained, our method has shown higher speed and more extensive applicability than other similar methods.

No MeSH data available.


Flow chart of mining motifs.
© Copyright Policy - open-access
Related In: Results  -  Collection


getmorefigures.php?uid=PMC4196890&req=5

f2-ebo-10-2014-155: Flow chart of mining motifs.

Mentions: There are five subtasks in our method: form of storage – a way to store digraph and undirected graph; backtracking – enumerating all sub-graphs of a given size that occur in the input graph; random graph generation – generating random graphs that meet the requirement of the input network; sub-graph isomorphic – standardizing the associated matrix, which marks the graph uniquely; and motif identification – distinguishing motifs among all founded sub-graphs on the basis of statistical parameters (Fig. 2).


A new method for motif mining in biological networks.

Xu Y, Zhang Q, Zhou C - Evol. Bioinform. Online (2014)

Flow chart of mining motifs.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f2-ebo-10-2014-155: Flow chart of mining motifs.
Mentions: There are five subtasks in our method: form of storage – a way to store digraph and undirected graph; backtracking – enumerating all sub-graphs of a given size that occur in the input graph; random graph generation – generating random graphs that meet the requirement of the input network; sub-graph isomorphic – standardizing the associated matrix, which marks the graph uniquely; and motif identification – distinguishing motifs among all founded sub-graphs on the basis of statistical parameters (Fig. 2).

Bottom Line: First, all sub-graphs can be enumerated by adding edges and nodes progressively, using the backtracking method based on the associated matrix.Taking advantage of the combination of the associated matrix and the backtracking method, our method reduces the complexity of enumerating sub-graphs, providing a more efficient solution for motif mining.From the results obtained, our method has shown higher speed and more extensive applicability than other similar methods.

View Article: PubMed Central - PubMed

Affiliation: Key Laboratory of Advanced Design and Intelligent Computing, Dalian University, Ministry of Education, Dalian, China.

ABSTRACT
Network motifs are overly represented as topological patterns that occur more often in a given network than in random networks, and take on some certain functions in practical biological applications. Existing methods of detecting network motifs have focused on computational efficiency. However, detecting network motifs also presents huge challenges in computational and spatial complexity. In this paper, we provide a new approach for mining network motifs. First, all sub-graphs can be enumerated by adding edges and nodes progressively, using the backtracking method based on the associated matrix. Then, the associated matrix is standardized and the isomorphism sub-graphs are marked uniquely in combination with symmetric ternary, which can simulate the elements (-1,0,1) in the associated matrix. Taking advantage of the combination of the associated matrix and the backtracking method, our method reduces the complexity of enumerating sub-graphs, providing a more efficient solution for motif mining. From the results obtained, our method has shown higher speed and more extensive applicability than other similar methods.

No MeSH data available.