Comparing Spectra with the Spectral Convolution

https://rosalind.info/problems/conv/

ROSALIND | Comparing Spectra with the Spectral Convolution

Problem

A multiset is a generalization of the notion of set to include a collection of objects in which each object may occur more than once (the order in which objects are given is still unimportant). For a multiset SS, the multiplicity of an element xx is the number of times that xx occurs in the set; this multiplicity is denoted S(x)S(x). Note that every set is included in the definition of multiset.

The Minkowski sum of multisets S1S1 and S2S2 containing real numbers is the new multiset S1⊕S2S1⊕S2 formed by taking all possible sums s1+s2s1+s2 of an element s1s1 from S1S1 and an element s2s2 from S2S2. The Minkowski sum could be defined more concisely as S1⊕S2=s1+s2:s1∈S1,s2∈S2S1⊕S2=s1+s2:s1∈S1,s2∈S2, The Minkowski difference S1⊖S2S1⊖S2 is defined analogously by taking all possible differences s1−s2s1−s2.

If S1S1 and S2S2 represent simplified spectra taken from two peptides, then S1⊖S2S1⊖S2 is called the spectral convolution of S1S1 and S2S2. In this notation, the shared peaks count is represented by (S2⊖S1)(0)(S2⊖S1)(0), and the value of xx for which (S2⊖S1)(x)(S2⊖S1)(x) has the maximal value is the shift value maximizing the number of shared masses of S1S1 and S2S2.

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

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

Sample Dataset

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

Sample Output

3
85.03163

 

 이 문제는 S1과 S2의 민코프스키 차를 구해내고 그 민코프스키 차 중 가장 많이 나온 값의 횟수와 많이 나온 값을 구하는 문제이다. 민코프스키 차는 말그대로 S1의 모든 요소와 S2의 모든 요소를 각각 뺀 값들이다. 이를 알고 풀면 쉽게 풀 수 있다.

if __name__ == '__main__':
    with open(r'파일경로','r') as f:
        S=[]
        for i in f.readlines():
            S.append(list(map(float,i.rstrip().split())))
        
        S1=S[0]
        S2=S[1]

spectral_convolution = [round(i-j,5) for i in S1 for j in S2]
spectral_convolution_count = {s:spectral_convolution.count(s) for s in spectral_convolution}
spectral_convolution_count_sorted = sorted(spectral_convolution_count.items(),key=lambda item:item[1],reverse=True)
print(spectral_convolution_count_sorted[0][1])
print(spectral_convolution_count_sorted[0][0])