【ROSALIND】【练Python，学生信】72 从谱图推测多肽

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

题目：

从谱图推测多肽（Using the Spectrum Graph to Infer Peptides）

Given: A list L (of length at most 100) containing positive real numbers.

所给：不超过100个正实数的列表L。

Return: The longest protein string that matches the spectrum graph of L (if multiple solutions exist, you may output any one of them).

需得：根据L能得到的最长蛋白序列（如果有多个结果，只返回任意一个即可）。

测试数据

3524.8542

3623.5245

3710.9335

3841.974

3929.00603

3970.0326

4026.05879

4057.0646

4083.08025

测试输出

WMSPG

生物学背景

       在58 从全谱推测多肽序列中，我们假设每种b离子和y离子都可以存在。但在实际情况中，并非每一种断裂方式都会出现，且往往具有误差。因此，很难从单一的质谱结果中得到完整的多肽。我们需要从实验结果中推断出尽量长的多肽序列。

思路

       很不幸，这题我没有看懂，在网上搜索大神的代码（ttps://github.com/fedeoliv/Rosalind-Problems/blob/master/sgra.py）并运行后，我才大致弄明白解答思路。让我们以题目所给数据为示例，来用画图的方法理解一下解题思路。

       首先，题目给了由9个实数组成的列表L，且从小到大排列，我们用下图来表示：

       本题的最终目的就是从这9个数中得到最长的多肽，为了实现这个目的，大神从后往前遍历这个列表，方法是用一个数后面的每个数依次减这个数，假如差值对应了一个氨基酸，且能使现有序列最长，就保留。不懂？我们来用图看一下。

       从最后一个数开始，当用第9个数减去第7个数时，我们第一次得到了一个对应氨基酸的差值，我们可以在第7个数下面标记“G”，记录下此时的多肽序列。如下图。

       继续向前遍历，当用第8个数减去第6个数时，我们又得到了一个对应氨基酸的差值，我们可以在第6个数下面标记“S”。如下图。

       继续，当被减数是第5个数时，出现了两种情况。既可以用第7个数减去第5个数，也可以用第8个数减去第5个数。但我们只选择前者，为什么？因为前者可以让肽段的长度变成2（“PG”）。如下图。

       重复上述过程，你会发现上面的这条路径会一骑绝尘，超越所有其他情况的长度，最终我们得到了最长的序列“WMSPG”。

       理解了思路之后，再看大神的代码就很简单了，因此代码部分就不再给注释啦。

代码