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.

Rombo, S.E. (2012). Extracting string motif bases for quorum higher than two. THEORETICAL COMPUTER SCIENCE, 460, 94-103 [10.1016/j.tcs.2012.06.021].

Extracting string motif bases for quorum higher than two

ROMBO, Simona Ester
2012-01-01

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.
http://www.sciencedirect.com/science/article/pii/S0304397512006032
Rombo, S.E. (2012). Extracting string motif bases for quorum higher than two. THEORETICAL COMPUTER SCIENCE, 460, 94-103 [10.1016/j.tcs.2012.06.021].
File in questo prodotto:
File Dimensione Formato  
tcs12.pdf

Solo gestori archvio

Dimensione 245.71 kB
Formato Adobe PDF
245.71 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/10447/65936
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 11
social impact