Extracting string motif bases for quorum higher than two

作者：Rombo Simona E^*

来源：Theoretical Computer Science, 2012, 460: 94-103.

DOI：10.1016/j.tcs.2012.06.021

Bases of generators of motifs consisting of strings in which some positions can be occupied by a don%26apos;t care provide a useful conceptual tool for their description and a way to reduce the time and space involved in the discovery process. %26lt;br%26gt;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. %26lt;br%26gt;The present paper explores properties of motif bases for quorum q %26gt;= 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%26apos;t cares is addressed, and suitable algorithms are proposed whose computational complexity depends on the fixed bound.

• 出版日期2012-11-16