【ROSALIND】【練Python，學(xué)生信】12 重疊圖與序列拼接
如果第一次閱讀本系列文檔請先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫在前面 ?謝謝配合~
題目：
構(gòu)建重疊圖（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鄰接表，以任意順序給出。
?
測試數(shù)據(jù)
>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
?
背景
? ? ? ? 圖論以圖為研究對象，圖是由若干給定的點及連接兩點的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點代表事物，用連接兩點的線表示相應(yīng)兩個事物間具有這種關(guān)系。
?
一個圖是一個有序的二元組<V，E>，記作G，其中：
(1) V = {v1, v2, ..., vn}是有限非空集合，稱為頂點集，其元素稱為頂點或結(jié)點。
(2)?E?=?{e1,?e2,?..., em}是有限集合，稱為邊集，E中每個元素都有V中的結(jié)點對與之對應(yīng)，稱為邊。
? ? ? ? 邊e既可以是有向的，也可以是無向的。有向邊與有序結(jié)點對<u,v>對應(yīng)，這時稱u為e的起點，v為e的終點。無向邊與無序結(jié)點對<u,v>對應(yīng)，u，v稱為e的兩個端點。
（轉(zhuǎn)載自CSDN
作者：Karen_Yu
原文：https://blog.csdn.net/karen_yu_/article/details/78776354）
當(dāng)一個圖的所有頂點都有名稱時，可以用鄰接表（adjacency list）的方式表示該圖，鄰接表每一行是兩個頂點的名稱，通過一個邊連接在一起。
對重疊圖（overlap graph）來說，Ok（k是正整數(shù)）代表被有向邊連接的兩個字符串（即頂點）s和t，s串最后k個字符與t串開頭k個字符相同，且t和s不相等。
重疊圖的思路常被應(yīng)用在在基因組組裝中。測序時，我們得到的測序數(shù)據(jù)相較于整個基因組而言是極小的；我們的任務(wù)是將這些小片段連接起來；序列之間的聯(lián)系因為重復(fù)序列的存在變得非常復(fù)雜，通過overlap最終都會構(gòu)建Graph，各種相關(guān)算法會從Graph中得到最優(yōu)路徑，從而得到最初的contig。
?
思路
將序列兩兩取出比較頭尾3個字符是否相同即可，是的話按順序存入一個列表當(dāng)中。
?
代碼
def readfasta(lines):
'''讀取FASTA格式文件的函數(shù)'''
??? 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):
'''判斷兩字符串頭尾是否有指定長度相同序列的函數(shù)'''
??? 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])) ??# 以適當(dāng)?shù)母袷捷敵?/p>
??? i += 1
?
