用户讨论:木子二月鸟

模体发现算法 Motif discovery algorithms

Various solutions have been proposed for the challenging problem of motif discovery. These algorithms can be classified under various paradigms such as exact counting methods, sampling methods, pattern growth methods and so on. However, motif discovery problem comprises two main steps: first, calculating the number of occurrences of a sub-graph and then, evaluating the sub-graph significance. The recurrence is significant if it is detectably far more than expected. Roughly speaking, the expected number of appearances of a sub-graph can be determined by a Null-model, which is defined by an ensemble of random networks with some of the same properties as the original network.

Here, a review on computational aspects of major algorithms is given and their related benefits and drawbacks from an algorithmic perspective are discussed.

针对模体发现这一问题存在多种解决方案。这些算法可以归纳为不同的范式：例如精确计数方法，采样方法，模式增长方法等。但模体发现问题包括两个主要步骤：首先，计算子图的出现次数，然后评估子图的重要性。如果检测到的重现性远超过预期，那么这种重现性是很显著的。粗略地讲，子图的预期出现次数可以由零模型 Null-model 确定，该模型定义为具有与原始网络某些属性相同的随机网络的集合。

接下来，对下列算法的计算原理进行简要回顾，并从算法的角度讨论了它们的优缺点。