如果第一次閱讀本系列文檔請(qǐng)先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫在前面 ?謝謝配合~

題目：

從全譜推測(cè)多肽序列（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）個(gè)正實(shí)數(shù)的列表L，第一個(gè)數(shù)是多肽P的總質(zhì)量，其他數(shù)都是P所得到的的b離子和y離子的質(zhì)量（未經(jīng)排序）。你可以認(rèn)為，如果某個(gè)b離子存在，它的對(duì)應(yīng)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..

需得：長(zhǎng)度為n的蛋白序列t。對(duì)t來(lái)說(shuō)：存在兩個(gè)正實(shí)數(shù)w1和w2，對(duì)于t的每個(gè)前綴p和后綴s，w（p）+w1和w（s）+w2都等于L的一個(gè)元素。如果存在多個(gè)解，可以輸出任意一個(gè)。

?

測(cè)試數(shù)據(jù)

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

測(cè)試輸出

KEKEP

?

生物學(xué)背景

? ? ? ? 在52 從前綴譜到多肽序列中，我們了解了b離子和y離子，也知道了如何從b離子反推蛋白序列。但在實(shí)際操作中，我們是無(wú)法區(qū)分b離子和y離子的，在質(zhì)譜結(jié)果中，我們通常能得到成對(duì)的離子，例如， ("PR")的質(zhì)量 + ("TEIN") 的質(zhì)量= ("PRTEIN")的質(zhì)量。因此，如果我們已知整個(gè)多肽的質(zhì)量，就可以用b離子的質(zhì)量推測(cè)出y離子的質(zhì)量，反之亦然。

? ? ? ??對(duì)長(zhǎng)度為n的蛋白質(zhì)P，我們可以簡(jiǎn)化問(wèn)題如下：構(gòu)建所有可能位置的斷裂，計(jì)算每種斷裂方式形成的b離子和y離子的質(zhì)量。在本題中，我們只關(guān)注發(fā)生過(guò)斷裂的區(qū)域其他位置的質(zhì)量被視為常數(shù)包含在所給離子的質(zhì)量中。即多肽鏈s包含子串t，s可以寫作s1ts2，斷裂只在t中發(fā)生，所以每個(gè)前綴都包含s1，每個(gè)后綴都包含s2。

?

思路

? ? ? ??這道題題目讀起來(lái)十分拗口，我有些地方讀了好幾遍都沒(méi)有讀通，但其實(shí)畫(huà)一畫(huà)就十分明顯了。如下圖，一段完整的多肽序列被分成3部分，假設(shè)在質(zhì)譜檢測(cè)中，斷裂只在t序列中發(fā)生。

? ? ? ??我們只要把斷裂產(chǎn)生的b、y離子分別求出來(lái)，排好序，依次相減，就可以得到t段的序列了。

? ? ? ??至此，本題可以分解為兩個(gè)小問(wèn)題。

? ? ? ??第一個(gè)問(wèn)題是把成對(duì)的b、y離子分別找出來(lái)。我認(rèn)為，成對(duì)的b、y離子質(zhì)量之和等于多肽的總質(zhì)量，所以我把每個(gè)離子的質(zhì)量取出來(lái)（實(shí)際只需取前半部分就夠了）依次與其他離子相加，和與多肽總質(zhì)量相減，差值最小的肯定是成對(duì)的離子。這樣做只能保證成對(duì)，但無(wú)法分辨哪個(gè)是b離子，哪個(gè)是y離子。

? ? ? ??第二個(gè)問(wèn)題是前后兩離子相減，得到對(duì)應(yīng)殘基。這里我用后一對(duì)離子中較小的那個(gè)減去前一對(duì)離子中較小的那個(gè)，不難想到，如果得到的差值可以對(duì)應(yīng)一個(gè)殘基，那這兩個(gè)離子均為b離子或均為y離子；如果得到的差不是殘基，那么這兩個(gè)離子一個(gè)為b離子，一個(gè)為y離子。我統(tǒng)一把后一對(duì)離子交換位置，再將離子對(duì)列表重新排序。重復(fù)這個(gè)過(guò)程，就能得到多肽序列t。

?

代碼

monoisotopic mass table.txt文件內(nèi)容：

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