Dna watson-crick complementarity in computer science

Genetic information is encoded over the four nucleotide alphabet {A, C, G, T} in the form of DNA helix (double-stranded structure). This structure consists of DNA strands with opposite orientation (called Watson and Crick strands), bonded via the Watson-Crick complementarity A-T, C-G. During DNA replication, each of these strands serves as a template for the reproduction of the complementary strand so as to produce two identical copies of the original DNA helix. Thus, we can say that the Watson and Crick strands are equivalent with respect to the information they encode. The Watson-Crick complementarity is mathematically modeled as an antimorphic involution t. Hence, we can formalize the above-mentioned equivalence by the equivalence between a word and its image under t. This generalization enables us to extend the notions of periodicity and power (repetition) to those of pseudo-periodicity and pseudo-power. We call any word in u{u,t(u)}* a pseudo-power of u. With the notion of pseudo-power, we extend two problems of significance which involve power of words, that is, the Fine and Wilf's theorem and the Lyndon-Schutzenberger equation. The first theorem answers the question of how long prefix a pseudo-power of u and that of v should share to imply that u and v are pseudo-powers of some common word. Onto the length of this prefix, we provide an upper bound 2 max(|u|, |v|) + min(|u|, |v|) – gcd(|u|, |v|), and later improve it slightly. We also investigate its lower bound by constructing words u, v which cannot be written as pseudo-powers of a common word, but some of whose pseudo-powers can share a prefix of length quite close to the upper bound. The extended Lyndon-Schutzenberger equation is of the form au,qu =bv,q vg w,qw , where α(u, t(u)) ∈ {u, t(u)}e, β( v, t(v)) ∈ {v, t( v)}n, and γ(w, t( w)) ∈ {w, t(w)} m for some e, n, m ≥ 1. We ask the question of under what conditions on e, n, m, this equation implies that u, v, w ∈ {t, t(t)} + for some word t. The strongest condition we obtained so far is e ≥ 4, m, n ≥ 3. Keywords: Watson-Crick complementarity, antimorphic involution, Fine and Wilf's theorem, Lyndon-Schutzenberger equation

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.