[[Codes Circulaires]]
 
Piste: » Codes Circulaires
Table des matières

Codes Circulaires

Notre projet BioInfo est (ou était) de développer des algorithmes efficaces pour une recherche combinatoire. Il nous est donné un alphabet de soixante symboles (64 mais dont 4 vite exclus pour impossibilité de respecter les contraintes) et des contraintes à vérifier pour des sous-ensembles de ces symboles, pour trouver tous les sous-ensembles vérifiant ces contraintes (et combien existent par cardinalité, combien ont certaines autres propriétés) ce qui paraitrait donner 260-1 possibilités!

Or, il y a beaucoup moins, car on peut segmenter l'ensemble en vingt “familles” de trois symboles, sachant que au plus un des trois membres d'une famille peut être présent dans un sous-ensemble satisfaisant les contraintes. Cela nous laisse néanmoins un gros espace de recherche, 420-1 cas à évaluer.1) Si l'on se contente de rechercher seulement les petits ensembles, de deux, trois ou quatre symboles, par exemple, c'est relativement faisable. Le tableau suivant décrit les espaces de recherche par taille (longueur) des ensembles. Pour les ensemble de trois symboles, exemple, il y a Combi(20,3) possibilités pour le choix des trois “familles” qui seront présentes, et trois choix par famille du membre qui représentera la famille. En général, il y a
Combi(20, k)*3k
possibilités pour des ensembles de cardinalité k.

Les dernières colonnes donnent une indication des besoins mémoire si l'on doit stocker tous les cas pour une cardinalité donné, et stocker ça plus la même info pour la cardinalité précédente (-1), ce qui correspond aux besoins pour un algorithme incrémental, procédant par test et rajout (si satisfaction des contraintes) d'éléments aux ensembles plus petits. La taille (25 octets) de la description d'un ensemble est arbitraire mais même en réduisant à un quart d'octet (par un facteur de 100) on aura besoin de 3 pica-octets (et probablement plus, 7-8 pica-octets) pour les ensembles de cardinalité 16-20. D'un autre côté, les ensembles maximaux (auxquels on ne peut plus trouver un entrant satisfaisant les contraintes) limiteront la croissance, mais seulement à partir des ensembles de cardinalité 14 (nous a-t-on indiqué) et seulement si l'on peut se les rappeler. Faut-il abandonner la stratégie incrémentale? Tester en profondeur d'abord?

Longueur Combi(20, longueur) 3**longueur Possibilités Dont CodeCirc. Mémoire @ 25 octets/CodeCirc Cumul pour 2 générations
1 20 3 60 60 1 500
2 190 9 1 710 1 704 42 750
3 1 140 27 30 780 30 432 769 500 812 250
4 4 845 81 392 445 9 811 125 10 580 625
5 15 504 243 3 767 472 94 186 800 103 997 925
6 38 760 729 28 256 040 706 401 000 800 587 800
7 77 520 2 187 169 536 240 141 639 780 4 238 406 000 4 944 807 000
8 125 970 6 561 826 489 170 20 662 229 250 24 900 635 250
9 167 960 19 683 3 305 956 680 82 648 917 000 103 311 146 250
10 184 756 59 049 10 909 657 044 272 741 426 100 355 390 343 100
11 167 960 177 147 29 753 610 120 743 840 253 000 1 016 581 679 100
12 125 970 531 441 66 945 622 770 1 673 640 569 250 2 417 480 822 250
13 77 520 1 594 323 123 591 918 960 3 089 797 974 000 4 763 438 543 250
14 38 760 4 782 969 185 387 878 440 4 634 696 961 000 7 724 494 935 000
15 15 504 14 348 907 222 465 454 128 5 561 636 353 200 10 196 333 314 200
16 4 845 43 046 721 208 561 363 245 5 214 034 081 125 10 775 670 434 325
17 1 140 129 140 163 147 219 785 820 3 680 494 645 500 8 894 528 726 625
18 190 387 420 489 73 609 892 910 1 840 247 322 750 5 520 741 968 250
19 20 1 162 261 467 23 245 229 340 581 130 733 500 2 421 378 056 250
20 1 3 486 784 401 3 486 784 401 87 169 610 025 668 300 343 525

Données et Règles (Conjecture?)

Il s'agit

  • d'un ensemble de 64 composés, chaque composé comprenant trois symboles tirés d'un ensemble de quatre symboles, avec doublons admis
  • des sous-ensembles de ces 64 composés qui vérifient quatre tests sur les symboles de leurs éléments
    • si s1-s2-s3 est dans l'ensemble, s2-s3-s1 ne l'est pas, ni s3-s1-s2 2)
    • des contraintes similaire avec des chainages décalées avec deux ou trois éléments de l'ensemble (FIXME : à clarifier).
  • de trouver combien il existe d'ensembles de chaque cardinalité vérifiant ces tests, et quelques autres éventuellement.

Comment Procéder?

Bonne question. A suivre. Les vitesses des programmes pour trouver les solution varient en vitesse de plusieurs ordres de grandeur : longueurs de 1 à 5 en moins d'une seconde à quelques minutes. Il sera intéressant d'apprendre (si on pourra) les sources de ces écarts.

Les Trils Possbles

Notons que pour notre A43, il y a

4 triplets d'un seule symbole : AAA CCC GGG TTT on ne les veux pas, ils forment des colliers.
4 triplets de trois symboles distinctes ACG ACT AGT et CGT Facile à générer (boucle externe d'ommission, interne de commission).
4 triplets de trois symboles distinctes AGC ATC ATG et CTG idem, mais dans le désordre.
12 triplets deux symboles, avec l'un en double (combinaisons de 2 parmi 4 = 6, avec deux possibilités pour le symbole à doubler chaque fois). for (i=0;i<3;i++){
for (j=i+1;j<4;j++) {
l1 = alphabet[i];
l2 = alphabet[j];
}}
premier ={l1, l1, l2};
second={l1, l2, l2};

Les implications par groupe de rotation

Si [ l1 l2 l3 ] produit un collier avec [ x1 x2 x3 ], alors

  • soit [x2 x3 l1 ] est dans l'ensemble,
  • soit [l2 l3 x1 ] est dans l'ensemble.

Ca ne veut pas dire que les rotations [ l2 l3 l1 ] et [ l3 l1 l2 ] produisent des colliers :

  • le premier va engendrer
    • [x2 x3 l2 ]
    • [l3 l1 x1 ]
  • le second va engendrer
    • [x2 x3 l3 ]
    • [l1 l2 x1 ]

Analysons les deux premier colliers dans le cas d'un ensemble du seul élément x :

  • [x2 x3 l1 ]==[x1 x2 x3 ] ⇒ [x1 == x2 == x3 : un tel trinucléotide n'est pas un code circulaire, cas exclu donc.
  • [l2 l3 x1 ]==[x1 x2 x3 ] ⇔
    • x1 == l2
    • x2 == l3
    • x3 == x1

Donc, x1 == x3== l2 et x2 == l3. Quelles sont les implications pour nos autres cas? Est-ce encore possible que nos autres cas ne produisent pas de collier?

  • Nous devons tester pour égalité à [x1 x2 x3 ] les deux trils dérivés suivants : FIXME analyse non terminée et peut être fausse et incohérente
    • [x2 x3 l2 ]
    • [l3 l1 x1 ]
  • en ce qui concerne le premier :
    • x2 <> x1 : possible, sûr même.
    • et/ou x3 <> x2 : possible
    • et/ou l2 <> x2 : possible et → l2 <>
  • en ce qui concerne le second :
    • l3 <> x1 : oui car l3 == x2 <> x1
1) 4 pour tenir compte des cas où aucun membre d'une famille n'est présent
2) en fait, ça définit les familles de permutations circulaires, ou rotations
 
java/code_finder.txt · Dernière modification: 2010/05/04 20:51 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