Login Logged in as anonymous / My BiBiServ / Logout
Reset Session
Authors: A. Pervukhin, M. Martin, H. Sudek

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.

built on June 25 2015 (5:acdba33c028d)