如何从NetworkX图形转换为ete3树对象？

Question

我想知道如何从networkx有向图中构建ete3.Tree对象？我添加了每个child的方式，我认为可以产生预期的结果，但我有麻烦。在

edges = [('lvl-1', 'lvl-2.1'), ('lvl-1', 'lvl-2.2'), ('lvl-2.1', 'lvl-3.1'), ('lvl-2.1', 2), ('lvl-2.2', 4), ('lvl-2.2', 6), ('lvl-3.1', 'lvl-4.1'), ('lvl-3.1', 5), ('lvl-4.1', 1), ('lvl-4.1', 3), ('input', 'lvl-1')]
graph = nx.OrderedDiGraph()
graph.add_edges_from(edges)
nx.draw(graph, pos=nx.nx_agraph.graphviz_layout(graph, prog="dot"), with_labels=True, node_size=1000, node_color="lightgray")

^{pr2}$

我也尝试了以下方法，但没有奏效：

tree = ete3.Tree()
for parent, child in graph.edges():
    if parent not in tree:
        tree.add_child(name=parent)
    subtree = tree.search_nodes(name=parent)[0]
    subtree.add_child(name=child)
print(tree)
#                /-1
#             /-|
#          /-|   \-3
#         |  |
#       /-|   \-5
#      |  |
#    /-|   \-2
#   |  |
#   |  |   /-4
# --|   \-|
#   |      \-6
#   |
#    \- /-lvl-1

Answer 1

# Graph
edges = [('lvl-1', 'lvl-2.1'), ('lvl-1', 'lvl-2.2'), ('lvl-2.1', 'lvl-3.1'), ('lvl-2.1', 2), ('lvl-2.2', 4), ('lvl-2.2', 6), ('lvl-3.1', 'lvl-4.1'), ('lvl-3.1', 5), ('lvl-4.1', 1), ('lvl-4.1', 3), ('input', 'lvl-1')]
G = nx.OrderedDiGraph()
G.add_edges_from(edges)

# Tree
root = "input"
subtrees = {node:ete3.Tree(name=node) for node in G.nodes()}
[*map(lambda edge:subtrees[edge[0]].add_child(subtrees[edge[1]]), G.edges())]
tree = subtrees[root]
print(tree.get_ascii())
#                                /-1
#                         /lvl-4.1
#                  /lvl-3.1      \-3
#                 |      |
#           /lvl-2.1      \-5
#          |      |
# -inputlvl-1      \-2
#          |
#          |       /-4
#           \lvl-2.2
#                  \-6

Answer 2

子树和从networkX对象读取都是正常的，问题是您将所有子树直接添加到原始的tree实例中。在ete3中，Tree类是in fact just a Node（包括指向其后代的指针，如果有的话），因此tree.add_child直接向根节点添加新的子节点/子树。在

您应该做的是iterate over the leaves of ete tree，找到node.name == parent的那个，并将所有子元素附加到它上。另外，您应该逐个附加它们，而不是预先生成子树。否则，您将获得具有单个父节点和单个子节点的附加内部节点。在

编辑：

代码的第二个版本几乎是正确的，但是您没有考虑到如果根不是它们的实际父节点，则节点永远不会被附加到树（ieroot）。这可能就是为什么您将lvl-1作为一个单独的节点，而不是其他节点的父节点。另外，我不确定networkX图的遍历顺序，这可能很重要。更安全（如果更丑）的版本应该是这样的：

# Setting up a root node for lvl-1 to attach to
tree.add_child(name='input')
# A copy in a list, because you may not want to edit the original graph
edges = list(graph.edges)
while len(edges) > 0:
    for parent, child in edges:
        # check if this edge's parent is in the tree
        for leaf it tree.get_leaves(): 
            if leaf.name == parent:
                # if it is, add child and thus create an edge
                leaf.add_child(name=child)
            # Wouldn't want to add the same edge twice, would you?
            edges.remove((parent, child))
    # Now if there are edges still unplaced, try again.

可能有几个打字错误，而且绝对是超慢。从边缘计数到O（n**2）或更糟的东西，包括所有的迭代和列表删除。可能有一种方法可以将图从根遍历到叶，这不需要边列表的副本（只需一次迭代即可工作）。但它最终会产生一棵正确的树。在