如果第一次阅读本系列文档请先移步阅读【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图这种有向相连的关系，巧妙运用键-值的变化实现了对图的遍历。

代码

def get_superstring(collection):
    db = dict([(dna[:-1], dna[1:]) for dna in collection]) # 将序列以字典的形式储存，键为每个k-mers的前(k-1)个字符，值为后(k-1)个字符
    k = list(db.keys())[0] # 从字典中取出一个键，以开启下面的循环
    superstring = ''

    while len(superstring) < len(collection): # 由于每个k-mers间都有(k-1)隔重合，所以最终序列的长度与不会超过数据集中片段的数目
        superstring += db[k][-1] # 用键查找到值，将这个k-mers末尾的字符添加到序列末端
        k = db[k] # 将这个键作为值输入字典，获取新的键

    return superstring


if __name__ == '__main__':
    collection = open('rosalind_pcov.txt').read().strip().split('\n')
    print(get_superstring(collection))