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 |
Il s'agit
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.
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++){ |
Si [ l1 l2 l3 ] produit un collier avec [ x1 x2 x3 ], alors
Ca ne veut pas dire que les rotations [ l2 l3 l1 ] et [ l3 l1 l2 ] produisent des colliers :
Analysons les deux premier colliers dans le cas d'un ensemble du seul élément x :
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?