Алгоритм построения графика DeBruijn дает неправильные результаты

Question

Я пытаюсь написать некоторый код для построения графа DeBruijn из набора klerers (k буквенных длинных строк, чтения последовательности ДНК) в Python, выводятся как совокупность ребер, соединяющих тот же узел к другим.

Когда я запускаю мой код на входе образца:

['GAGG','CAGG','GGGG','GGGA','CAGG','AGGG','GGAG'] 

я получаю:

CAG -> AGG 
GAG -> AGG 

Вместо:

AGG -> GGG 
CAG -> AGG,AGG 
GAG -> AGG 
GGA -> GAG 
GGG -> GGA,GGG 

Любой намек на то, что я делаю неправильно?
Вот код:

import itertools 

inp=['GAGG','CAGG','GGGG','GGGA','CAGG','AGGG','GGAG'] 

y=[a[1:] for a in inp] 
z=[b[:len(b)-1] for b in inp] 

y.extend(z) 
edjes=list(set(y)) 

w=[c[1:] for c in edjes] 
v=[d[:len(d)-1] for d in edjes] 

w.extend(v) 

nodes=list(set(w)) 

graph={} 


new=itertools.product(edjes,edjes) 

for node in nodes: 
    for edj in new: 
     edje1,edje2=edj[0],edj[1] 
     if edje1[1:]==node and edje2[:len(edje2)-1]==node: 
      if edje1 in graph: 
       graph[edje1].append(edje2) 
      else: 
       graph[edje1]=[edje2] 

for val in graph.values(): 
    val.sort() 


for k,v in sorted(graph.items()): 
    if len(v)<1: 
     continue 
    else: 
     line=k+' -> '+','.join(v)+'\n' 
    print (line) 

Answer 1

Я думаю, что вы делаете алгоритм слишком сложным: вы можете просто первым выполнить уникальность фильтра на входе:

inp=['GAGG','CAGG','GGGG','GGGA','CAGG','AGGG','GGAG'] 

edges=list(set(inp)) 

А затем перебрать этот список «края». Для каждого ребра, первые три символа является от узла, последние три символа является в узле:

for edge in edges: 
    frm = edge[:len(edge)-1] 
    to = edge[1:] 
    #... 

Теперь вам просто нужно добавить к вашему графику:

for edge in edges: 
    frm = edge[:len(edge)-1] 
    to = edge[1:] 
    if frm in graph: 
     graph[frm].append(to) 
    else: 
     graph[frm]=[to] 

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

for val in graph.values(): 
    val.sort() 

for k,v in sorted(graph.items()): 
    print(k+' -> '+','.join(v)) 

Это приводит к:

AGG -> GGG 
CAG -> AGG 
GAG -> AGG 
GGA -> GAG 
GGG -> GGA,GGG 

Как вы можете видеть, есть небольшая разница в строке 2: есть ваш ожидаемый результат содержит AGG два раза, что делает не имеет особого смысла.

Так что полный алгоритм что-то вроде:

inp=['GAGG','CAGG','GGGG','GGGA','CAGG','AGGG','GGAG'] 

edges=list(set(inp)) 

graph={} 

for edge in edges: 
    frm = edge[:len(edge)-1] 
    to = edge[1:] 
    if frm in graph: 
     graph[frm].append(to) 
    else: 
     graph[frm]=[to] 

for val in graph.values(): 
    val.sort() 

for k,v in sorted(graph.items()): 
    print(k+' -> '+','.join(v)) 

Ваш алгоритм

Проблема я думаю, является то, что вы считаете, трехбуквенные последовательности, чтобы быть «edjes» (вероятно, края). Края - это четыре символа последовательности. Выполняя это преобразование, информация теряется. Затем вы создаете набор двухсимвольных элементов (nodes, которые вообще не являются узлами). Кажется, что они используются для «склеивания» узлов вместе. Но на этом этапе вы больше не знаете, как склеиваются кусочки в любом случае.