6. Codes Circulaires

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.

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.

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^*.

L'ensemble A³₄ est-il un code comma-free?

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.

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.

L'ensemble A³₄ est-il un code circulaire?

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₁

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.

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.

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)

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.

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.