Given a text x of length n, we study the problem of solving the k-difference problem for all the words, either with fixed or variable length, taken from the text itself. The result finds its application in pattern discovery in biosequences where over- or under-represented words are extracted from the input sequences. The proposed algorithm runs in amortized linear time per word. This improves the complexity obtained by applying well-known algorithms to each of the O(n) fixed length words or O(n(2)) variable length words in x by factor of k, root k log k, or root m log m, depending on the chosen algorithm. The space required is O(n) if we just count the occurrences, or O(n(2)) if we also store the positions. This second scenario can be used as the basis for other applications, such as searching gapped factors with mismatches or approximate pattern matching extended to any word.

k-difference matching in amortized linear time for all the words in a text

PIZZI, CINZIA
2009

Abstract

Given a text x of length n, we study the problem of solving the k-difference problem for all the words, either with fixed or variable length, taken from the text itself. The result finds its application in pattern discovery in biosequences where over- or under-represented words are extracted from the input sequences. The proposed algorithm runs in amortized linear time per word. This improves the complexity obtained by applying well-known algorithms to each of the O(n) fixed length words or O(n(2)) variable length words in x by factor of k, root k log k, or root m log m, depending on the chosen algorithm. The space required is O(n) if we just count the occurrences, or O(n(2)) if we also store the positions. This second scenario can be used as the basis for other applications, such as searching gapped factors with mismatches or approximate pattern matching extended to any word.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/11577/2384551
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact