Efficient Mass Decomposition

We study the problem of decomposing a positive integer M over a (fixed and finite) weighted alphabet Σ: We want to find non-negative integers ci such that M = c1a1+...+ckak, where the ai are the positive integer weights of the individual characters and |Σ| = k. We refer to the vector (c1,...,ck) as a witness (of M over Σ), and denote by γ(M) the number of distinct witnesses of M. We present a data structure of size O(ka1) that allows finding all witnesses of any query M in time O(ka1 ·γ(M)). To the best of our knowledge, this is the first algorithm for the problem with runtime independent of the size of the query M. Construction of the data structure requires O(ka1) time and constant additional space, and is very easy to implement. The problem is motivated by mass spectrometry experiments, where peaks need to be mapped to sample molecules whose mass they could represent. Our simulations show that the algorithm presented performs well on relevant applications.