DNA Watson-Crick Complementarity in Computer Science.

详细信息   

• 作者：Seki ; Shinnosuke.
• 学历：Doctor
• 年：2010
• 关键词：Watson-Crick complementarity ; antimorphic involuti
• 毕业院校：The University of Western Ontario
• ISBN：9780494733974
• CBH：NR73397
• Country：Canada
• 语种：English
• FileSize：12155781
• Pages：383

文摘

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 &thetas；. Hence, we can formalize the above-mentioned equivalence by the equivalence between a word and its image under &thetas；. 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,&thetas；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 Wilfs theorem and the Lyndon-Schü；tzenberger 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|) &ndash； 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-Schü；tzenberger equation is of the form au,qu ＝bv,q vg w,qw , where &alpha；u, &thetas；u)) &isin； {u, &thetas；u)}&ell；, &beta； v, &thetas；v)) &isin； {v, &thetas； v)}n, and &gamma；w, &thetas； w)) &isin； {w, &thetas；w)} m for some &ell；, n, m &ge； 1. We ask the question of under what conditions on &ell；, n, m, this equation implies that u, v, w &isin； {t, &thetas；t)} ＋ for some word t. The strongest condition we obtained so far is &ell； &ge； 4, m, n &ge； 3.