【ROSALIND】【练Python，学生信】69 完全覆盖情况下的基因组组装

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】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片段来自同一个环装染色体。这个染色体的所有k-mers都在这个数据集中，de Bruijn图恰好形成一个环。

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

需得：一条包含所有片段且长度最短的序列，对应于待测的环装染色体。

测试数据

ATTAC

TACAG

GATTA

ACAGA

CAGAT

TTACA

AGATT

测试输出

GATTACA

背景

       尽管真核生物的染色体通常为线性，许多原核生物的染色体是环形的。我们用碱基序列来表示线性染色体，同样的方法也适用于环形染色体。

       在测序中，完全覆盖是指序列的每一个位置都有以此为开端的read（或称k-mer）。随着测序技术的发展，未来这也许不再是一种理想状态，而成为一种真实的情况。

特别提醒

       本题假设所有k-mers都来自同一条链，这是很理想的情况，在实际操作中，研究者不会知道某个序列到底是从哪个链上测出来的。

思路

       本题思路和代码来自https://github.com/fedeoliv/Rosalind-Problems/blob/master/pcov.py。只不过原代码适用于python2环境，我将其改成了在python3中可以运行。

       这道题需借助de brujin图来理解，图的每个结点由k-mers组成，当两个k-mers间存在k-1个完全匹配后，结点之间形成边。以示例数据为例：

GATTA

   ATTAC

      TTACA

         TACAG

           ACAGA

              CAGAT

                 AGATT

       代码用字典来表示de brujin图这种有向相连的关系，巧妙运用键-值的变化实现了对图的遍历。

代码