Abstract. We study the Submass Finding Problem: Given a string s over a weighted alphabet, i.e., an alphabet Σ with a weight function μ : Σ → N, decide for an input mass M whether s has a substring whose weights sum up to M. If M is indeed a submass, then we want to find one or all occurrences of such substrings. We present efficient algorithms for both the decision and the search problem. Furthermore, our approach allows us to compute efficiently the number of different submasses of s. The main idea of our algorithms is to define appropriate polynomials such that we can determine the solution for the Submass Finding Prob- lem from the coefficients of the product of these polynomials. We obtain very efficient running times by using Fast Fourier Transform to compute this product. Our main algorithm for the decision problem runs in time O(μs log μs), where μs is the total mass of string s. Employing stan- dard methods for compressing sparse polynomials, this runtime can be viewed as O(σ(s) log2 σ(s)), where σ(s) denotes the number of different submasses of s. In this case, the runtime is independent of the size of the individual masses of characters.

Efficient Algorithms for Finding Submasses in Weighted Strings

Liptak, Zsuzsanna
2004

Abstract

Abstract. We study the Submass Finding Problem: Given a string s over a weighted alphabet, i.e., an alphabet Σ with a weight function μ : Σ → N, decide for an input mass M whether s has a substring whose weights sum up to M. If M is indeed a submass, then we want to find one or all occurrences of such substrings. We present efficient algorithms for both the decision and the search problem. Furthermore, our approach allows us to compute efficiently the number of different submasses of s. The main idea of our algorithms is to define appropriate polynomials such that we can determine the solution for the Submass Finding Prob- lem from the coefficients of the product of these polynomials. We obtain very efficient running times by using Fast Fourier Transform to compute this product. Our main algorithm for the decision problem runs in time O(μs log μs), where μs is the total mass of string s. Employing stan- dard methods for compressing sparse polynomials, this runtime can be viewed as O(σ(s) log2 σ(s)), where σ(s) denotes the number of different submasses of s. In this case, the runtime is independent of the size of the individual masses of characters.
9783540223412
Fast Fourier Transform, combinatorics, weighted strings, mass spectrometry, submass finding problem
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/391095
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact