# Does an algorithm exist for solving the change-making problem using a finite coin library of known size?

I'm currently working on implementing an algorithm to solve a real-world problem I'm encountering in a lab, but with little background in algorithms, I'm struggling to create an ideal solution.

I work in a protein lab and using a mass spectrometer I can get the mass of a protein of interest. Each protein is made up of a string of building blocks called amino acids, and each amino acid has a known mass. Additionally, each amino acid can posses one of about a dozen modification which can alter it's mass by a known amount, positively or negatively.

Using the total mass of the protein alone, I'm looking for a way to identify all possible combinations of amino acids and modifications that could potentially sum up to that protein's mass.

As an example, say we know the following:

• Protein mass: 12 Da
• Amino acid masses:
• A: 3 Da
• B: 6 Da
• C: 10 Da
• Modification masses:
• a: +2 Da

With this information, we can decompose the peptides mass into the sums of the following combinations (I may have missed some):

• AAAA
• AAB
• BB
• Ca

Obviously order of the building blocks can't be inferred from the mass alone, but the atomic makeup should be.

I've attempted to solve the problem by looking at it as a type of change-making problem, and implemented my first solution using the algorithm outlined by Bocker and Liptak in the following paper:

https://bio.informatik.uni-jena.de/bib2html/downloads/2005/BoeckerLiptak_EfficientMassDecomposition_ACMSAC_2005.pdf

The issue is that this algorithm calculates every possible combination of amino acids and modifications that sums to the peptide mass, which for larger peptides results in billions if not trillions of combinations over a runtime of hours if not days.

Bocker and Liptak use an infinite set of values to sum to the target peptide mass, whereas I believe that I can drastically shorten the runtime if I can use a finite library size. Say I know that I protein I'm analyzing normally has 3 As, 2 Bs, and 5 Cs, the idea I have is to restrict the calculations to only those combinations that involve the same number of amino acids plus or minus X. The number of modifications would be tied to the number of amino acids on a one to one basis.

Is there an algorithm for this sort of calculation? Please feel free to ask me to clarify anything because I know that it's a complicated problem.

Best!

• Lower bounds are easy: If you require at least $L_i$ copies of amino acid $i$, just subtract $L_i$ times that amino acid's mass from the original total, and remember to add $L_i$ back to the appropriate vector element at the end. Upper bounds $U_i$ might require using one of the "usual" DP algorithms instead. Let $f(x, i)$ be the smallest number of copies of amino acid $i$ needed to decompose the mass $x$ using amino acids $0, \dots, i$: compute it using $f(0, i) = 0$ and ... – j_random_hacker Jul 30 '18 at 19:45
• ... $f(x, i) = \text{if }f(x, i-1) < \infty\text{ then }0\text{ else if }f(x-m_i, i) < U_i\text{ then } f(x-m_i, i) + 1\text{ else }\infty$ when $x > 0$. – j_random_hacker Jul 30 '18 at 19:47
• Basically if $f(x ,i)$ is any finite value then it indicates that there is at least one valid solution for the mass $x$ using the first $i$ amino acid types. So if $M$ is your target mass and you have $k$ amino acid types, check that $f(M, k)$ is finite to ensure there is at least one solution. If so, you can find all of them by recursively backtracing through the DP matrix: Start at the $k$-th amino acid type with current mass $m=M$, and try whichever or both possible predecessor states ($f(x, i-1)$ and $f()$) are valid (finite-valued). – j_random_hacker Jul 30 '18 at 20:00
• Whoops, ran out of time on the edit... The second predecessor state should have been "$f(x-m_i, i)$", not "$f()$". – j_random_hacker Jul 30 '18 at 20:10
• This sounds like a knapsack instance, and I think @j_random_hacker gave you what you need to get going. Construct the DP matrix and backtrack in a way that suits you. – Pål GD Jul 31 '18 at 8:44