我正在尝试编写一些代码,用 Python 中的一组 kmers(k 字母长字符串,DNA 测序读取)构建 DeBruijn 图,输出为边集合,将同一节点连接到其他节点。
当我在示例输入上运行代码时:
['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)
最佳答案
我认为你使算法变得过于复杂:你可以简单地首先对输入执行唯一性过滤器:
inp=['GAGG','CAGG','GGGG','GGGA','CAGG','AGGG','GGAG']
edges=list(set(inp))
然后迭代这个“边”列表。对于每条边,前三个字符是 from 节点,后三个字符是 to 节点:
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”(可能边缘)。边缘是四个序列字符。通过执行此转换,信息会丢失。接下来,您构建一组两个字符的项目(节点
,它们根本不是节点)。它们似乎是用来将节点“粘合”在一起的。但在那个阶段,你不再知道这些碎片是如何粘合在一起的。
关于python - 构建 DeBruijn 图的算法给出了错误的结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34354444/