【ROSALIND】【练Python，学生信】54 谱卷积与质谱结果比较

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

题目：

谱卷积与质谱结果比较（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个正实数。

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的最大重数，以及使(S1⊖S2)(x)最大的x的绝对值（如果有多个结果，返回一个即可）。

测试数据

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

生物学背景

       如果我们手里有两次质谱的结果，如何确定这两次的样本是否来自同一蛋白呢？我们需要有指标来衡量不同质谱结果之间的相似性。

       最简单的方法是数一下两个结果中相同的峰的数量，即共有峰数（shared peaks count）。如果我们把原谱图简化为只有质量的简化谱（simplified spectra），就是计算同时出现在两个谱中质量的数量。但这种方法有严重的问题：如果有两条多肽，一条是另一条的子序列，那么两个多肽得到的谱图应该非常类似，但峰值却会发生偏移，使重合的峰数非常少。只有将其中一个谱向左或向右偏移一定位置才能使两个谱图最大程度地重合。在简化谱中情况也是一样，需要给其中一个谱的每个元素都加上某个值，才能使两个谱最大程度地匹配。

数学背景

       多重集（multiset）是集合概念的推广，普通的集合（set）中每个值只能出现一次，而多重集中每个元素可以出现多次（顺序不重要）。对于一个多重集S，其元素x的重度（multiplicity）是x在S中出现的次数，表示为S(x)。

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

       相应的，S1⊖S2的计算方法为从S1和S2中取所有可能的值相减，表示为S1⊖S2=s1-s2 : s1∈S1,s2∈S2。

       如果S1和S2分别是两个多肽的简化谱，S1⊖S2被称作S1和S2的谱卷积（spectral convolution）。共有的峰值数由（S2⊖S1）（0）表示，这道题的目的就是找一个偏移值x，使（S2⊖S1）（x）具有最大值，也就是使S1和S2中具有最多的相同质量。

思路

       这道题的题目对我来说有点绕，但思路和代码却很简单。可以说只要读懂题，自然也就把代码写好了，在此不再赘述，请参考代码和注释。

代码