====== 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 **2⁶⁰-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, 4²⁰-1 cas à évaluer.((4 pour tenir compte des cas où aucun membre d'une famille n'est présent)) 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)*3^k \\ 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 ((en fait, ça définit les familles de permutations circulaires, ou rotations)) * 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 A₄³, 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 [ l₁ l₂ l₃ ] produit un collier avec [ x₁ x₂ x₃ ], alors * soit [x₂ x₃ l₁ ] est dans l'ensemble, * soit [l₂ l₃ x₁ ] est dans l'ensemble. Ca ne veut pas dire que les rotations [ l₂ l₃ l₁ ] et [ l₃ l₁ l₂ ] produisent des colliers : * le premier va engendrer * [x₂ x₃ l₂ ] * [l₃ l₁ x₁ ] * le second va engendrer * [x₂ x₃ l₃ ] * [l₁ l₂ x₁ ] Analysons les deux premier colliers dans le cas d'un ensemble du seul élément x : * [x₂ x₃ l₁ ]==[x₁ x₂ x₃ ] => [x₁ == x₂ == x₃ : un tel trinucléotide n'est pas un code circulaire, cas exclu donc. * [l₂ l₃ x₁ ]==[x₁ x₂ x₃ ] <=> * x₁ == l₂ * x₂ == l₃ * x₃ == x₁ Donc, x₁ == x₃== l₂ et x₂ == l₃. 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é à [x₁ x₂ x₃ ] les deux trils dérivés suivants : FIXME ** analyse non terminée et peut être fausse et incohérente ** * [x₂ x₃ l₂ ] * [l₃ l₁ x₁ ] * en ce qui concerne le premier : * x₂ <> x₁ : possible, sûr même. * et/ou x₃ <> x₂ : possible * et/ou l₂ <> x₂ : possible et -> l₂ <> * en ce qui concerne le second : * l₃ <> x₁ : oui car l₃ == x₂ <> x₁