Recensement de codes circulaires

Il s'agit d'un problème d'énumération combinatoire efficace (ou très gros moyens de calcul) pour dénombrer (et lister, éventuellement) les ensembles de trils (trinucléotides ou trilettres) de A43 qui sont des codes circulaires, puis parmi ces ensembles, ceux qui sont maximaux, maximaux et autocomplémentaires, maximaux et C3, et (enfin) à la fois maximaux, autocomplémentaires et C3.

Pour cela, nous sommes équipés d'un test, le théorème “Letter diletter continued closed necklace” mais il y aurait 260-1 possibilités à étudier (la cardinalité de l'ensemble des parties de l'ensemble des trils après avoir écarté les quatre qui ne peuvent pas appartenir à un code circulaire, AAA, CCC, GGG, et TTT)! Il convient donc de les construire :

  • soit par accroissements, rajoutant un tril s'il est admissible et cessant l'exploration dès qu'un ensemble est maximale;
  • soit à partir des ensembles maximaux (si on les avait tous ce serait merveilleux, n'est-ce pas?).

Quelques observations :

  • Si on ne faisait les accroissement qu'à partir des tril Axy et multipliait le résultat par quatre? En effet, si l'on prend cet arbre et échange A et C ou A et G ou A et T on retrouvera la même chose que si l'on était parti de ces graines. Donc, on trouvera toujours un multiple de 4 pour chaque cas recensé. Ca se vérifie pour les quelques indications que nous avons
    • maximaux de cardinal 14 : 192 = 48*4 = 4 * 3 * 16;
    • codes circulaires de cardinal 5 : 3,568,212 = 892,053 * 4 = 4 * 3 * 297,351
    • codes circulaires de cardinal 7 : 141,639,780 = 35,409,945 * 4 = 4 * 5 * 7,081,989 = 4 * 3 * 5 * 2,360,663
  • Logiquement, je m'attendais à ce que, après division par 4, on trouve des multiples de 6 (les permutations des C,G, et T) mais vraisemblablement il y a des permutations qui donnent un ensemble identique à ce que donnent d'autres qu'il ne faut pas compter deux fois. Est-ce possible de les “anticiper” et corriger le compte par un calcul?

Tests du "collier continu fermé"

  • pour chaque tril pisi de l'ensemble, si pi (soit P(pisi), la rotation à gauche) ne doit pas appartenir à l'ensemble.
  • pour chaque paire de trils p1s1 et p2s2 de l'ensemble, l'ensemble ne soit pas contenir s1p2 et s2p1 (mais peut contenir l'un d'eux?)
  • pour chaque trois trils de l'ensemble, l'ensemble doit ne pas contenir au moins un de s1p2, s2p3, s3p1.
  • enfin, pour chaque 4 trils de l'ensemble, il doit ne pas contenir au moins un de : s1p2, s2p3, s3p4, s4p1

Autres Exclusions d'Office

Nous avons déjà noté les quatre trils qui ne peuvent pas appartenir à un code circulaire, AAA, CCC, GGG, et TTT – ils sont leurs propres rotations à gauche. Notons aussi que puisque R(l1l2l3) = R(l2l3l1), R(R(l1l2l3) )

 
m1ilc/bioinfo_projet.txt · Dernière modification: 2010/03/23 13:34 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki