Name
Abstract | ||
|---|---|---|
Repetition avoidance has been intensely studied since Thue's work in the early 1900's. In this paper, we consider another type of repetition, called pseudopower, inspired by the Watson-Crick complementarity property of DNA sequences. A DNA single strand can be viewed as a string over the four-letter alphabet {A,C,G, T}, wherein A is the complement of T, while C is the complement of G. Such a DNA single strand will bind to a reverse complement DNA single strand, called its Watson-Crick complement, to form a helical double-stranded DNA molecule. The Watson-Crick complement of a DNA strand is deducible from, and thus informationally equivalent to, the original strand. We use this fact to generalize the notion of the power of a word by relaxing the meaning of “sameness” to include the image through an antimorphic involution, the model of DNA Watson-Crick complementarity. Given a finite alphabet Σ, an antimorphic involution is a function &thgr; : Σ* → Σ* which is an involution, i.e., &thgr;2 equals the identity, and an antimorphism, i.e., &thgr;(uv) = &thgr;(v)&thgr;(u), for all u ∈ Σ*. For a positive integer k, we call a word w a pseudo-kth-power with respect to &thgr; if it can be written as w = u1 ... uk, where for 1 ≤ i, j ≤ k we have either ui = uj or ui = &thgr;(uj). The classical kth-power of a word is a special case of a pseudo-kth-power, where all the repeating units are identical. We first classify the alphabets Σ and the antimorphic involutions &thgr; for which there exist arbitrarily long pseudo-kth-power-free words. Then we present efficient algorithms to test whether a finite word w is pseudo-kth-power-free. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-14455-4_39 | Fundam. Inform. |
Keywords | Field | DocType |
Watson-Crick complementarity property,DNA single strand,long pseudo-kth-power-free word,DNA sequence,antimorphic involution,helical double-stranded DNA molecule,DNA Watson-Crick complementarity,Pseudopower Avoidance,original strand,DNA strand,finite word w | Complementarity (molecular biology),Discrete mathematics,Computer science,Watson,DNA computing | Journal |
Volume | Issue | ISBN |
114 | 1 | 3-642-14454-3 |
Citations | PageRank | References |
1 | 0.58 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehsan Chiniforooshan | 1 | 118 | 16.38 |
| Lila Kari | 2 | 1123 | 124.45 |
| Zhi Xu | 3 | 9 | 2.61 |