Hočevar Tomaž, Demšar Janez
Faculty of Computer and Information Science, University of Ljubljana, Ljubljana, Slovenia.
PLoS One. 2017 Feb 9;12(2):e0171428. doi: 10.1371/journal.pone.0171428. eCollection 2017.
Graphlet analysis is an approach to network analysis that is particularly popular in bioinformatics. We show how to set up a system of linear equations that relate the orbit counts and can be used in an algorithm that is significantly faster than the existing approaches based on direct enumeration of graphlets. The approach presented in this paper presents a generalization of the currently fastest method for counting 5-node graphlets in bioinformatics. The algorithm requires existence of a vertex with certain properties; we show that such vertex exists for graphlets of arbitrary size, except for complete graphs and a cycle with four nodes, which are treated separately. Empirical analysis of running time agrees with the theoretical results.
图元分析是一种在生物信息学中特别流行的网络分析方法。我们展示了如何建立一个线性方程组系统，该系统将轨道计数联系起来，并且可以用于一种算法中，该算法比基于直接枚举图元的现有方法要快得多。本文提出的方法是生物信息学中当前计数5节点图元最快方法的一种推广。该算法要求存在具有某些属性的顶点；我们表明，除了完全图和具有四个节点的环（它们将单独处理）之外，对于任意大小的图元都存在这样的顶点。运行时间的实证分析与理论结果一致。
