46
个编辑
更改
→ESU (FANMOD)算法及对应的软件
The sampling bias of Kashtan ''et al.'' <ref name="kas1" /> provided great impetus for designing better algorithms for the NM discovery problem. Although Kashtan ''et al.'' tried to settle this drawback by means of a weighting scheme, this method imposed an undesired overhead on the running time as well a more complicated implementation. This tool is one of the most useful ones, as it supports visual options and also is an efficient algorithm with respect to time. But, it has a limitation on motif size as it does not allow searching for motifs of size 9 or higher because of the way the tool is implemented.
The sampling bias of Kashtan ''et al.'' <ref name="kas1" /> provided great impetus for designing better algorithms for the NM discovery problem. Although Kashtan ''et al.'' tried to settle this drawback by means of a weighting scheme, this method imposed an undesired overhead on the running time as well a more complicated implementation. This tool is one of the most useful ones, as it supports visual options and also is an efficient algorithm with respect to time. But, it has a limitation on motif size as it does not allow searching for motifs of size 9 or higher because of the way the tool is implemented.
由于Kashtan等学者发现的采样偏差问题，所以针对NM discovery problem需要设计更好的算法。虽然Kashtan等人尝试用加权法来解决这个弊端，但这个方法在运行上，消耗了过多的运行时间，且实现起来也变得更加复杂。但这个工具还是最好用的工具之一，因为它支持可视化选项，同时也『是个节约时间的算法』。但是，它在所支持的模体的规模大小还是有局限性。由于该工具在具体实施中，不允许搜索规模大小为9或者更大的模体。
Wernicke <ref name="wer1" /> introduced an algorithm named ''RAND-ESU'' that provides a significant improvement over ''mfinder''.<ref name="kas1" /> This algorithm, which is based on the exact enumeration algorithm ''ESU'', has been implemented as an application called ''FANMOD''.<ref name="wer1" /> ''RAND-ESU'' is a NM discovery algorithm applicable for both directed and undirected networks, effectively exploits an unbiased node sampling throughout the network, and prevents overcounting sub-graphs more than once. Furthermore, ''RAND-ESU'' uses a novel analytical approach called ''DIRECT'' for determining sub-graph significance instead of using an ensemble of random networks as a Null-model. The ''DIRECT'' method estimates the sub-graph concentration without explicitly generating random networks.<ref name="wer1" /> Empirically, the DIRECT method is more efficient in comparison with the random network ensemble in case of sub-graphs with a very low concentration; however, the classical Null-model is faster than the ''DIRECT'' method for highly concentrated sub-graphs.<ref name="mil1" /><ref name="wer1" /> In the following, we detail the ''ESU'' algorithm and then we show how this exact algorithm can be modified efficiently to ''RAND-ESU'' that estimates sub-graphs concentrations.
Wernicke <ref name="wer1" /> introduced an algorithm named ''RAND-ESU'' that provides a significant improvement over ''mfinder''.<ref name="kas1" /> This algorithm, which is based on the exact enumeration algorithm ''ESU'', has been implemented as an application called ''FANMOD''.<ref name="wer1" /> ''RAND-ESU'' is a NM discovery algorithm applicable for both directed and undirected networks, effectively exploits an unbiased node sampling throughout the network, and prevents overcounting sub-graphs more than once. Furthermore, ''RAND-ESU'' uses a novel analytical approach called ''DIRECT'' for determining sub-graph significance instead of using an ensemble of random networks as a Null-model. The ''DIRECT'' method estimates the sub-graph concentration without explicitly generating random networks.<ref name="wer1" /> Empirically, the DIRECT method is more efficient in comparison with the random network ensemble in case of sub-graphs with a very low concentration; however, the classical Null-model is faster than the ''DIRECT'' method for highly concentrated sub-graphs.<ref name="mil1" /><ref name="wer1" /> In the following, we detail the ''ESU'' algorithm and then we show how this exact algorithm can be modified efficiently to ''RAND-ESU'' that estimates sub-graphs concentrations.