Suppose you are given a DNA fragment of mass 1897.27 Dalton and no other
information. What nucleotide combinations are there that lead to exactly this mass?
Decomp helps you solve this and similar problems efficiently.
Problems like this (referred to as mass decomposition problems) often arise in
mass spectrometry, where the only information left about DNA, protein, or other sample
fragments is their molecular masss.
Given the weighted alphabet A, B, C with weights 3, 5, 8, what are the
decompositions for weight 16? Shown are all three solutions: A2B2, A1B1C1, and C2.
The answer to the above question looks like this: There are two possible
nucleotide decompositions: - either 6 Adenines
- or 2 Cytosines, 1 Adenine, and 3 Guanines
In short notation, we write: A6 and C2A1G3. For a second example, see the figure
on the right. More generally, the set A, C, G, T in conjunction with the corresponding
molecular masses is called a weighted alphabet. Decomp can use predefined DNA and amino acid
alphabets, and of course arbitrary alphabets provided by you. Decomp can also be used to
solve the money-changing problem (also called coin change problem). Formally, the problem is
stated as follows: Given an ordered set of weights {a1 , ��� , ak} and a nonnegative query
mass M, find all solutions to M = a1c1 + a2c2 + ��� + akck where c1, ��� ,ck are nonnegative
integers.
