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):
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:
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.