I want to count the number of possible linear peptides of different lengths of a given mass. I have tried a branch and bound approach which works for small numbers but it unexpectedly stops when length of peptide becomes 6 or more.
So, I'm looking for an efficient algorithm or any suggestion you think useful.
I've attached my python code.
That's the money changing problem.
It has already been used for finding the atomic composition of proteins (the work of S. Bocker) and the composition of complexes in terms of proteins (the works of F. Cazals).
Some links :
Decomp-from interpreting Mass Spectrometry peaks to solving the Money Changing Problem ; Sebastian Böcker, Zsuzsanna Lipták, Marcel Martin, Anton Pervukhin, and Henner Sudek; Bioinformatics, 24 (4): 591-593, 2008
Stoichiometry Determination for Mass-spectrometry Data:the Interval Case; D. Agarwal, N. Malod-Dognin and F. Cazals; Research report, 2012
For the software:
http://bibiserv.techfak.uni-bielefeld.de/decomp/
http://cgal.inria.fr/abs/addict/
Thanks Noël Malod-Dognin, but money changing problem gives: 'The minimum number of coins with denominations coins that changes money',
But i need all possible combination of coins, that changes money.
There is a need to tweak the money changing algo.... what i don't understand how!
The two papers/software that I listed will return all the solutions to the money changing problem (not only the one having smallest number of coins). Once you get all the solutions for your target mass, then you need to convert each solution into all the corresponding sequences, which are all the corresponding combinations.
The combinatorics for this problem is as follows. The number of sum formulas for a given total mass can be calculated by counting 'restricted partitions'. That is the number of ways to write the total mass as a sum with each summand a weight of an amino acid. For each such sum formula, the number of isomers is the 'multinomial coefficient'.
I took the liberty to write a small program to count these values, and enumerate the actual sum formulas and also the actual isomers. The program is written in a specialised programming language called GAP, because GAP already knows about combinatorics where Python does not.
Of course, the number of peptides for a given total mass, without any additional constraints, grows quite quickly:
# List([200,300..1200], tm -> [tm, NrIsomers(tm)]);
# -->
# tm count
# [ [ 200, 8 ],
# [ 300, 87 ],
# [ 400, 882 ],
# [ 500, 14599 ],
# [ 600, 183329 ],
# [ 700, 2741184 ],
# [ 800, 39575132 ],
# [ 900, 584340761 ],
# [ 1000, 8756135919 ],
# [ 1100, 131791563155 ],
# [ 1200, 1996626917844 ] ]
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Programming Languages
- Python