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

題目：

譜卷積與質(zhì)譜結(jié)果比較（Comparing Spectra with the Spectral Convolution）

Given: Two multisets of positive real numbers S1 and S2. The size of each multiset is at most 200.

所給：兩個多重集S1和S2，各包含不超過200個正實數(shù)。

Return: The largest multiplicity of S1?S2, as well as the absolute value of the number x maximizing (S1?S2)(x) (you may return any such value if multiple solutions exist).

需得：S1?S2的最大重數(shù)，以及使(S1?S2)(x)最大的x的絕對值（如果有多個結(jié)果，返回一個即可）。

?

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

186.07931 287.12699 548.20532 580.18077 681.22845 706.27446 782.27613 968.35544 968.35544

101.04768 158.06914 202.09536 318.09979 419.14747 463.17369

測試輸出

3

85.03163

?

生物學(xué)背景

? ? ? ?如果我們手里有兩次質(zhì)譜的結(jié)果，如何確定這兩次的樣本是否來自同一蛋白呢？我們需要有指標(biāo)來衡量不同質(zhì)譜結(jié)果之間的相似性。

? ? ? ?最簡單的方法是數(shù)一下兩個結(jié)果中相同的峰的數(shù)量，即共有峰數(shù)（shared peaks count）。如果我們把原譜圖簡化為只有質(zhì)量的簡化譜（simplified spectra），就是計算同時出現(xiàn)在兩個譜中質(zhì)量的數(shù)量。但這種方法有嚴(yán)重的問題：如果有兩條多肽，一條是另一條的子序列，那么兩個多肽得到的譜圖應(yīng)該非常類似，但峰值卻會發(fā)生偏移，使重合的峰數(shù)非常少。只有將其中一個譜向左或向右偏移一定位置才能使兩個譜圖最大程度地重合。在簡化譜中情況也是一樣，需要給其中一個譜的每個元素都加上某個值，才能使兩個譜最大程度地匹配。

?

數(shù)學(xué)背景

? ? ? ?多重集（multiset）是集合概念的推廣，普通的集合（set）中每個值只能出現(xiàn)一次，而多重集中每個元素可以出現(xiàn)多次（順序不重要）。對于一個多重集S，其元素x的重度（multiplicity）是x在S中出現(xiàn)的次數(shù)，表示為S(x)。

? ? ? ?S1⊕S2（即閔可夫斯基和，Minkowski sum）的計算方法為從S1和S2中取所有可能的值相加，表示為S1⊕S2=s1+s2 : s1∈S1,s2∈S2。

? ? ? ?相應(yīng)的，S1?S2的計算方法為從S1和S2中取所有可能的值相減，表示為S1?S2=s1-s2 : s1∈S1,s2∈S2。

? ? ? ?如果S1和S2分別是兩個多肽的簡化譜，S1?S2被稱作S1和S2的譜卷積（spectral convolution）。共有的峰值數(shù)由（S2?S1）（0）表示，這道題的目的就是找一個偏移值x，使（S2?S1）（x）具有最大值，也就是使S1和S2中具有最多的相同質(zhì)量。

?

思路

? ? ? ?這道題的題目對我來說有點繞，但思路和代碼卻很簡單。可以說只要讀懂題，自然也就把代碼寫好了，在此不再贅述，請參考代碼和注釋。

?

代碼