The maximum clique enumeration problem: algorithms, applications, and implementations.
The maximum clique enumeration problem: algorithms, applications, and implementations.
复制标题
DOI：
10.1186/1471-2105-13-s10-s5
复制
发表时间：
2012-06-25
影响因子：
3
通讯作者：
Langston MA
中科院分区：
文献类型：
--
作者：
Eblen JD;Phillips CA;Rogers GL;Langston MA
最大团枚举（MCE）问题要求我们在一个有限的、简单的图中识别所有的最大团。MCE与另外两个众所周知且被广泛研究的问题密切相关：最大团优化问题（要求我们确定最大团的大小）和最大团枚举问题（要求我们编制所有最大团的列表）。当然，这三个问题很难，因为它们包含了经典版本的完全集团决策问题。由于Bron、Kerbosch、Kose等的存在，MCE原则上可以用标准的枚举方法求解。不幸的是，这些技术并不适合我们应用程序中遇到的图形。我们必须在数据挖掘和计算生物学中深深扎根的实例上解决MCE问题，在这些实例中，高吞吐量的数据捕获通常会创建极端大小和密度的图形。原则上，MCE也可以使用更现代的算法来求解，这些算法部分基于顶点覆盖和固定参数可跟踪性（FPT）理论。虽然FPT是一种改进，但随着数据集的大小和密度的增长，这些算法也可能无法很好地扩展。广泛的基准图的测试平台是使用公开可用的转录组数据集从基因表达Omnibus （GEO）创建的。实证测试揭示了这种高通量生物数据的关键但潜在的特征。结果表明，这些特征将真实数据与旨在再现显著拓扑特征的随机数据区分开来。特别是，对于真实数据，往往存在异常高程度的最大集团重叠。有了这些知识，新的分解策略就可以针对数据进行调整，并与最佳的FPT MCE实现相结合。对MCE进行了若干算法改进，逐步减少了测试平台上图的运行时间。通常，最终的运行时改进是几个数量级。其结果是，曾经需要耗费大量时间才能解决的问题被带入了现实可行的领域。
The maximum clique enumeration (MCE) problem asks that we identify all maximum cliques in a finite, simple graph. MCE is closely related to two other well-known and widely-studied problems: the maximum clique optimization problem, which asks us to determine the size of a largest clique, and the maximal clique enumeration problem, which asks that we compile a listing of all maximal cliques. Naturally, these three problems are -hard, given that they subsume the classic version of the -complete clique decision problem. MCE can be solved in principle with standard enumeration methods due to Bron, Kerbosch, Kose and others. Unfortunately, these techniques are ill-suited to graphs encountered in our applications. We must solve MCE on instances deeply seeded in data mining and computational biology, where high-throughput data capture often creates graphs of extreme size and density. MCE can also be solved in principle using more modern algorithms based in part on vertex cover and the theory of fixed-parameter tractability (FPT). While FPT is an improvement, these algorithms too can fail to scale sufficiently well as the sizes and densities of our datasets grow. An extensive testbed of benchmark graphs are created using publicly available transcriptomic datasets from the Gene Expression Omnibus (GEO). Empirical testing reveals crucial but latent features of such high-throughput biological data. In turn, it is shown that these features distinguish real data from random data intended to reproduce salient topological features. In particular, with real data there tends to be an unusually high degree of maximum clique overlap. Armed with this knowledge, novel decomposition strategies are tuned to the data and coupled with the best FPT MCE implementations. Several algorithmic improvements to MCE are made which progressively decrease the run time on graphs in the testbed. Frequently the final runtime improvement is several orders of magnitude. As a result, instances which were once prohibitively time-consuming to solve are brought into the domain of realistic feasibility.