Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage
Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage
复制标题
将生物网络划分为具有最大边缘覆盖的高度连接的集群
DOI：
10.1109/tcbb.2013.177
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
R. Niedermeier
中科院分区：
文献类型：
--
作者：
F. Hüffner;C. Komusiewicz;A. Liebtrau;R. Niedermeier
Hartuv和Shamir提出了一种用于生物网络的聚类算法，用于识别非重叠的高度连通的组件。我们通过引入组合优化问题高度连接删除，要求删除尽可能少的边缘，从一个图形，使得到的图形由高度连接的组件，该算法所采取的方法进行扩展。我们表明，高度连接删除是NP难的，并提供了一个固定参数的算法和核。我们提出了确切的和启发式的解决方案的战略，基于多项式时间的数据简化规则和整数线性规划列生成。数据简化通常会识别出75%的被删除的边，以获得最佳解;然后，列生成方法可以在5小时内最佳地解决具有多达6，000个顶点和13，500条边的蛋白质相互作用网络。此外，我们提出了一个新的启发式，发现更多的集群比Hartuv和Shamir的方法。
A popular clustering algorithm for biological networks which was proposed by Hartuv and Shamir identifies nonoverlapping highly connected components. We extend the approach taken by this algorithm by introducing the combinatorial optimization problem Highly Connected Deletion, which asks for removing as few edges as possible from a graph such that the resulting graph consists of highly connected components. We show that Highly Connected Deletion is NP-hard and provide a fixed-parameter algorithm and a kernelization. We propose exact and heuristic solution strategies, based on polynomial-time data reduction rules and integer linear programming with column generation. The data reduction typically identifies 75 percent of the edges that are deleted for an optimal solution; the column generation method can then optimally solve protein interaction networks with up to 6,000 vertices and 13,500 edges within five hours. Additionally, we present a new heuristic that finds more clusters than the method by Hartuv and Shamir.
登录
查看更多内容
影响因子：
3
作者：
Chang WC;Vakati S;Krause R;Eulenstein O
通讯作者：
Eulenstein O
影响因子：
5.8
作者：
Gat-Viks, I;Sharan, R;Shamir, R
通讯作者：
Shamir, R
更快的确定性最大流量算法
DOI：
--
发表时间：
1992
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Valerie King;S. Rao;R. Tarjan
通讯作者：
R. Tarjan
DOI：
10.1136/ebmh.11.4.102
发表时间：
2008-10
期刊：
Evidence Based Mental Health
影响因子：
--
作者：
P. Cochat;L. Vaucoret;J. Sarles
通讯作者：
P. Cochat;L. Vaucoret;J. Sarles
更快的参数化集群删除和集群编辑
DOI：
10.1016/j.ipl.2011.05.003
发表时间：
2011
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
Sebastian Böcker;P. Damaschke
通讯作者：
P. Damaschke