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-01-01

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.
2005
9781581139648
weighted strings; integer decomposition; coin change prob- lem; mass spectrometry
File in questo prodotto:
File Dimensione Formato  
BoeckerLiptak_EfficientMassDecomposition_ACMSAC_2005.pdf

solo utenti autorizzati

Tipologia: Versione dell'editore
Licenza: Copyright dell'editore
Dimensione 943.53 kB
Formato Adobe PDF
943.53 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: https://hdl.handle.net/11562/391094
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? ND
social impact