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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.