Name
Abstract | ||
|---|---|---|
The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n(3)), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n(2) log n log vertical bar Sigma vertical bar) and O(vertical bar Sigma vertical bar n(2) log(2) n log log n), with Sigma denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences.The present paper describes an off-line algorithm for binary strings that takes O(n(2)) time. The algorithm does not need to resort to the FFT and yet its performance is optimal for finite Sigma. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1142/S0129054110007714 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Design and analysis of algorithms, pattern matching, motif discovery, irredundant motif, basis | Log-log plot,Discrete mathematics,Combinatorics,Binary strings,Motif (music),Fast Fourier transform,Landmark,Pattern matching,Mathematics,Alphabet | Journal |
Volume | Issue | ISSN |
21 | 6 | 0129-0541 |
Citations | PageRank | References |
2 | 0.39 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alberto Apostolico | 1 | 1441 | 182.20 |
| Claudia Tagliacollo | 2 | 19 | 1.99 |