7,129
个编辑
更改
→模体发现算法
===G-Tries===
===G-Tries===
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>这个在概念上类似前缀树的数据结构，根据子图结构来进行存储，并找出了每个子图在一个更大的图中出现的次数。这个数据结构有一个突出的方面：在应用于模体发现算法时，主网络中的子图需要进行评估。因此，在随机网络中寻找那些在不在主网络中的子图，这个消耗时间的步骤就不再需要执行了。
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>这个在概念上类似前缀树的数据结构，根据子图结构来进行存储，并找出了每个子图在一个更大的图中出现的次数。这个数据结构有一个突出的方面：在应用于模体发现算法时，主网络中的子图需要进行评估。因此，在随机网络中寻找那些在不在主网络中的子图，这个消耗时间的步骤就不再需要执行了。
g-trie是一个存储一组图的多叉树。每一个树节点都存储着一个图节点及其对应的到前一个节点的边的信息。从根节点到叶节点的一条路径对应一个图。一个g-trie节点的子孙节点共享一个子图（即每一次路径的分叉意味着从一个子图结构中扩展出不同的图结构，而这些扩展出来的图结构自然有着相同的子图结构）。如何构造一个g-trie在<ref name="rib1" />中有详细描述。构造好一个g-trie以后，需要进行计数步骤。计数流程的主要思想是回溯所有可能的子图，同时进行同构性测试。这种回溯技术本质上和其他以模体为中心的方法，比如 MODA 和 GK 算法中使用的技术是一样的。这种技术利用了共同的子结构，亦即在一定时间内，几个不同的候选子图中存在部分是同构的。
在上述算法中，G-Tries是最快的。然而，它的一个缺点是内存的超量使用，这局限了它在个人电脑运行时所能发现的模体的大小
===对比===
===对比===
下面的表格和数据显示了在各种标准网络中运行上述算法所获得的结果。这些结果皆获取于各自相应的来源<ref name="omi1" /><ref name="kash1" /><ref name="rib1" /> ，因此需要独立地对待它们。
下面的表格和数据显示了在各种标准网络中运行上述算法所获得的结果。这些结果皆获取于各自相应的来源<ref name="omi1" /><ref name="kash1" /><ref name="rib1" /> ，因此需要独立地对待它们。
[[Image:Runtimes of algorithms.jpg|thumb|''Runtimes of Grochow–Kellis, mfinder, FANMOD, FPF and MODA for subgraphs from three nodes up to nine nodes''.<ref name="omi1" />]]
[[Image:Runtimes of algorithms.jpg|thumb|Grochow–Kellis，mfinder，FANMOD，FPF和MODA的运行时间适用于从三个节点到多达九个节点的子图。<ref name="omi1" />]]
{|class="wikitable"
{|class="wikitable" style="width: 75%;margin:0 auto"
|+ Grochow–Kellis, FANMOD, 和 G-Trie 在5个不同网络上生成含3到9个节点子图所用的运行时间 <ref name="rib1" />
|+ Grochow–Kellis, FANMOD, 和 G-Trie 在5个不同网络上生成含3到9个节点子图所用的运行时间 <ref name="rib1" />
|-
|-
|}
|}
{|class="wikitable"
{|class="wikitable" style="width: 75%;margin:0 auto"
|+ mfinder, FANMOD, Mavisto 和 Kavosh 在3个不同网络上生成含3到10个节点子图所用的运行时间<ref name="kash1" />
|+ mfinder, FANMOD, Mavisto 和 Kavosh 在3个不同网络上生成含3到10个节点子图所用的运行时间<ref name="kash1" />
|-
|-
===算法的分类===
===算法的分类===
正如表格所示，模体发现算法可以分为两大类：基于精确计数的算法，以及使用统计采样以及估计的算法。因为后者并不计数所有子图在主网络中出现的次数，所以第二类算法会更快，却也可能产生带有偏向性的，甚至不现实的结果。
正如表格所示，模体发现算法可以分为两大类：基于精确计数的算法，以及使用统计采样以及估计的算法。因为后者并不计数所有子图在主网络中出现的次数，所以第二类算法会更快，却也可能产生带有偏向性的，甚至不现实的结果。
更深一层地，基于精确计数的算法可以分为'''以网络为中心'''的方法以及以'''子图为中心'''的方法。前者在给定网络中搜索给定大小的子图，而后者首先根据给定大小生成各种可能的非同构图，然后在网络中分别搜索这些生成的图。这两种方法都有各自的优缺点，这些在上文有讨论。
更深一层地，基于精确计数的算法可以分为'''以网络为中心'''的方法以及以'''子图为中心'''的方法。前者在给定网络中搜索给定大小的子图，而后者首先根据给定大小生成各种可能的非同构图，然后在网络中分别搜索这些生成的图。这两种方法都有各自的优缺点，这些在上文有讨论。
另一方面，基于估计的方法可能会利用如前面描述过的颜色编码手段，其它的手段则通常会在枚举过程中忽略一些子图(比如，像在 FANMOD 中做的那样)，然后只在枚举出来的子图上做估计。
另一方面，基于估计的方法可能会利用如前面描述过的颜色编码手段，其它的手段则通常会在枚举过程中忽略一些子图(比如，像在 FANMOD 中做的那样)，然后只在枚举出来的子图上做估计。
此外，表格还指出了一个算法能否应用于有向网络或无向网络，以及导出子图或非导出子图。更多信息请参考下方提供的网页和实验室地址及联系方式。
此外，表格还指出了一个算法能否应用于有向网络或无向网络，以及导出子图或非导出子图。更多信息请参考下方提供的网页和实验室地址及联系方式。
|}
|}
{|class="wikitable"
{|class="wikitable" style="width: 75%;margin:0 auto"
|+ 算法提出者的地址和联系方式
|+ 算法提出者的地址和联系方式
|-
|-