如何在边缘列表中找到所有的团？

Question

我有一个巨大的边缘列表文件(~80 GB)，包含来自旧OrthoMCL过程的同源基因。我想要将边缘列表中的所有团 (所有顶点之间都共享一个边缘的子图) 解析出来，然后将每个团折叠成一行，并忽略冗余性(如GeneA,GeneB<->GeneB,GeneA)和自身碰撞(GeneA<->GeneA)。我正在尝试使用Python的networkX(find_cliques)，但我是比较经验不足的编程人员，所以我没有得到期望的输出。如果有任何有经验的网络结构工作者，您能否指引我正确的方向呢？

以下是示例输入:

GeneA,GeneA
GeneA,GeneB
GeneA,GeneC
GeneB,GeneA
GeneB,GeneB
GeneB,GeneC
GeneC,GeneA
GeneC,GeneB
GeneC,GeneC
GeneD,GeneD
GeneD,GeneE
GeneD,GeneF
GeneE,GeneD
GeneE,GeneE
GeneE,GeneF
GeneF,GeneD
GeneF,GeneE
GeneF,GeneF
GeneH,GeneH
GeneH,GeneI
GeneH,GeneJ
GeneH,GeneK
GeneH,GeneL
GeneH,GeneM
GeneH,GeneN
GeneH,GeneO
GeneH,GeneP
GeneH,GeneQ
GeneI,GeneH
GeneI,GeneI
GeneI,GeneJ
GeneI,GeneK
GeneI,GeneL
GeneI,GeneM
GeneI,GeneN
GeneI,GeneO
GeneI,GeneP
GeneI,GeneQ
GeneJ,GeneH
GeneJ,GeneI
GeneJ,GeneJ
GeneJ,GeneK
GeneJ,GeneL
GeneJ,GeneM
GeneJ,GeneN
GeneJ,GeneO
GeneJ,GeneP
GeneJ,GeneQ
GeneK,GeneH
GeneK,GeneI
GeneK,GeneJ
GeneK,GeneK
GeneK,GeneL
GeneK,GeneM
GeneK,GeneN
GeneK,GeneO
GeneK,GeneP
GeneK,GeneQ
GeneL,GeneH
GeneL,GeneI
GeneL,GeneJ
GeneL,GeneK
GeneL,GeneL
GeneL,GeneM
GeneL,GeneN
GeneL,GeneO
GeneL,GeneP
GeneL,GeneQ
GeneM,GeneH
GeneM,GeneI
GeneM,GeneJ
GeneM,GeneK
GeneM,GeneL
GeneM,GeneM
GeneM,GeneN
GeneM,GeneO
GeneM,GeneP
GeneM,GeneQ
GeneN,GeneH
GeneN,GeneI
GeneN,GeneJ
GeneN,GeneK
GeneN,GeneL
GeneN,GeneM
GeneN,GeneN
GeneN,GeneO
GeneN,GeneP
GeneN,GeneQ
GeneO,GeneH
GeneO,GeneI
GeneO,GeneJ
GeneO,GeneK
GeneO,GeneL
GeneO,GeneM
GeneO,GeneN
GeneO,GeneO
GeneO,GeneP
GeneO,GeneQ
GeneP,GeneH
GeneP,GeneI
GeneP,GeneJ
GeneP,GeneK
GeneP,GeneL
GeneP,GeneM
GeneP,GeneN
GeneP,GeneO
GeneP,GeneP
GeneP,GeneQ
GeneQ,GeneH
GeneQ,GeneI
GeneQ,GeneJ
GeneQ,GeneK
GeneQ,GeneL
GeneQ,GeneM
GeneQ,GeneN
GeneQ,GeneO
GeneQ,GeneP
GeneQ,GeneQ
GeneR,GeneR
GeneR,GeneS
GeneR,GeneT
GeneR,GeneU
GeneS,GeneR
GeneS,GeneS
GeneS,GeneT
GeneS,GeneU
GeneT,GeneR
GeneT,GeneS
GeneT,GeneT
GeneT,GeneU
GeneU,GeneR
GeneU,GeneS
GeneU,GeneT
GeneU,GeneU
GeneV,GeneW
GeneW,GeneV
GeneX,GeneX
GeneX,GeneY
GeneX,GeneZ
GeneY,GeneX
GeneY,GeneY
GeneY,GeneZ
GeneZ,GeneX
GeneZ,GeneY
GeneZ,GeneZ

以下是所需的输出：

GeneA,GeneB,GeneC
GeneD,GeneE,GeneF
GeneH,GeneI,GeneJ,GeneK,GeneL,GeneM,GeneN,GeneO,GeneP,GeneQ
GeneR,GeneS,GeneT,GeneU
GeneV,GeneW
GeneX,GeneY,GeneZ

提前感谢您！

- Gloom

---

如果输入是这个图，其中ABCD和ABCE都是最大团，但ABCDE不是一个团，那该怎么办？此外，任何团的子图也是团，但您的示例输出没有列出这些团。 - user2357112

我认为这个数据集不会有问题，因为原始的聚类机制显然非常严格。但如果出现这种情况，我更愿意接受准团簇 ABCDE 而不是 ABCD 或 ABCE。这种做法可行吗？ - Gloom

可能是可以的，但听起来您的图表可能具有重要的结构，这可以简化问题。您的示例图恰好是6个完全图的不相交并集（一个K2，三个K3，一个K4和一个K10），使其团结构非常简单。您的真实数据是否保证具有类似的属性？ - user2357112

我不会说保证，但那肯定是预期的结果。 - Gloom

Answer 1

你可以尝试使用 find_cliques函数 来实现。

import networkx as nx
G = nx.read_edgelist("edgelist.txt",delimiter=',')

for clq in nx.clique.find_cliques(G):
    print clq

输出

[u'GeneX', u'GeneY', u'GeneZ']
[u'GeneP', u'GeneQ', u'GeneH', u'GeneI', u'GeneJ', u'GeneK', u'GeneL', u'GeneM', u'GeneN', u'GeneO']
[u'GeneR', u'GeneS', u'GeneT', u'GeneU']
[u'GeneV', u'GeneW']
[u'GeneA', u'GeneB', u'GeneC']
[u'GeneD', u'GeneE', u'GeneF']

如果您想了解更多信息，可以查看networkx中用于操作团的其他函数。

- Gambit1614