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.

Efficient Mass Decomposition

Liptak, Zsuzsanna
2005

Abstract

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.
9781581139648
weighted strings; integer decomposition; coin change prob- lem; mass spectrometry
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/391094
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? ND
social impact