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

題目：

De Bruijn圖的構(gòu)建（Constructing a De Bruijn Graph）

?

Given: A collection of up to 1000 (possibly repeating) DNA strings of equal length (not exceeding 50 bp) corresponding to a set S of (k+1)-mers.

所給：一個含有(k+1)-mer的集合S，其中至少包含1000條（可能有重復(fù)）DNA序列，長度均相等且不超過50 bp。

Return: The adjacency list corresponding to the de Bruijn graph corresponding to S∪Src.

需得：由S∪Src組成的De Bruijn圖對應(yīng)的鄰接表。

?

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

TGAT

CATG

TCAT

ATGC

CATC

CATC

測試輸出

(ATC, TCA)

(ATG, TGA)

(ATG, TGC)

(CAT, ATC)

(CAT, ATG)

(GAT, ATG)

(GCA, CAT)

(TCA, CAT)

(TGA, GAT)

?

生物學(xué)背景

? ? ? ? 在二代測序中，所得數(shù)據(jù)的總長度將比基因組本身長得多。所以將測序的覆蓋度定義為基因組中每個核苷酸出現(xiàn)的平均次數(shù)。換句話說，如果30億bp基因組的總測序長度是300億bp，那么我們獲得的測序覆蓋度是10x。因為我們要處理數(shù)量如此巨大的短的測序片段，必然需要合適的算法將短片段拼接起來，De Bruijn就是最常用的二代測序拼接算法。具體介紹可參考下面的文章：https://blog.csdn.net/Emmett_Bioinfo/article/details/109274974。

? ? ? ??有關(guān)k-mer的介紹請參考23 按字母順序排列的K-mer。

?

數(shù)學(xué)背景

? ? ? ??有關(guān)De Bruijn圖的介紹可以參考下面這篇文章：https://zhuanlan.zhihu.com/p/57177938。簡單來說，De Bruijn圖是一個展示符號序列之間重疊關(guān)系的有方向的示意圖。在二代測序數(shù)據(jù)處理中， 測序片段（reads）打斷成為長度為k的核酸片段（k-mer），隨后根據(jù)k-mer間重復(fù)的部分構(gòu)建De Bruijn 圖，得到最優(yōu)化路徑從而實現(xiàn)序列的拼接。

? ? ? ??假設(shè)S是某DNA序列的(k+1)-mer組成的集合，Src是S中序列的反向互補序列組成的集合。則這兩者的并集S∪Src 對應(yīng)的De Bruijn 圖Bk有如下特點：

1）Bk中的結(jié)點為S∪Src中的(k+1)-mer所包含的k-mers。（Nodes of Bk correspond to all k-mers that are present as a substring of a (k+1)-mer from S∪Src.）

2）Bk中的邊由如下方式產(chǎn)生：S∪Src中的每個(k+1)-mer（用r表示），形成有向邊（r[1:k]，r[2:k+1]）。（Edges of Bk are encoded by the (k+1)-mers of S∪Src in the following way: for each (k+1)-mer r in S∪Src, form a directed edge (r[1:k], r[2:k+1]).）

?

思路

這道題是對之前k-mer和集合知識的小小回顧。我的方法是先得到S∪Src，然后取出其中的每個元素分別得到k-mer即可，寫法較簡單，請參考代碼和注釋。

代碼