### Abstract

Bases of generators of motifs consisting of strings in which some positions can be occupied by a don’t care provide a useful conceptual tool for their description and a way to reduce the time and space involved in the discovery process.In the last few years, a few algorithms have been proposed for the extraction of a basis, building in large part on combinatorial properties of strings and their autocorrelations.Currently, the most efficient techniques for binary alphabets and quorum q = 2 require time quadratic in the length of the host string. The present paper explores properties of motif bases for quorum q ≥ 2, both with binary and general alphabets, by also showing that important results holding for quorum q = 2 cannot be extended to this, more general, case. Furthermore, the extraction of motifs in which a bound is set on the maximum allowed number of don’t cares is addressed, and suitable algorithms are proposed whose computational complexity depends on the fixed bound.

Lingua originale | English |
---|---|

pagine (da-a) | 94-103 |

Numero di pagine | 10 |

Rivista | Theoretical Computer Science |

Volume | 460 |

Stato di pubblicazione | Published - 2012 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Entra nei temi di ricerca di 'Extracting string motif bases for quorum higher than two'. Insieme formano una fingerprint unica.

## Cita questo

Rombo, S. E., & Rombo, S. E. (2012). Extracting string motif bases for quorum higher than two.

*Theoretical Computer Science*,*460*, 94-103.