本文是论文“detecting overlapping protein complexes in protein-protein interaction networks”笔记。
Nepusz, T., Yu, H., & Paccanaro, A. (2012). Detecting overlapping protein complexes in protein-protein interaction networks.Nature Methods,9(5), 471.
文章提出了一种从蛋白质交互网络中检测potentially overlapping protein complexs的方法，称为CluterONE。从蛋白质网络中识别复合蛋白的问题可以转化为检测蛋白质交互网络中的包含较多连接的高密度区域（dense regions containing many connections in PPI networks）。
通常一种蛋白质有多种功能，会出现在多种复合蛋白质中，即，这样一个节点应该归属于多个复合蛋白中。然而目前的一些社交网络社团发现算法无法解决这一问题（2012年的文章，也许最近的工作可以解决这一问题）。此外在生物信息领域中一些其它的复合蛋白发现算法采用无权重的无向图，无法很好的解决权重图问题。本文提出的方法针对权重图问题，并且认为，尽可能利用节点间的权重关系，有助于更好的寻找复合蛋白。一个表示复合蛋白的子图应该满足以下两个结构上的属性：
1) 子图内包含许多可靠的连接
2) 该子图应该和图的其它部分很好的分离
ClusterONE基于内聚性得分（cohesiveness score）这一准则来寻找复合蛋白。
一个节点集合V的内聚性得分定义为f(V)。其中w^in(V)表示节点V之间边权重之和，w^bound(V)表示该节点集与图中其它节点连接边的权重之和。p表示该PPI中一个蛋白质尚未发现的连接的概率。
文章分为三个步骤来寻找复合蛋白。
1）从种子节点开始，寻找复合蛋白。通常选择度最大的节点作为初始的种子节点。当一个复合蛋白找到之后，从余下未包含在已找到的复合蛋白中的节点中选取种子节点，再次寻找复合蛋白。
在这一过程中，其详细的发现步骤为：
a) 选择种子节点，V_0 = {v_0}, 设置步数t=0；
b) 计算V_t的内聚性得分，令V_t+1 = V_t
c) 对每一个和V有连接的外部节点v，令V' = {V_t, v} 如果，f(V')>f(V_t+1),令V_t+1 = V'. （该步骤扩充节点，如果扩充的节点使得内聚上升，则纳入节点）
d) 对于子图内的每一个节点v，令V'' = V' \ {v}， 如果f(V'')>f(V_t+1) 那么令V_t+1 = V'' （该步骤删除节点，如果删除内部节点使得内聚上升，则删除节点）
e) 如果V_t != V_t+1, t = t+1，返回到步骤b)， 否则V_t为一个局部的聚合群体(即一个复合蛋白)
2）在这一步骤，对已经寻找到的复合蛋白进行合并。如果两个复合蛋白重叠的部分较多，则将两个复合蛋白合并。合并准则如下：
文章设置阈值为0.8，如果两个复合蛋白间的上述指标超过0.8，则对两个蛋白质进行合并。
3）在最终的步骤中，如果复合蛋白中包含的节点小于3，或者其density小于阈值（n个节点的复合蛋白V的density为W^in(V)/(n(n-1)/2) )
文章的主要方法如上，水平有限，如有错误，欢迎指正。
