NetworkX: найдите самый длинный путь в DAG, возвращая все связи на максимум - PullRequest
Новая
       37

NetworkX: найдите самый длинный путь в DAG, возвращая все связи на максимум

0 голосов
/ 10 декабря 2018

У меня проблемы с выяснением того, как обновить алгоритм networkx dag_find_longest_path (), чтобы он возвращал "N" для связей вместо того, чтобы возвращать первое найденное максимальное ребро или возвращать список всех ребер, которые связаны для максимального веса.

Сначала я создал группу обеспечения доступности баз данных из кадра данных pandas, который содержит список ребер, подобный следующему подмножеству: 

edge1        edge2          weight
115252161:T  115252162:A     1.0
115252162:A  115252163:G     1.0
115252163:G  115252164:C     3.0
115252164:C  115252165:A     5.5
115252165:A  115252166:C     5.5
115252162:T  115252163:G     1.0
115252166:C  115252167:A     7.5
115252167:A  115252168:A     7.5
115252168:A  115252169:A     6.5
115252165:A  115252166:G     0.5

Затем я использую следующий код для топологической сортировки графика, а затем нахожу самый длинный путь в соответствии ск весам ребер: 

 G = nx.from_pandas_edgelist(edge_df, source="edge1", 
                                target="edge2", 
                                edge_attr=['weight'], 
                                create_using=nx.OrderedDiGraph())

longest_path = pd.DataFrame(nx.dag_longest_path(G))

Это прекрасно работает, за исключением случаев, когда есть связи для максимального взвешенного ребра, он возвращает первое найденное максимальное ребро, и вместо этого я хотел бы просто вернуть "N"представляющий" Нуль ".Итак, в настоящее время вывод: 

115252161   T
115252162   A
115252163   G
115252164   C
115252165   A
115252166   C

Но на самом деле мне нужно: 

115252161   T
115252162   N (or [A,T] )
115252163   G
115252164   C
115252165   A
115252166   C

Алгоритм поиска самого длинного пути: 

def dag_longest_path(G):

    dist = {}  # stores [node, distance] pair
    for node in nx.topological_sort(G):
        # pairs of dist,node for all incoming edges
        pairs = [(dist[v][0] + 1, v) for v in G.pred[node]]
        if pairs:
            dist[node] = max(pairs)
        else:
            dist[node] = (0, node)
    node, (length, _) = max(dist.items(), key=lambda x: x[1])
    path = []
    while length > 0:
        path.append(node)
        length, node = dist[node]
    return list(reversed(path))

Копируемое с возможностью вставки определение G. 

import pandas as pd
import networkx as nx
import numpy as np

edge_df = pd.read_csv(
    pd.compat.StringIO(
        """edge1        edge2          weight
115252161:T  115252162:A     1.0
115252162:A  115252163:G     1.0
115252163:G  115252164:C     3.0
115252164:C  115252165:A     5.5
115252165:A  115252166:C     5.5
115252162:T  115252163:G     1.0
115252166:C  115252167:A     7.5
115252167:A  115252168:A     7.5
115252168:A  115252169:A     6.5
115252165:A  115252166:G     0.5"""
    ),
    sep=r" +",
)


G = nx.from_pandas_edgelist(
    edge_df,
    source="edge1",
    target="edge2",
    edge_attr=["weight"],
    create_using=nx.OrderedDiGraph(),
)

longest_path = pd.DataFrame(nx.dag_longest_path(G))

Ответы [ 3 ]

0 голосов
/ 11 декабря 2018

Судя по вашему примеру, каждый узел определяется идентификатором позиции (число перед :), и два узла с разными присоединенными базами идентичны для целей расчета длины пути.Если это правильно, нет необходимости изменять алгоритм, и вы можете получить свой результат, манипулируя метками вершин.

По сути, отбросьте все после точки с запятой в edge_df, вычислите самый длинный путь и добавьте основание.метки из ваших исходных данных. 

edge_df_pos = pd.DataFrame(
    {
        "edge1": edge_df.edge1.str.partition(":")[0],
        "edge2": edge_df.edge2.str.partition(":")[0],
        "weight": edge_df.weight,
    }
)

vert_labels = dict()
for col in ("edge1", "edge2"):
    verts, lbls = edge_df[col].str.partition(":")[[0, 2]].values.T
    for vert, lbl in zip(verts, lbls):
        vert_labels.setdefault(vert, set()).add(lbl)


G_pos = nx.from_pandas_edgelist(
    edge_df_pos,
    source="edge1",
    target="edge2",
    edge_attr=["weight"],
    create_using=nx.OrderedDiGraph(),
)

longest_path_pos = nx.dag_longest_path(G_pos)

longest_path_df = pd.DataFrame([[node, vert_labels[node]] for node in longest_path_pos])

Результат 

# 0       1
# 0  115252161     {T}
# 1  115252162  {A, T}
# 2  115252163     {G}
# 3  115252164     {C}
# 4  115252165     {A}
# 5  115252166  {G, C}
# 6  115252167     {A}
# 7  115252168     {A}
# 8  115252169     {A}

Если моя интерпретация неверна, я сомневаюсь, что существует простое расширение алгоритма, основанного на топологической сортировке.Проблема в том, что граф может допускать несколько топологических сортировок.Если вы напечатаете dist, как определено в dag_longest_path в вашем примере, вы получите что-то вроде этого: 

{'115252161:T': (0, '115252161:T'),
 '115252162:A': (1, '115252161:T'),
 '115252162:T': (0, '115252162:T'),
 '115252163:G': (2, '115252162:A'),
 '115252164:C': (3, '115252163:G'),
 '115252165:A': (4, '115252164:C'),
 '115252166:C': (5, '115252165:A'),
 '115252166:G': (5, '115252165:A'),
 '115252167:A': (6, '115252166:C'),
 '115252168:A': (7, '115252167:A'),
 '115252169:A': (8, '115252168:A')}

Обратите внимание, что '115252162:T' находится в третьей строке и больше нигде.Следовательно, dist не может провести различие между вашим примером и другим примером, где '115252162:T' встречается как непересекающийся компонент.Поэтому не должно быть возможности восстановить любые пути через '115252162:T', просто используя данные в dist.

0 голосов
/ 12 декабря 2018

В итоге я просто смоделировал поведение в объекте счетчика defaultdict.

from collections import defaultdict, Counter

Я изменил свой список краев на кортеж (положение, нуклеотид, вес): 

test = [(112,"A",23.0), (113, "T", 27), (112, "T", 12.0), (113, "A", 27), (112,"A", 1.0)]

Затем использовал defaultdict (счетчик), чтобы быстро суммировать вхождения каждого нуклеотида в каждой позиции: 

nucs = defaultdict(Counter)

for key, nuc, weight in test:
    nucs[key][nuc] += weight

И затем перебираем словарь, чтобы извлечь все нуклеотиды, равные максимальному значению: 

for key, nuc in nucs.items():
    seq_list = []
    max_nuc = []
    max_val = max(nuc.values())
    for x, y in nuc.items():
        if y == max_val:
            max_nuc.append(x)

    if len(max_nuc) != 1:
        max_nuc = "N"
    else:
        max_nuc = ''.join(max_nuc)

    seq_list.append(max_nuc)
    sequence = ''.join(seq_list)

Возвращает окончательную последовательность для нуклеотида с найденным максимальным значением,и возвращает N в положении связи: 

TNGCACAAATGCTGAAAGCTGTACCATANCTGTCTGGTCTTGGCTGAGGTTTCAATGAATGGAATCCCGTAACTCTTGGCCAGTTCGTGGGCTTGTTTTGTATCAACTGTCCTTGTTGGCAAATCACACTTGTTTCCCACTAGCACCAT

Однако вопрос меня беспокоил, поэтому я закончил тем, что использовал атрибуты узла в networkx как средство пометить каждый узел как связующий или нет.Теперь, когда узел возвращается по самому длинному пути, я могу проверить атрибут «tie» и заменить имя узла на «N», если оно было помечено: 

def get_path(self, edge_df):

    G = nx.from_pandas_edgelist(
        edge_df,
        source="edge1",
        target="edge2",
        edge_attr=["weight"],
        create_using=nx.OrderedDiGraph()
    )

    # flag all nodes as not having a tie
    nx.set_node_attributes(G, "tie", False)

    # check nodes for ties
    for node in G.nodes:

        # create list of all edges for each node
        edges = G.in_edges(node, data=True)

        # if there are multiple edges
        if len(edges) > 1:

            # find max weight
            max_weight = max([edge[2]['weight'] for edge in edges])

            tie_check = []
            for edge in edges:
                # pull out all edges that match max weight
                if edge[2]["weight"] == max_weight:
                    tie_check.append(edge)

            # check if there are ties       
            if len(tie_check) > 1:
                for x in tie_check:

                    # flag node as being a tie
                    G.node[x[0]]["tie"] = True

    # return longest path
    longest_path = nx.dag_longest_path(G)     

    return longest_path
0 голосов
/ 11 декабря 2018

Эта строка внутри функции отбрасывает нужные вам пути;потому что max возвращает только один результат: 

node, (length, _) = max(dist.items(), key=lambda x: x[1])

Я бы сохранил максимальное значение, а затем искал бы по нему все элементы.Затем повторно используйте код, чтобы найти нужные пути.Пример будет выглядеть так: 

def dag_longest_path(G):
    dist = {}  # stores [node, distance] pair
    for node in nx.topological_sort(G):
        # pairs of dist,node for all incoming edges
        pairs = [(dist[v][0] + 1, v) for v in G.pred[node]]
        if pairs:
            dist[node] = max(pairs)
        else:
            dist[node] = (0, node)
    # store max value inside val variable
    node, (length, val) = max(dist.items(), key=lambda x: x[1])
    # find all dictionary items that have the maximum value
    nodes = [(item[0], item[1][0]) for item in dist.items() if item[1][1] == val]
    paths = []
    # iterate over the different nodes and append the paths to a list
    for node, length in nodes:
        path = []
        while length > 0:
            path.append(node)
            length, node = dist[node]
        paths.append(list(reversed(path)))
    return paths

PS.Я не проверял этот код, чтобы узнать, работает ли он правильно.

...