Extracting string motif bases for quorum higher than two

Simona Ester Rombo, Simona E. Rombo

Risultato della ricerca: Article

13 Citazioni (Scopus)

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 originaleEnglish
pagine (da-a)94-103
Numero di pagine10
RivistaTheoretical Computer Science
Volume460
Stato di pubblicazionePublished - 2012

Fingerprint

Quorum
Strings
Autocorrelation
Binary
Computational complexity
Computational Complexity
Generator

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Extracting string motif bases for quorum higher than two. / Rombo, Simona Ester; Rombo, Simona E.

In: Theoretical Computer Science, Vol. 460, 2012, pag. 94-103.

Risultato della ricerca: Article

@article{295a97767853499397cb45859cb41490,
title = "Extracting string motif bases for quorum higher than two",
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.",
author = "Rombo, {Simona Ester} and Rombo, {Simona E.}",
year = "2012",
language = "English",
volume = "460",
pages = "94--103",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

TY - JOUR

T1 - Extracting string motif bases for quorum higher than two

AU - Rombo, Simona Ester

AU - Rombo, Simona E.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10447/65936

UR - http://www.sciencedirect.com/science/article/pii/S0304397512006032

M3 - Article

VL - 460

SP - 94

EP - 103

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -