python - 如何在边缘列表中找到所有派系

Question

我有一个来自旧 OrthoMCL 过程的直系同源基因的大量边缘列表文件(~80 GB)。我想从边列表中解析所有派系(所有顶点彼此共享边的子图)，然后将每个派系折叠为一行，同时忽略减少性(例如 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

提前致谢!

Answer 1

您可以简单地尝试函数 find_cliques function

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']

还有其他几个 functions in networkx for manipulating cliques如果你想看看。