【ROSALIND】【练Python，学生信】58 从全谱推测多肽序列

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

题目：

从全谱推测多肽序列（Inferring Peptide from Full Spectrum）

Given: A list L containing 2n+3 positive real numbers (n≤100). The first number in L is the parent mass of a peptide P, and all other numbers represent the masses of some b-ions and y-ions of P (in no particular order). You may assume that if the mass of a b-ion is present, then so is that of its complementary y-ion, and vice-versa.

所给：包含2n+3（n≤100）个正实数的列表L，第一个数是多肽P的总质量，其他数都是P所得到的的b离子和y离子的质量（未经排序）。你可以认为，如果某个b离子存在，它的对应y离子也肯定存在，反之亦然。

Return: A protein string t of length n for which there exist two positive real numbers w1 and w2 such that for every prefix p and suffix s of t, each of w(p)+w1 and w(s)+w2 is equal to an element of L. (In other words, there exists a protein string whose t-prefix and t-suffix weights correspond to the non-parent mass values of L.) If multiple solutions exist, you may output any one..

需得：长度为n的蛋白序列t。对t来说：存在两个正实数w1和w2，对于t的每个前缀p和后缀s，w（p）+w1和w（s）+w2都等于L的一个元素。如果存在多个解，可以输出任意一个。

测试数据

1988.21104821

610.391039105

738.485999105

766.492149105

863.544909105

867.528589105

992.587499105

995.623549105

1120.6824591

1124.6661391

1221.7188991

1249.7250491

1377.8200091

测试输出

KEKEP

生物学背景

        在52 从前缀谱到多肽序列中，我们了解了b离子和y离子，也知道了如何从b离子反推蛋白序列。但在实际操作中，我们是无法区分b离子和y离子的，在质谱结果中，我们通常能得到成对的离子，例如， ("PR")的质量 + ("TEIN") 的质量= ("PRTEIN")的质量。因此，如果我们已知整个多肽的质量，就可以用b离子的质量推测出y离子的质量，反之亦然。

        对长度为n的蛋白质P，我们可以简化问题如下：构建所有可能位置的断裂，计算每种断裂方式形成的b离子和y离子的质量。在本题中，我们只关注发生过断裂的区域其他位置的质量被视为常数包含在所给离子的质量中。即多肽链s包含子串t，s可以写作s1ts2，断裂只在t中发生，所以每个前缀都包含s1，每个后缀都包含s2。

思路

        这道题题目读起来十分拗口，我有些地方读了好几遍都没有读通，但其实画一画就十分明显了。如下图，一段完整的多肽序列被分成3部分，假设在质谱检测中，断裂只在t序列中发生。

        我们只要把断裂产生的b、y离子分别求出来，排好序，依次相减，就可以得到t段的序列了。

        至此，本题可以分解为两个小问题。

        第一个问题是把成对的b、y离子分别找出来。我认为，成对的b、y离子质量之和等于多肽的总质量，所以我把每个离子的质量取出来（实际只需取前半部分就够了）依次与其他离子相加，和与多肽总质量相减，差值最小的肯定是成对的离子。这样做只能保证成对，但无法分辨哪个是b离子，哪个是y离子。

        第二个问题是前后两离子相减，得到对应残基。这里我用后一对离子中较小的那个减去前一对离子中较小的那个，不难想到，如果得到的差值可以对应一个残基，那这两个离子均为b离子或均为y离子；如果得到的差不是残基，那么这两个离子一个为b离子，一个为y离子。我统一把后一对离子交换位置，再将离子对列表重新排序。重复这个过程，就能得到多肽序列t。

代码

monoisotopic mass table.txt文件内容：

A   71.03711

C   103.00919

D   115.02694

E   129.04259

F   147.06841

G   57.02146

H   137.05891

I   113.08406

K   128.09496

L   113.08406

M   131.04049

N   114.04293

P   97.05276

Q   128.05858

R   156.10111

S   87.03203

T   101.04768

V   99.06841

W   186.07931

Y   163.06333