====== 6. Codes Circulaires ====== ===== Définitions ===== ?? code :: un ensemble X de A⁺ est un code sur A si pour chaque x₁,...,x_n, x'₁,...,x'_m ∈ X, n,m ≥ 1, la condition x₁,...,x_n = x'₁,...,x'_m implique que n=m et x_i=x'_i pour i=1,...,n. !! ==== Exercice ==== L'ensemble A³₄ est-il un code? Oui : * x₁,...,x_n = x'₁,...,x'_m implique que n=m car tous les mots ont longueur 3. * => x_i=x'_i car ils arrivent aux mêmes positions (3*(i-1).."*(i-1+2) et les deux concaténations sont égales. ===== Définition ===== ?? code trinucléotide comma-free :: un code trinucléotide X ∈ A³₄ est comma-free (ou sans ponctuation) si pour chaque y ∈ X et u, v ∈ A^*₄ tels que uyv = x₁,...,x_n avec x₁,...,x_n ∈ X, n ≥ 1, alors u, v ∈ X^*. !! ==== Exercice ==== L'ensemble A³₄ est-il un code comma-free? ===== Définition ===== ?? code trinucléotide circulaire :: un code trinucléotide ∈ A³₄ est circulaire si pour chaque x₁,...,x_n, x'₁,...,x'_m ∈ X, n,m ≥ 1, p ∈ A^*₄, s ∈ A⁺₄, les conditions s x₂,...,x_np = x'₁,...,x'_m et x₁ = ps impliquent n=m, p=ε, et x_i=x'_i pour i=1,...,n. !! ==== Exercice ==== Donner une représentation graphique de cette définition. Tout mot construit avec X et écrit sur "un cercle" a au plus un factorisation avec X. ==== Exercice ==== L'ensemble A³₄ est-il un code circulaire? ==== Exercice ==== Quelles sont les deux classes de contraintes évidentes que doit vérifier un code trinucléotide pour être circulaire? Nécessaires mais pas suffisantes (d'ailleurs). * pas de trinucléotides avec des nucléotides identiques : {AAA, CCC, GGG, TTT} * pas de trinucléotides avec un de ses trinucléotides permutés (rotations) : * l₀ l₁ l₂ * l₁ l₂ l₀ * l₂ l₀ l₁ ===== Définition ===== ?? code trinucléotide circulaire maximal :: un code trinucléotide circulaire X ∈ A³₄ est maximal si pour chaque x ∈ A³₄ , X ∪ {x} n'est pas un code trinucléotide circulaire. !! ==== Exercice ==== Combien de mots (longueur) au maximum peut avoir un code trinucléotide circulaire? Etant donnée la première contrainte, il reste 64-4 trinucléotides candidats pour les codes circulaires. Mais la deuxième contrainte divise par trois, car on ne pourra pas avoir deux (ou trois) trinucléotides d'une même classe d'équivalence par rotation. Il a y 20 telles classes, 20 est la longueur maximale. ==== L'application complémentaire ==== C : A⁺₄ -> A⁺₄ est définie par C(A)=T, C(T)=A, C(C)=G, C(G)=C, et par C(uv) = C(v)C(u) pour tout u,v ∈ A⁺₄. Cette application est associée à la propriété double hélice d'ADN qui est complémentaire et antiparallèle (un brin de ADN chimiquement orienté dans la direction 5'-3' et l'autre brin d'ADN dans la direction opposée 3'-5'; Watson & Crick, 1953). Cette application C définie sur les mots est naturellement étendue aux ensembles de mots : un ensemble complémentaire de trinucléotides est obtenu en appliquant l'application complémentaire C à tous ses trinucléotides. Exemples * C(uv) = C(v) C(u) : * C(AAC) = C(C)C(AA) = C(C) C(A) C(A) = G T T * C(AAC) = C(AC)C(A) = C(C) C(A) C(A) = G T T * C(xyz) = C(yz)C(x) = C(z) C(y) C(x) = C(z) C(xy) ==== L'application permutée ==== P : A⁺₄ -> A⁺₄ permute circulairement chaque trinucléotide l₁ l₂ l₃ de la façon suivante * P(l₁ l₂ l₃) = l₂ l₃ l₁ * le k-ième itéré de P est noté P^k. Cette application définie sur les mots est naturellement étendue aux ensembles de mots : un ensemble permuté de trinucléotides est obtenu en appliquant l'application permutée P à tous ses trinucléotides. === Remarque === Deux trinucléotides u et v sont conjugués s'il existe 2 mots s et t tels que u=st et v =ts. Ainsi, si u et v satisfont P^k(u)=v pour un k donné, alors u et v sont conjugués.