370
个编辑
更改
跳到导航
跳到搜索
第556行：
第556行： − + − As seen in the table, motif discovery algorithms can be divided into two general categories: those based on exact counting and those using statistical sampling and estimations instead. Because the second group does not count all the occurrences of a subgraph in the main network, the algorithms belonging to this group are faster, but they might yield in biased and unrealistic results.+ − In the next level, the exact counting algorithms can be classified to network-centric and subgraph-centric methods. The algorithms of the first class search the given network for all subgraphs of a given size, while the algorithms falling into the second class first generate different possible non-isomorphic graphs of the given size, and then explore the network for each generated subgraph separately. Each approach has its advantages and disadvantages which are discussed above.+ − On the other hand, estimation methods might utilize color-coding approach as described before. Other approaches used in this category usually skip some subgraphs during enumeration (e.g., as in FANMOD) and base their estimation on the enumerated subgraphs.+ − − Furthermore, table indicates whether an algorithm can be used for directed or undirected networks as well as induced or non-induced subgraphs. For more information refer to the provided web links or lab addresses. + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − + − +
→Classification of algorithms
|}
|}
===Classification of algorithms===
===算法的分类===
正如表格所示，模体发现算法可以分为两大类：基于精确计数的算法，以及使用统计采样以及估计的算法。因为后者并不计数所有子图在主网络中出现的次数，所以第二类算法会更快，却也可能产生带有偏向性的，甚至不现实的结果。
更深一层地，基于精确计数的算法可以分为'''以网络为中心'''的方法以及以'''子图为中心'''的方法。前者在给定网络中搜索给定大小的子图，而后者首先根据给定大小生成各种可能的非同构图，然后在网络中分别搜索这些生成的图。这两种方法都有各自的优缺点，这些在上文有讨论。
另一方面，基于估计的方法可能会利用如前面描述过的颜色编码手段，其它的手段则通常会在枚举过程中忽略一些子图(比如，像在 FANMOD 中做的那样)，然后只在枚举出来的子图上做估计。
此外，表格还指出了一个算法能否应用于有向网络或无向网络，以及导出子图或非导出子图。更多信息请参考下方提供的网页和实验室地址及联系方式。
{|class="wikitable"
{|class="wikitable"
|+ Classification of Motif Discovery Algorithms
|+ 模体发现算法的分类
|-
|-
!Counting Method
!计数方式
!Basis
!基础
!Name
!算法名称
!Directed / Undirected
!有向 / 无向
!Induced / Non-Induced
!导出/ 非导出
|-
|-
| rowspan="9" |Exact
| rowspan="9" |精确基数
| rowspan="5" |Network-Centric
| rowspan="5" |以网络为中心
|[http://www.weizmann.ac.il/mcb/UriAlon/ mfinder]||Both||Induced
|[http://www.weizmann.ac.il/mcb/UriAlon/ mfinder]||皆可||导出
|-
|-
|[http://theinf1.informatik.uni-jena.de/~wernicke/motifs/ ESU (FANMOD)]||Both||Induced
|[http://theinf1.informatik.uni-jena.de/~wernicke/motifs/ ESU (FANMOD)]||皆可||导出
|-
|-
|[http://lbb.ut.ac.ir/Download/LBBsoft/Kavosh/ Kavosh] (used in [http://apps.cytoscape.org/apps/cytokavosh CytoKavosh])||Both||Induced
|[http://lbb.ut.ac.ir/Download/LBBsoft/Kavosh/ Kavosh] (used in [http://apps.cytoscape.org/apps/cytokavosh CytoKavosh])||皆可||导出
|-
|-
|[http://www.dcc.fc.up.pt/gtries/ G-Tries]||Both||Induced
|[http://www.dcc.fc.up.pt/gtries/ G-Tries]||皆可||导出
|-
|-
|[http://nesreenahmed.com/graphlets PGD]
|[http://nesreenahmed.com/graphlets PGD]
|Undirected
|无向
|Induced
|导出
|-
|-
|rowspan="4"|Subgraph-Centric
|rowspan="4"|以子图为中心
|[http://mavisto.ipk-gatersleben.de/ FPF (Mavisto)]||Both||Induced
|[http://mavisto.ipk-gatersleben.de/ FPF (Mavisto)]||皆可||导出
|-
|-
|[https://www.msu.edu/~jinchen/ NeMoFinder]||Undirected||Induced
|[https://www.msu.edu/~jinchen/ NeMoFinder]||无向||导出
|-
|-
|[http://people.cs.uchicago.edu/~joshuag/index.html Grochow–Kellis]||Both||Both
|[http://people.cs.uchicago.edu/~joshuag/index.html Grochow–Kellis]||皆可||Both
|-
|-
|[http://lbb.ut.ac.ir/Download/LBBsoft/MODA/ MODA]||Both||Both
|[http://lbb.ut.ac.ir/Download/LBBsoft/MODA/ MODA]||皆可||皆可
|-
|-
|rowspan="3"|Estimation / Sampling
|rowspan="3"|采样估计
|Color-Coding Approach
|颜色编码
|[http://www.math.tau.ac.il/~nogaa/ N. Alon] ''et al.''’s Algorithm||Undirected||Non-Induced
|[http://www.math.tau.ac.il/~nogaa/ N. Alon] ''et al.''’s Algorithm||无向||非导出
|-
|-
|rowspan="2"|Other Approaches
|rowspan="2"|其他手段
|[http://www.weizmann.ac.il/mcb/UriAlon/ mfinder]||Both||Induced
|[http://www.weizmann.ac.il/mcb/UriAlon/ mfinder]||皆可||导出
|-
|-
|[http://theinf1.informatik.uni-jena.de/~wernicke/motifs/ ESU (FANMOD)]||Both||Induced
|[http://theinf1.informatik.uni-jena.de/~wernicke/motifs/ ESU (FANMOD)]||皆可||导出
|}
|}
{|class="wikitable"
{|class="wikitable"
|+ Addresses of Designers of Algorithms
|+ 算法提出者的地址和联系方式
|-
|-
!Algorithm
!算法
!Lab / Dept. Name
!实验室/研究组
!Department / School
!学院
!Institute
!大学/研究所
!Address
!地址
!E-Mail
!电子邮件
|-
|-
|[http://www.weizmann.ac.il/mcb/UriAlon/ mfinder]||Uri Alon's Group||Department of Molecular Cell Biology||Weizmann Institute of Science||Rehovot, Israel, Wolfson, Rm. 607||urialon at weizmann.ac.il
|[http://www.weizmann.ac.il/mcb/UriAlon/ mfinder]||Uri Alon's Group||Department of Molecular Cell Biology||Weizmann Institute of Science||Rehovot, Israel, Wolfson, Rm. 607||urialon at weizmann.ac.il