| 第209行： |
第209行： |
| | '''返回''' | | '''返回''' |
| | |} | | |} |
| − |
| |
| − | ===NeMoFinder===
| |
| − | Chen ''et al.'' <ref name="che1">{{cite conference |vauthors=Chen J, Hsu W, Li Lee M, etal |title=NeMoFinder: dissecting genome-wide protein-protein interactions with meso-scale network motifs |conference=the 12th ACM SIGKDD international conference on Knowledge discovery and data mining |year=2006 |location=Philadelphia, Pennsylvania, USA |pages=106–115}}</ref> introduced a new NM discovery algorithm called ''NeMoFinder'', which adapts the idea in ''SPIN'' <ref name="hua1">{{cite conference |vauthors=Huan J, Wang W, Prins J, etal |title=SPIN: mining maximal frequent sub-graphs from graph databases |conference=the 10th ACM SIGKDD international conference on Knowledge discovery and data mining |year=2004 |pages=581–586}}</ref> to extract frequent trees and after that expands them into non-isomorphic graphs.<ref name="cir1" /> ''NeMoFinder'' utilizes frequent size-n trees to partition the input network into a collection of size-{{math|n}} graphs, afterward finding frequent size-n sub-graphs by expansion of frequent trees edge-by-edge until getting a complete size-{{math|n}} graph {{math|K<sub>n</sub>}}. The algorithm finds NMs in undirected networks and is not limited to extracting only induced sub-graphs. Furthermore, ''NeMoFinder'' is an exact enumeration algorithm and is not based on a sampling method. As Chen ''et al.'' claim, ''NeMoFinder'' is applicable for detecting relatively large NMs, for instance, finding NMs up to size-12 from the whole ''S. cerevisiae'' (yeast) PPI network as the authors claimed.<ref name="uet1">{{cite journal |vauthors=Uetz P, Giot L, Cagney G, etal |title=A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae |journal=Nature |year=2000 |volume=403 |issue=6770 |pages=623–627 |doi=10.1038/35001009 |pmid=10688190|bibcode=2000Natur.403..623U }}</ref>
| |
| − |
| |
| − | ''NeMoFinder'' consists of three main steps. First, finding frequent size-{{math|n}} trees, then utilizing repeated size-n trees to divide the entire network into a collection of size-{{math|n}} graphs, finally, performing sub-graph join operations to find frequent size-n sub-graphs.<ref name="che1" /> In the first step, the algorithm detects all non-isomorphic size-{{math|n}} trees and mappings from a tree to the network. In the second step, the ranges of these mappings are employed to partition the network into size-n graphs. Up to this step, there is no distinction between ''NeMoFinder'' and an exact enumeration method. However, a large portion of non-isomorphic size-n graphs still remain. ''NeMoFinder'' exploits a heuristic to enumerate non-tree size-n graphs by the obtained information from the preceding steps. The main advantage of the algorithm is in the third step, which generates candidate sub-graphs from previously enumerated sub-graphs. This generation of new size-{{math|n}} sub-graphs is done by joining each previous sub-graph with derivative sub-graphs from itself called ''cousin sub-graphs''. These new sub-graphs contain one additional edge in comparison to the previous sub-graphs. However, there exist some problems in generating new sub-graphs: There is no clear method to derive cousins from a graph, joining a sub-graph with its cousins leads to redundancy in generating particular sub-graph more than once, and cousin determination is done by a canonical representation of the adjacency matrix which is not closed under join operation. ''NeMoFinder'' is an efficient network motif finding algorithm for motifs up to size 12 only for protein-protein interaction networks, which are presented as undirected graphs. And it is not able to work on directed networks which are so important in the field of complex and biological networks. The pseudocode of ''NeMoFinder'' is shown below:
| |
| − |
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | ! NeMoFinder
| |
| − | |-
| |
| − | |'''Input:'''
| |
| − |
| |
| − | {{math|G}} - PPI network;
| |
| − |
| |
| − | {{math|N}} - Number of randomized networks;
| |
| − |
| |
| − | {{math|K}} - Maximal network motif size;
| |
| − |
| |
| − | {{math|F}} - Frequency threshold;
| |
| − |
| |
| − | {{math|S}} - Uniqueness threshold;
| |
| − |
| |
| − | '''Output:'''
| |
| − |
| |
| − | {{math|U}} - Repeated and unique network motif set;
| |
| − |
| |
| − | {{math|D ← ∅}};
| |
| − |
| |
| − | '''for''' motif-size {{math|k}} '''from''' 3 '''to''' {{math|K}} '''do'''
| |
| − |
| |
| − | {{pad|1em}}{{math|T ← ''FindRepeatedTrees''(k)}};
| |
| − |
| |
| − | {{pad|1em}}{{math|GD<sub>k</sub> ← ''GraphPartition''(G, T)}}
| |
| − |
| |
| − | {{pad|1em}}{{math|D ← D ∪ T}};
| |
| − |
| |
| − | {{pad|1em}}{{math|D′ ← T}};
| |
| − |
| |
| − | {{pad|1em}}{{math|i ← k}};
| |
| − |
| |
| − | {{pad|1em}}'''while''' {{math|D′ ≠ ∅}} '''and''' {{math|i ≤ k × (k - 1) / 2}} '''do'''
| |
| − |
| |
| − | {{pad|2em}}{{math|D′ ← ''FindRepeatedGraphs''(k, i, D′)}};
| |
| − |
| |
| − | {{pad|2em}}{{math|D ← D ∪ D′}};
| |
| − |
| |
| − | {{pad|2em}}{{math|i ← i + 1}};
| |
| − |
| |
| − | {{pad|1em}}'''end while'''
| |
| − |
| |
| − | '''end for'''
| |
| − |
| |
| − | '''for''' counter {{math|i}} '''from''' 1 '''to''' {{math|N}} '''do'''
| |
| − |
| |
| − | {{pad|1em}}{{math|G<sub>rand</sub> ← ''RandomizedNetworkGeneration''()}};
| |
| − |
| |
| − | {{pad|1em}}'''for each''' {{math|g ∈ D}} '''do'''
| |
| − |
| |
| − | {{pad|2em}}{{math|''GetRandFrequency''(g, G<sub>rand</sub>)}};
| |
| − |
| |
| − | {{pad|1em}}'''end for'''
| |
| − |
| |
| − | '''end for'''
| |
| − |
| |
| − | {{math|U ← ∅}};
| |
| − |
| |
| − | '''for each''' {{math|g ∈ D}} '''do'''
| |
| − |
| |
| − | {{pad|1em}}{{math|s ← ''GetUniqunessValue''(g)}};
| |
| − |
| |
| − | {{pad|1em}}'''if''' {{math|s ≥ S}} '''then'''
| |
| − |
| |
| − | {{pad|2em}}{{math|U ← U ∪ {g}}};
| |
| − |
| |
| − | {{pad|1em}}'''end if'''
| |
| − |
| |
| − | '''end for'''
| |
| − |
| |
| − | '''return''' {{math|U}};
| |
| − | |}
| |
| − |
| |
| − | ===Grochow–Kellis===
| |
| − | Grochow and Kellis <ref name="gro1">{{cite conference|vauthors=Grochow JA, Kellis M |title=Network Motif Discovery Using Sub-graph Enumeration and Symmetry-Breaking |conference=RECOMB |year=2007 |pages=92–106| doi=10.1007/978-3-540-71681-5_7| url=http://www.cs.colorado.edu/~jgrochow/Grochow_Kellis_RECOMB_07_Network_Motifs.pdf}}</ref> proposed an ''exact'' algorithm for enumerating sub-graph appearances. The algorithm is based on a ''motif-centric'' approach, which means that the frequency of a given sub-graph,called the ''query graph'', is exhaustively determined by searching for all possible mappings from the query graph into the larger network. It is claimed <ref name="gro1" /> that a ''motif-centric'' method in comparison to ''network-centric'' methods has some beneficial features. First of all it avoids the increased complexity of sub-graph enumeration. Also, by using mapping instead of enumerating, it enables an improvement in the isomorphism test. To improve the performance of the algorithm, since it is an inefficient exact enumeration algorithm, the authors introduced a fast method which is called ''symmetry-breaking conditions''. During straightforward sub-graph isomorphism tests, a sub-graph may be mapped to the same sub-graph of the query graph multiple times. In the Grochow–Kellis (GK) algorithm symmetry-breaking is used to avoid such multiple mappings. Here we introduce the GK algorithm and the symmetry-breaking condition which eliminates redundant isomorphism tests.
| |
| − |
| |
| − | [[File:Automorphisms of a subgraph.jpg|thumb|(a) ''graph G'', (b) ''illustration of all automorphisms of G that is showed in (a)''. From set AutG we can obtain a set of symmetry-breaking conditions of G given by SymG in (c). Only the first mapping in AutG satisfies the SynG conditions; as a result, by applying SymG in the Isomorphism Extension module the algorithm only enumerate each match-able sub-graph in the network to G once. Note that SynG is not necessarily a unique set for an arbitrary graph G.]]
| |
| − |
| |
| − | The GK algorithm discovers the whole set of mappings of a given query graph to the network in two major steps. It starts with the computation of symmetry-breaking conditions of the query graph. Next, by means of a branch-and-bound method, the algorithm tries to find every possible mapping from the query graph to the network that meets the associated symmetry-breaking conditions. An example of the usage of symmetry-breaking conditions in GK algorithm is demonstrated in figure.
| |
| − |
| |
| − | As it is mentioned above, the symmetry-breaking technique is a simple mechanism that precludes spending time finding a sub-graph more than once due to its symmetries.<ref name="gro1" /><ref name="gro2">{{cite conference|author=Grochow JA |title=On the structure and evolution of protein interaction networks |conference=Thesis M. Eng., Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science|year=2006| url=http://www.cs.toronto.edu/~jgrochow/Grochow_MIT_Masters_06_PPI_Networks.pdf}}</ref> Note that, computing symmetry-breaking conditions requires finding all automorphisms of a given query graph. Even though, there is no efficient (or polynomial time) algorithm for the graph automorphism problem, this problem can be tackled efficiently in practice by McKay's tools.<ref name="mck1" /><ref name="mck2" /> As it is claimed, using symmetry-breaking conditions in NM detection lead to save a great deal of running time. Moreover, it can be inferred from the results in <ref name="gro1" /><ref name="gro2" /> that using the symmetry-breaking conditions results in high efficiency particularly for directed networks in comparison to undirected networks. The symmetry-breaking conditions used in the GK algorithm are similar to the restriction which ''ESU'' algorithm applies to the labels in EXT and SUB sets. In conclusion, the GK algorithm computes the exact number of appearance of a given query graph in a large complex network and exploiting symmetry-breaking conditions improves the algorithm performance. Also, GK algorithm is one of the known algorithms having no limitation for motif size in implementation and potentially it can find motifs of any size.
| |
| − |
| |
| − |
| |
| − | ===Color-coding approach===
| |
| − | Most algorithms in the field of NM discovery are used to find induced sub-graphs of a network. In 2008, Noga Alon ''et al.'' <ref name="alo1">{{cite journal|author1=Alon N |author2=Dao P |author3=Hajirasouliha I |author4=Hormozdiari F |author5=Sahinalp S.C |title=Biomolecular network motif counting and discovery by color coding |journal=Bioinformatics |year=2008 |volume=24 |issue=13 |pages=i241–i249 |doi=10.1093/bioinformatics/btn163|pmid=18586721 |pmc=2718641 }}</ref> introduced an approach for finding non-induced sub-graphs too. Their technique works on undirected networks such as PPI ones. Also, it counts non-induced trees and bounded treewidth sub-graphs. This method is applied for sub-graphs of size up to 10.
| |
| − |
| |
| − | This algorithm counts the number of non-induced occurrences of a tree {{math|T}} with {{math|k {{=}} O(logn)}} vertices in a network {{math|G}} with {{math|n}} vertices as follows:
| |
| − |
| |
| − | # '''Color coding.''' Color each vertex of input network G independently and uniformly at random with one of the {{math|k}} colors.
| |
| − | # '''Counting.''' Apply a dynamic programming routine to count the number of non-induced occurrences of {{math|T}} in which each vertex has a unique color. For more details on this step, see.<ref name="alo1" />
| |
| − | # Repeat the above two steps {{math|O(e<sup>k</sup>)}} times and add up the number of occurrences of {{math|T}} to get an estimate on the number of its occurrences in {{math|G}}.
| |
| − |
| |
| − | As available PPI networks are far from complete and error free, this approach is suitable for NM discovery for such networks. As Grochow–Kellis Algorithm and this one are the ones popular for non-induced sub-graphs, it is worth to mention that the algorithm introduced by Alon ''et al.'' is less time-consuming than the Grochow–Kellis Algorithm.<ref name="alo1" />
| |
| − |
| |
| − |
| |
| − | ===MODA===
| |
| − | Omidi ''et al.'' <ref name="omi1">{{cite journal|vauthors=Omidi S, Schreiber F, Masoudi-Nejad A |title=MODA: an efficient algorithm for network motif discovery in biological networks |journal=Genes Genet Syst |year=2009 |volume=84 |issue=5 |pages=385–395 |doi=10.1266/ggs.84.385|pmid=20154426 |doi-access=free }}</ref> introduced a new algorithm for motif detection named ''MODA'' which is applicable for induced and non-induced NM discovery in undirected networks. It is based on the motif-centric approach discussed in the Grochow–Kellis algorithm section. It is very important to distinguish motif-centric algorithms such as MODA and GK algorithm because of their ability to work as query-finding algorithms. This feature allows such algorithms to be able to find a single motif query or a small number of motif queries (not all possible sub-graphs of a given size) with larger sizes. As the number of possible non-isomorphic sub-graphs increases exponentially with sub-graph size, for large size motifs (even larger than 10), the network-centric algorithms, those looking for all possible sub-graphs, face a problem. Although motif-centric algorithms also have problems in discovering all possible large size sub-graphs, but their ability to find small numbers of them is sometimes a significant property.
| |
| − |
| |
| − | Using a hierarchical structure called an ''expansion tree'', the ''MODA'' algorithm is able to extract NMs of a given size systematically and similar to ''FPF'' that avoids enumerating unpromising sub-graphs; ''MODA'' takes into consideration potential queries (or candidate sub-graphs) that would result in frequent sub-graphs. Despite the fact that ''MODA'' resembles ''FPF'' in using a tree like structure, the expansion tree is applicable merely for computing frequency concept {{math|F<sub>1</sub>}}. As we will discuss next, the advantage of this algorithm is that it does not carry out the sub-graph isomorphism test for ''non-tree'' query graphs. Additionally, it utilizes a sampling method in order to speed up the running time of the algorithm.
| |
| − |
| |
| − | Here is the main idea: by a simple criterion one can generalize a mapping of a k-size graph into the network to its same size supergraphs. For example, suppose there is mapping {{math|f(G)}} of graph {{math|G}} with {{math|k}} nodes into the network and we have a same size graph {{math|G′}} with one more edge {{math|&langu, v⟩}}; {{math|f<sub>G</sub>}} will map {{math|G′}} into the network, if there is an edge {{math|⟨f<sub>G</sub>(u), f<sub>G</sub>(v)⟩}} in the network. As a result, we can exploit the mapping set of a graph to determine the frequencies of its same order supergraphs simply in {{math|O(1)}} time without carrying out sub-graph isomorphism testing. The algorithm starts ingeniously with minimally connected query graphs of size k and finds their mappings in the network via sub-graph isomorphism. After that, with conservation of the graph size, it expands previously considered query graphs edge-by-edge and computes the frequency of these expanded graphs as mentioned above. The expansion process continues until reaching a complete graph {{math|K<sub>k</sub>}} (fully connected with {{math|{{frac|k(k-1)|2}}}} edge).
| |
| − |
| |
| − | As discussed above, the algorithm starts by computing sub-tree frequencies in the network and then expands sub-trees edge by edge. One way to implement this idea is called the expansion tree {{math|T<sub>k</sub>}} for each {{math|k}}. Figure shows the expansion tree for size-4 sub-graphs. {{math|T<sub>k</sub>}} organizes the running process and provides query graphs in a hierarchical manner. Strictly speaking, the expansion tree {{math|T<sub>k</sub>}} is simply a [[directed acyclic graph]] or DAG, with its root number {{math|k}} indicating the graph size existing in the expansion tree and each of its other nodes containing the adjacency matrix of a distinct {{math|k}}-size query graph. Nodes in the first level of {{math|T<sub>k</sub>}} are all distinct {{math|k}}-size trees and by traversing {{math|T<sub>k</sub>}} in depth query graphs expand with one edge at each level. A query graph in a node is a sub-graph of the query graph in a node's child with one edge difference. The longest path in {{math|T<sub>k</sub>}} consists of {{math|(k<sup>2</sup>-3k+4)/2}} edges and is the path from the root to the leaf node holding the complete graph. Generating expansion trees can be done by a simple routine which is explained in.<ref name="omi1" />
| |
| − |
| |
| − | ''MODA'' traverses {{math|T<sub>k</sub>}} and when it extracts query trees from the first level of {{math|T<sub>k</sub>}} it computes their mapping sets and saves these mappings for the next step. For non-tree queries from {{math|T<sub>k</sub>}}, the algorithm extracts the mappings associated with the parent node in {{math|T<sub>k</sub>}} and determines which of these mappings can support the current query graphs. The process will continue until the algorithm gets the complete query graph. The query tree mappings are extracted using the Grochow–Kellis algorithm. For computing the frequency of non-tree query graphs, the algorithm employs a simple routine that takes {{math|O(1)}} steps. In addition, ''MODA'' exploits a sampling method where the sampling of each node in the network is linearly proportional to the node degree, the probability distribution is exactly similar to the well-known Barabási-Albert preferential attachment model in the field of complex networks.<ref name="bar1">{{cite journal|vauthors=Barabasi AL, Albert R |title=Emergence of scaling in random networks |journal=Science |year=1999 |volume=286 |issue=5439 |pages=509–512 |doi=10.1126/science.286.5439.509 |pmid=10521342|bibcode=1999Sci...286..509B |arxiv=cond-mat/9910332 }}</ref> This approach generates approximations; however, the results are almost stable in different executions since sub-graphs aggregate around highly connected nodes.<ref name="vaz1">{{cite journal |vauthors=Vázquez A, Dobrin R, Sergi D, etal |title=The topological relationship between the large-scale attributes and local interaction patterns of complex networks |journal=PNAS |year=2004 |volume=101 |issue=52 |pages=17940–17945 |doi=10.1073/pnas.0406024101|pmid=15598746 |pmc=539752 |bibcode=2004PNAS..10117940V |arxiv=cond-mat/0408431 }}</ref> The pseudocode of ''MODA'' is shown below:
| |
| − |
| |
| − | [[File:Expansion Tree.jpg|thumb|''Illustration of the expansion tree T4 for 4-node query graphs''. At the first level, there are non-isomorphic k-size trees and at each level, an edge is added to the parent graph to form a child graph. In the second level, there is a graph with two alternative edges that is shown by a dashed red edge. In fact, this node represents two expanded graphs that are isomorphic.<ref name="omi1" />]]
| |
| − |
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | ! MODA
| |
| − | |-
| |
| − | |'''Input:''' {{math|G}}: Input graph, {{math|k}}: sub-graph size, {{math|Δ}}: threshold value
| |
| − |
| |
| − | '''Output:''' Frequent Subgraph List: List of all frequent {{math|k}}-size sub-graphs
| |
| − |
| |
| − | '''Note:''' {{math|F<sub>G</sub>}}: set of mappings from {{math|G}} in the input graph {{math|G}}
| |
| − |
| |
| − | '''fetch''' {{math|T<sub>k</sub>}}
| |
| − |
| |
| − | '''do'''
| |
| − |
| |
| − | {{pad|1em}}{{math|G′ {{=}} ''Get-Next-BFS''(T<sub>k</sub>)}} // {{math|G′}} is a query graph
| |
| − |
| |
| − | {{pad|1em}}if {{math|{{!}}E(G′){{!}} {{=}} (k – 1)}}
| |
| − |
| |
| − | {{pad|1em}}'''call''' {{math|''Mapping-Module''(G′, G)}}
| |
| − |
| |
| − | {{pad|1em}}'''else'''
| |
| − |
| |
| − | {{pad|2em}}'''call''' {{math|''Enumerating-Module''(G′, G, T<sub>k</sub>)}}
| |
| − |
| |
| − | {{pad|1em}}'''end if'''
| |
| − |
| |
| − | {{pad|1em}}'''save''' {{math|F<sub>2</sub>}}
| |
| − |
| |
| − | {{pad|1em}}'''if''' {{math|{{!}}F<sub>G</sub>{{!}} > Δ}} '''then'''
| |
| − |
| |
| − | {{pad|2em}}add {{math|G′}} into Frequent Subgraph List
| |
| − |
| |
| − | {{pad|1em}}'''end if'''
| |
| − |
| |
| − | '''Until''' {{math|{{!}}E(G'){{!}} {{=}} (k – 1)/2}}
| |
| − |
| |
| − | '''return''' Frequent Subgraph List
| |
| − | |}
| |
| − |
| |
| − |
| |
| − | ===Kavosh===
| |
| − | A recently introduced algorithm named ''Kavosh'' <ref name="kash1">{{cite journal|vauthors=Kashani ZR, Ahrabian H, Elahi E, Nowzari-Dalini A, Ansari ES, Asadi S, Mohammadi S, Schreiber F, Masoudi-Nejad A |title=Kavosh: a new algorithm for finding network motifs |journal=BMC Bioinformatics |year=2009 |volume=10 |issue=318|pages=318 |doi=10.1186/1471-2105-10-318 |pmid=19799800 |pmc=2765973}} {{open access}}</ref> aims at improved main memory usage. ''Kavosh'' is usable to detect NM in both directed and undirected networks. The main idea of the enumeration is similar to the ''GK'' and ''MODA'' algorithms, which first find all {{math|k}}-size sub-graphs that a particular node participated in, then remove the node, and subsequently repeat this process for the remaining nodes.<ref name="kash1" />
| |
| − |
| |
| − | For counting the sub-graphs of size {{math|k}} that include a particular node, trees with maximum depth of k, rooted at this node and based on neighborhood relationship are implicitly built. Children of each node include both incoming and outgoing adjacent nodes. To descend the tree, a child is chosen at each level with the restriction that a particular child can be included only if it has not been included at any upper level. After having descended to the lowest level possible, the tree is again ascended and the process is repeated with the stipulation that nodes visited in earlier paths of a descendant are now considered unvisited nodes. A final restriction in building trees is that all children in a particular tree must have numerical labels larger than the label of the root of the tree. The restrictions on the labels of the children are similar to the conditions which ''GK'' and ''ESU'' algorithm use to avoid overcounting sub-graphs.
| |
| − |
| |
| − | The protocol for extracting sub-graphs makes use of the compositions of an integer. For the extraction of sub-graphs of size {{math|k}}, all possible compositions of the integer {{math|k-1}} must be considered. The compositions of {{math|k-1}} consist of all possible manners of expressing {{math|k-1}} as a sum of positive integers. Summations in which the order of the summands differs are considered distinct. A composition can be expressed as {{math|k<sub>2</sub>,k<sub>3</sub>,…,k<sub>m</sub>}} where {{math|k<sub>2</sub> + k<sub>3</sub> + … + k<sub>m</sub> {{=}} k-1}}. To count sub-graphs based on the composition, {{math|k<sub>i</sub>}} nodes are selected from the {{math|i}}-th level of the tree to be nodes of the sub-graphs ({{math|i {{=}} 2,3,…,m}}). The {{math|k-1}} selected nodes along with the node at the root define a sub-graph within the network. After discovering a sub-graph involved as a match in the target network, in order to be able to evaluate the size of each class according to the target network, ''Kavosh'' employs the ''nauty'' algorithm <ref name="mck1" /><ref name="mck2" /> in the same way as ''FANMOD''. The enumeration part of Kavosh algorithm is shown below:
| |
| − |
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | ! Enumeration of Kavosh
| |
| − | |-
| |
| − | |'''''Enumerate_Vertex(G, u, S, Remainder, i)'''''
| |
| − |
| |
| − | '''Input:''' {{math|G}}: Input graph<br>
| |
| − | {{pad|3em}}{{math|u}}: Root vertex<br>
| |
| − | {{pad|3em}}{{math|S}}: selection ({{math|S {{=}} { S<sub>0</sub>,S<sub>1</sub>,...,S<sub>k-1</sub>}}} is an array of the set of all {{math|S<sub>i</sub>}})<br>
| |
| − | {{pad|3em}}{{math|Remainder}}: number of remaining vertices to be selected<br>
| |
| − | {{pad|3em}}{{math|i}}: Current depth of the tree.<br>
| |
| − | '''Output:''' all {{math|k}}-size sub-graphs of graph {{math|G}} rooted in {{math|u}}.
| |
| − |
| |
| − | '''if''' {{math|Remainder {{=}} 0}} '''then'''<br>
| |
| − | {{pad|1em}}'''return'''<br>
| |
| − | '''else'''<br>
| |
| − | {{pad|1em}}{{math|ValList ← ''Validate''(G, S<sub>i-1</sub>, u)}}<br>
| |
| − | {{pad|1em}}{{math|n<sub>i</sub> ← ''Min''({{!}}ValList{{!}}, Remainder)}}<br>
| |
| − | {{pad|1em}}'''for''' {{math|k<sub>i</sub> {{=}} 1}} '''to''' {{math|n<sub>i</sub>}} '''do'''<br>
| |
| − | {{pad|2em}}{{math|C ← ''Initial_Comb''(ValList, k<sub>i</sub>)}}<br>
| |
| − | {{pad|2em}}(Make the first vertex combination selection according)<br>
| |
| − | {{pad|2em}}'''repeat'''<br>
| |
| − | {{pad|3em}}{{math|S<sub>i</sub> ← C}}<br>
| |
| − | {{pad|3em}}{{math|''Enumerate_Vertex''(G, u, S, Remainder-k<sub>i</sub>, i+1)}}<br>
| |
| − | {{pad|3em}}{{math|''Next_Comb''(ValList, k<sub>i</sub>)}}<br>
| |
| − | {{pad|3em}}(Make the next vertex combination selection according)<br>
| |
| − | {{pad|2em}}'''until''' {{math|C {{=}} NILL}}<br>
| |
| − | {{pad|2em}}'''end for'''<br>
| |
| − | {{pad|1em}}'''for each''' {{math|v ∈ ValList}} '''do'''<br>
| |
| − | {{pad|2em}}{{math|Visited[v] ← false}}<br>
| |
| − | {{pad|1em}}'''end for'''<br>
| |
| − | '''end if'''
| |
| − | |-
| |
| − | |'''''Validate(G, Parents, u)'''''<br>
| |
| − | '''Input:''' {{math|G}}: input graph, {{math|Parents}}: selected vertices of last layer, {{math|u}}: Root vertex.<br>
| |
| − | '''Output:''' Valid vertices of the current level.
| |
| − |
| |
| − | {{math|ValList ← NILL}}<br>
| |
| − | '''for each''' {{math|v ∈ Parents}} '''do'''<br>
| |
| − | {{pad|1em}}'''for each''' {{math|w ∈ Neighbor[u]}} '''do'''<br>
| |
| − | {{pad|2em}}'''if''' {{math|label[u] < label[w]}} '''AND NOT''' {{math|Visited[w]}} '''then'''<br>
| |
| − | {{pad|3em}}{{math|Visited[w] ← true}}<br>
| |
| − | {{pad|3em}}{{math|ValList {{=}} ValList + w}}<br>
| |
| − | {{pad|2em}}'''end if'''<br>
| |
| − | {{pad|1em}}'''end for'''<br>
| |
| − | '''end for'''<br>
| |
| − | '''return''' {{math|ValList}}<br>
| |
| − | |}
| |
| − |
| |
| − | Recently a ''Cytoscape'' plugin called ''CytoKavosh'' <ref name="mas2">{{cite journal|author1=Ali Masoudi-Nejad |author2=Mitra Anasariola |author3=Ali Salehzadeh-Yazdi |author4=Sahand Khakabimamaghani |title=CytoKavosh: a Cytoscape Plug-in for Finding Network Motifs in Large Biological Networks |journal=PLoS ONE |volume=7 |issue=8 |pages=e43287 |year=2012 |doi=10.1371/journal.pone.0043287|pmid=22952659 |pmc=3430699 |bibcode=2012PLoSO...743287M }} {{open access}}</ref> is developed for this software. It is available via ''Cytoscape'' web page [http://apps.cytoscape.org/apps/cytokavosh].
| |
| | | | |
| | | | |