2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I don't understand your problem. Can you formulate it using more abstract terms? $\endgroup$
    – Yuval Filmus
    Commented Jun 20, 2018 at 21:11
  • $\begingroup$ Given that you can both take away and add mass, there might be infinitely many possibilities. $\endgroup$
    – Tom van der Zanden
    Commented Jun 20, 2018 at 21:22
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jun 21, 2018 at 3:24
  • $\begingroup$ 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). $\endgroup$
    – j_random_hacker
    Commented Jun 21, 2018 at 11:45

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Draconis
    Commented Jun 21, 2018 at 14:56
  • $\begingroup$ @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". $\endgroup$
    – j_random_hacker
    Commented Jun 21, 2018 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.