| − | In 2010, Pedro Ribeiro and Fernando Silva proposed a novel data structure for storing a collection of sub-graphs, called a ''g-trie''.<ref name="rib1">{{cite conference|vauthors=Ribeiro P, Silva F |title=G-Tries: an efficient data structure for discovering network motifs |conference=ACM 25th Symposium On Applied Computing - Bioinformatics Track |location=Sierre, Switzerland |year=2010 |pages=1559–1566 |url=http://www.nrcbioinformatics.ca/acmsac2010/}}</ref> This data structure, which is conceptually akin to a prefix tree, stores sub-graphs according to their structures and finds occurrences of each of these sub-graphs in a larger graph. One of the noticeable aspects of this data structure is that coming to the network motif discovery, the sub-graphs in the main network are needed to be evaluated. So, there is no need to find the ones in random network which are not in the main network. This can be one of the time-consuming parts in the algorithms in which all sub-graphs in random networks are derived.
| + | 2010年， Pedro Ribeiro 和 Fernando Silva 提出了一个叫做''g-trie''的新数据结构，用来存储一组子图。<ref name="rib1">{{cite conference|vauthors=Ribeiro P, Silva F |title=G-Tries: an efficient data structure for discovering network motifs |conference=ACM 25th Symposium On Applied Computing - Bioinformatics Track |location=Sierre, Switzerland |year=2010 |pages=1559–1566 |url=http://www.nrcbioinformatics.ca/acmsac2010/}}</ref>这个在概念上类似前缀树的数据结构，根据子图结构来进行存储，并找出了每个子图在一个更大的图中出现的次数。这个数据结构有一个突出的方面：在应用于模体发现算法时，主网络中的子图需要求解 evaluated。因此，在随机网络中寻找那些在不在主网络中的子图，这个消耗时间的步骤就不再需要执行了。 |
| − | A ''g-trie'' is a multiway tree that can store a collection of graphs. Each tree node contains information about a single graph vertex and its corresponding edges to ancestor nodes. A path from the root to a leaf corresponds to one single graph. Descendants of a g-trie node share a common sub-graph. Constructing a ''g-trie'' is well described in.<ref name="rib1" /> After constructing a ''g-trie'', the counting part takes place. The main idea in counting process is to backtrack by all possible sub-graphs, but at the same time do the isomorphism tests. This backtracking technique is essentially the same technique employed by other motif-centric approaches like ''MODA'' and ''GK'' algorithms. Taking advantage of common substructures in the sense that at a given time there is a partial isomorphic match for several different candidate sub-graphs.
| + | ''g-trie'' 是一个存储一组图的多叉树。每一个树节点都存储着一个'''图节点'''及其'''对应的到前一个节点的边'''的信息。从根节点到叶节点的一条路径对应一个图。<一个 g-trie 节点的子孙节点共享一个子图。如何构造一个 ''g-trie'' 在<ref name="rib1" />中有详细描述。构造好一个 ''g-trie'' 以后，需要进行计数步骤。计数流程的主要思想是回溯所有可能的子图，同时进行同构性测试。这种回溯技术本质上和其他以模体为中心的方法，比如''MODA'' 和 ''GK'' 算法中使用的技术是一样的。这种技术利用了共同的子结构，亦即在一定时间内，几个不同的候选子图中存在部分是同构的。 |
| − | Among the mentioned algorithms, ''G-Tries'' is the fastest. But, the excessive use of memory is the drawback of this algorithm, which might limit the size of discoverable motifs by a personal computer with average memory.
| + | 在上述算法中，''G-Tries'' 是最快的。然而，它的一个缺点是内存的超量使用，这局限了它在个人电脑运行时所能发现的模体的大小 |