如果第一次閱讀本系列文檔請先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫在前面 ?謝謝配合~

題目：

完全覆蓋情況下的基因組組裝（Genome Assembly with Perfect Coverage）

?

Given: A collection of (error-free) DNA k-mers (k≤50) taken from the same strand of a circular chromosome. In this dataset, all k-mers from this strand of the chromosome are present, and their de Bruijn graph consists of exactly one simple cycle.

所給：一組DNA的k-mers（k≤50）片段，無測序錯誤，且這些DNA片段來自同一個環(huán)裝染色體。這個染色體的所有k-mers都在這個數(shù)據(jù)集中，de Bruijn圖恰好形成一個環(huán)。

Return: A cyclic superstring of minimal length containing the reads (thus corresponding to a candidate cyclic chromosome).

需得：一條包含所有片段且長度最短的序列，對應(yīng)于待測的環(huán)裝染色體。

?

測試數(shù)據(jù)

ATTAC

TACAG

GATTA

ACAGA

CAGAT

TTACA

AGATT

測試輸出

GATTACA

?

背景

? ? ? ?盡管真核生物的染色體通常為線性，許多原核生物的染色體是環(huán)形的。我們用堿基序列來表示線性染色體，同樣的方法也適用于環(huán)形染色體。

? ? ? ?在測序中，完全覆蓋是指序列的每一個位置都有以此為開端的read（或稱k-mer）。隨著測序技術(shù)的發(fā)展，未來這也許不再是一種理想狀態(tài)，而成為一種真實(shí)的情況。

?

特別提醒

? ? ? ?本題假設(shè)所有k-mers都來自同一條鏈，這是很理想的情況，在實(shí)際操作中，研究者不會知道某個序列到底是從哪個鏈上測出來的。

?

思路

? ? ? ?本題思路和代碼來自https://github.com/fedeoliv/Rosalind-Problems/blob/master/pcov.py。只不過原代碼適用于python2環(huán)境，我將其改成了在python3中可以運(yùn)行。

? ? ? ?這道題需借助de brujin圖來理解，圖的每個結(jié)點(diǎn)由k-mers組成，當(dāng)兩個k-mers間存在k-1個完全匹配后，結(jié)點(diǎn)之間形成邊。以示例數(shù)據(jù)為例：

GATTA

? ?ATTAC

? ? ? TTACA

? ? ? ? ?TACAG

? ? ? ? ? ?ACAGA

? ? ? ? ? ? ? CAGAT

? ? ? ? ? ? ? ? ?AGATT

? ? ? ?代碼用字典來表示de brujin圖這種有向相連的關(guān)系，巧妙運(yùn)用鍵-值的變化實(shí)現(xiàn)了對圖的遍歷。

?

代碼