【ROSALIND】【练Python，学生信】56 De Bruijn图的构建

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

De Bruijn图的构建（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条（可能有重复）DNA序列，长度均相等且不超过50 bp。

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

需得：由S∪Src组成的De Bruijn图对应的邻接表。

测试数据

TGAT

CATG

TCAT

ATGC

CATC

CATC

测试输出

(ATC, TCA)

(ATG, TGA)

(ATG, TGC)

(CAT, ATC)

(CAT, ATG)

(GAT, ATG)

(GCA, CAT)

(TCA, CAT)

(TGA, GAT)

生物学背景

        在二代测序中，所得数据的总长度将比基因组本身长得多。所以将测序的覆盖度定义为基因组中每个核苷酸出现的平均次数。换句话说，如果30亿bp基因组的总测序长度是300亿bp，那么我们获得的测序覆盖度是10x。因为我们要处理数量如此巨大的短的测序片段，必然需要合适的算法将短片段拼接起来，De Bruijn就是最常用的二代测序拼接算法。具体介绍可参考下面的文章：https://blog.csdn.net/Emmett_Bioinfo/article/details/109274974。

        有关k-mer的介绍请参考23 按字母顺序排列的K-mer。

数学背景

        有关De Bruijn图的介绍可以参考下面这篇文章：https://zhuanlan.zhihu.com/p/57177938。简单来说，De Bruijn图是一个展示符号序列之间重叠关系的有方向的示意图。在二代测序数据处理中， 测序片段（reads）打断成为长度为k的核酸片段（k-mer），随后根据k-mer间重复的部分构建De Bruijn 图，得到最优化路径从而实现序列的拼接。

        假设S是某DNA序列的(k+1)-mer组成的集合，Src是S中序列的反向互补序列组成的集合。则这两者的并集S∪Src 对应的De Bruijn 图Bk有如下特点：

1）Bk中的结点为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中的边由如下方式产生：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即可，写法较简单，请参考代码和注释。

代码