【ROSALIND】【练Python，学生信】12 重叠图与序列拼接
如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面 谢谢配合~
题目：
构建重叠图（overlap graph）
Given: A collection of DNA strings in FASTA format having total length at most 10 kbp.
所给：多条DNA序列，长度均不超过10kb，以FASTA格式给出。
Return: The adjacency list corresponding to O3. You may return edges in any order.
需得：O3邻接表，以任意顺序给出。
测试数据
>Rosalind_0498
AAATAAA
>Rosalind_2391
AAATTTT
>Rosalind_2323
TTTTCCC
>Rosalind_0442
AAATCCC
>Rosalind_5013
GGGTGGG
测试输出
Rosalind_0498 Rosalind_2391
Rosalind_0498 Rosalind_0442
Rosalind_2391 Rosalind_2323
背景
图论以图为研究对象，图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
一个图是一个有序的二元组<V，E>，记作G，其中：
(1) V = {v1, v2, ..., vn}是有限非空集合，称为顶点集，其元素称为顶点或结点。
(2) E = {e1, e2, ..., em}是有限集合，称为边集，E中每个元素都有V中的结点对与之对应，称为边。
边e既可以是有向的，也可以是无向的。有向边与有序结点对<u,v>对应，这时称u为e的起点，v为e的终点。无向边与无序结点对<u,v>对应，u，v称为e的两个端点。
（转载自CSDN
作者：Karen_Yu
原文：https://blog.csdn.net/karen_yu_/article/details/78776354）
当一个图的所有顶点都有名称时，可以用邻接表（adjacency list）的方式表示该图，邻接表每一行是两个顶点的名称，通过一个边连接在一起。
对重叠图（overlap graph）来说，Ok（k是正整数）代表被有向边连接的两个字符串（即顶点）s和t，s串最后k个字符与t串开头k个字符相同，且t和s不相等。
重叠图的思路常被应用在在基因组组装中。测序时，我们得到的测序数据相较于整个基因组而言是极小的；我们的任务是将这些小片段连接起来；序列之间的联系因为重复序列的存在变得非常复杂，通过overlap最终都会构建Graph，各种相关算法会从Graph中得到最优路径，从而得到最初的contig。
思路
将序列两两取出比较头尾3个字符是否相同即可，是的话按顺序存入一个列表当中。
代码
def readfasta(lines):
'''读取FASTA格式文件的函数'''
seq = []
index = []
seqplast = ""
numlines = 0
for i in lines:
if '>' in i:
index.append(i.replace("\n", "").replace(">", ""))
seq.append(seqplast.replace("\n", ""))
seqplast = ""
numlines += 1
else:
seqplast = seqplast + i.replace("\n", "")
numlines += 1
if numlines == len(lines):
seq.append(seqplast.replace("\n", ""))
seq = seq[1:]
return index, seq
def isoverlap(n,s1,s2):
'''判断两字符串头尾是否有指定长度相同序列的函数'''
return s1[-n:] == s2[:n]
f = open('rosalind_grph.txt', 'r')
lines = f.readlines()
f.close()
[index,seq] = readfasta(lines)
k = 3
i =0
edges = []
while i < len(seq):
j = i+1
while j < len(seq):
if isoverlap(k, seq[i], seq[j]): # 两两取出序列，进行判断
edges.append([index[i],index[j]])
elif isoverlap(k, seq[j], seq[i]):
edges.append([index[j], index[i]])
j += 1
i += 1
i = 0
while i < len(edges):
print(' '.join(edges[i])) # 以适当的格式输出
i += 1
