# Can the subset sum problem work with an undefined set?

To give a brief outline of my actual problem, I'm attempting to identify possible impurities in proteins. I have a theoretical mass and an experimental mass, and the difference between the two would in theory be caused by any impurities present in the proteins. Impurities could take the form of an amino acid insertion, an amino acid deletion, an amino acid substitution, or an amino acid modification (modifications can both add and subtract mass).

Every impurity can be associated to a known change in mass, so I want to use the subset sum problem to get all subsets of impurities that add up to the delta mass. My issue is that I'm working with an undefined set. I know what impurities I can have, but I don't know how many of each I can have.

Is it possible to get the subset sum problem to work with an undefined set such as this? Is there a better algorithm I could implement to solve the issue?

• I don't understand your problem. Can you formulate it using more abstract terms? – Yuval Filmus Jun 20 '18 at 21:11
• Given that you can both take away and add mass, there might be infinitely many possibilities. – Tom van der Zanden Jun 20 '18 at 21:22
• I'm confused. What is known? You know about the possible impurities. Do you know what the effect on change in mass of each possible impurity is? How accurately can you measure the total change in mass? Is measurement error an issue? Do you have data on the probability distribution of number of impurities, and number of each type? If not it would probably be useful to gather that. You probably need a prior on the space of possible impurity-combinations. – D.W. Jun 21 '18 at 3:24
• I think he has $m$ different impurities, where a single copy (molecule?) of the $i$th impurity has mass $x_i$, and is looking for a solution to a subset sum problem in which the target sum is an experimentally measured mass difference $d$, and the set contains the numbers $kx_i$ and $-kx_i$ for $1 \le i \le m$ and $k$ can take any positive integer value. That is, the set is infinite (not undefined). – j_random_hacker Jun 21 '18 at 11:45

## 1 Answer

If you only have extra impurities, then the DECOMP program described in the following paper will efficiently solve the problem -- even if you only have an approximate mass difference $d$ to work with:

DECOMP--from interpreting Mass Spectrometry peaks to solving the Money Changing Problem (Böcker S., Lipták Z., Martin M., Pervukhin A., Sudek H. 2008)

The paper cites earlier papers by the same authors that describe the underlying Round Robin algorithm -- a very nice and fast algorithm based on Frobenius numbers for solving a problem that people previously resorted to tables computed using brute-force to solve.

To deal with "negative impurities" (components that should be present but are absent from the experimental sample), I think your best option is to try all possible "missing mass" values $a$ in a small range that includes zero, and for each such value $a$, use DECOMP to solve two problems: One that finds all possible combinations of "missing" components that solves for $a$, and one that finds all possible combinations of "extra" components that solves for $d+a$. Every pair of (missing, extra) component multisets is then a solution for the chosen $a$.

Bear in mind that, if there is a subset of components that sums to zero, then there will be an infinite number of solutions, since it is always possible to add another copy of this component subset to a solution to get another valid solution.

• There will always be a subset that sums to zero, if I'm reading the problem right: add one lysine, subtract one lysine. Same for any other amino acid. – Draconis Jun 21 '18 at 14:56
• @Draconis: Right, "subset" wasn't quite right. I should have been more precise, but I couldn't think of a consise way to express "Let the weight of one unit of the $i$-th component be $x_i$. If there exists an integer multiplier $m_i$ for each component type $i$, such that at least one multiplier is nonzero and $\sum_{i=1}^{k}m_ix_i = 0$, then there will be an infinite number of solutions". – j_random_hacker Jun 21 '18 at 16:09