|
Attention:
Due to technical maintenance some tools might be unavailable. See maintenance information. 
|
|
|
|
|
|
Welcome to Decomp
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.Sebastian Böcker and Zsuzsanna Lipták
Efficient Mass Decomposition
In Proc. of the 2005 ACM Symposium on Applied Computing, ACM Press, 2005, pages 151-157 (download preprint as PDF).
Decomp and the associated web interface have been implemented by Anton Pervukhin (PhD student), Marcel Martin, and Henner Sudek (student assistants).
 |
 |
 |
 |
 |
 |
 |
 |
|
|
|