2

我有一个包含许多基因及其相互作用的图表。我有兴趣找到一个子图，其中一组特定基因的最大数量是图中的 A、B、C、D、E。

尝试了 BFS 算法和连接的组件。但不知道如何找到我感兴趣的基因的子图。

def bfs(G, gene, n):
"""

Using breadth-first search
returns a graph of breadth n starting at source gene.
"""
S = nx.algorithms.traversal.breadth_first_search.bfs_tree(G, source=gene, depth_limit=n)
return S

给定一个具有 V 顶点和 E 边的图 G(V,E)，我想找到一个子图 G'(v,e)，其中 v 是 V 的子集，这样 G' 包含我感兴趣的最大节点。

4

1 回答 1

2

编辑虽然我认为我的原始代码（现在在底部）很好，但我认为你可以做得更好，使用node_connected_component(G,u)它返回与u.

让我解释一下下面的代码。首先，我将逐步介绍有趣的基因。对于第一个，我寻找G它所在的组件，然后找到同一组件中的所有其他有趣基因。然后，当我查看每个后续有趣的基因时，我确保我还没有在与另一个相同的组件中遇到它。如果它是一个新组件，我会在同一组件中找到所有其他有趣的基因。最后，我找到了具有最有趣基因的组件。

component_count = {}
seen = {}
for source in interesting_genes:
    if source not in seen:
        reachable_nodes = nx.node_connected_component(G, source)
        reachable_nodes_of_interest = [target for target in interesting_genes if target in reachable_nodes]
        for node in reachable_nodes_of_interest:
            seen[node] = True
        component_count = len(reachable_nodes_of_interest)

source = max(component_count, key=component_count.get) #finds the node with the largest component_count


Gprime = G.subgraph(nx.node_connected_component(G, source))

查看. _ _single_source_shortest_path_length

seen = {source:False for source in interesting_genes}  #if we've found the component of a node, no need to recalculate it.
component_count = {}  #will count how many other interesting genes there are in a component
for source in interesting_genes:
    if not seen[source]:
        reachable_nodes_dict = nx.single_source_shortest_path_length(G, node)
        reachable_nodes_of_interest = [target for target in interesting_genes if target in reachable_nodes_dict]
        for target in reachable_nodes_of_interest:
            seen[target] = True
        component_count[source] = len(reachable_nodes_of_interest)
source = max(component_count, key=component_count.get) #finds the node with the largest component_count


Gprime = G.subgraph(nx.node_connected_component(G, source))
于 2019-08-02T01:58:23.320 回答