446
13 L’ordinateur ` a ADN
nombre de variables. Plus il y a de variables, plus N doit ˆ etre grand pour repr´ esenter
tous les sommets et toutes les arˆ etes par des s´ equences diff´ erentes.
On met donc dans une ´ eprouvette une grande quantit´ e de chacune des chaˆ ınes d’ADN
codantes, sommets comme arˆ etes, et au bout d’un certain temps, tous les chemins
possibles sont form´ es avec une tr` es forte probabilit´ e. Il reste donc ` a faire des tests
pour voir si l’´ enonc´ e logique se v´ erifie.
La premi` ere ´ etape est la reformulation de l’´ enonc´ e sous la forme conjonctive normale,
c’est-` a-dire sous la forme
α = C 1 ∧ C 2 ∧ C 3 ∧ · · · ∧ C m
o` u tous les C i sont des propositions logiques n’utilisant que le ∨ et le ¬. Un th´ eor` eme de
logique assure qu’une telle conversion est possible pour n’importe quel ´ enonc´ e logique
utilisant des ET, des OU et des NON. Cela se fait `
a l’aide des r` egles suivantes :
1. Pour tous x 1 , x 2 , x 3 ,
x 1 ∧ (x 2 ∨ x 3 ) = (x 1 ∧ x 2 ) ∨ (x 1 ∧ x 3 ).
2. Pour tous x 1 , x 2 , x 3 ,
x 1 ∨ (x 2 ∧ x 3 ) = (x 1 ∨ x 2 ) ∧ (x 1 ∨ x 3 ).
3. Pour tous x 1 , x 2 ,
¬(x 1 ∨ x 2 ) = ¬x 1 ∧ ¬x 2 .
4. Pour tous x 1 , x 2 ,
¬(x 1 ∧ x 2 ) = ¬x 1 ∨ ¬x 2 .
Bien que la conversion soit possible, elle ne se fait pas toujours facilement. En effet,
les algorithmes connus pour ce type de conversion sont assez complexes et ne donnent
pas n´ ecessairement la forme conjonctive normale dans un d´ elai raisonnable. Cependant,
dans plusieurs probl` emes, l’´ enonc´ e est d´ ej` a sous forme conjonctive normale et ne n´ ecessite pas cette traduction laborieuse. Ainsi, dans le cas de l’exemple 13.44, il suffit de
choisir C 1 = x 1 ∨ x 2 et C 2 = ¬x 3 .
Pour satisfaire ` a un ´ enonc´ e de la forme C 1 ∧ · · · ∧ C m , on doit satisfaire `
a C 1 et on
doit satisfaire ` a C 2 et on doit satisfaire ` a · · · C m .
La conversion `
a la forme conjonctive normale sert ` a guider l’extraction de la solution.
On prend l’´ enonc´ e C 1 et on extrait de l’´ eprouvette toutes les chaˆ ınes qui correspondent
` a ces crit` eres. Dans notre exemple, C 1 = x 1 ∨ x 2 . Ceci veut dire qu’on extrait toutes les
chaˆ ınes o` u au moins une des deux variables x 1 et x 2 vaut 1.
Ceci peut se faire en extrayant en premier lieu toutes les chaˆ ınes o` u x 1 = 1. Pour
ce faire, on peut utiliser des techniques similaires `
a celles d’Adleman. En effet, on peut
mettre dans l’´ eprouvette de d´ epart (´ eprouvette A) des petites billes de fer auxquelles
sont attach´ ees des amorces constitu´ ees des compl´ ements des chaˆ ınes d’ADN repr´ esentant
13 L’ordinateur ` a ADN
nombre de variables. Plus il y a de variables, plus N doit ˆ etre grand pour repr´ esenter
tous les sommets et toutes les arˆ etes par des s´ equences diff´ erentes.
On met donc dans une ´ eprouvette une grande quantit´ e de chacune des chaˆ ınes d’ADN
codantes, sommets comme arˆ etes, et au bout d’un certain temps, tous les chemins
possibles sont form´ es avec une tr` es forte probabilit´ e. Il reste donc ` a faire des tests
pour voir si l’´ enonc´ e logique se v´ erifie.
La premi` ere ´ etape est la reformulation de l’´ enonc´ e sous la forme conjonctive normale,
c’est-` a-dire sous la forme
α = C 1 ∧ C 2 ∧ C 3 ∧ · · · ∧ C m
o` u tous les C i sont des propositions logiques n’utilisant que le ∨ et le ¬. Un th´ eor` eme de
logique assure qu’une telle conversion est possible pour n’importe quel ´ enonc´ e logique
utilisant des ET, des OU et des NON. Cela se fait `
a l’aide des r` egles suivantes :
1. Pour tous x 1 , x 2 , x 3 ,
x 1 ∧ (x 2 ∨ x 3 ) = (x 1 ∧ x 2 ) ∨ (x 1 ∧ x 3 ).
2. Pour tous x 1 , x 2 , x 3 ,
x 1 ∨ (x 2 ∧ x 3 ) = (x 1 ∨ x 2 ) ∧ (x 1 ∨ x 3 ).
3. Pour tous x 1 , x 2 ,
¬(x 1 ∨ x 2 ) = ¬x 1 ∧ ¬x 2 .
4. Pour tous x 1 , x 2 ,
¬(x 1 ∧ x 2 ) = ¬x 1 ∨ ¬x 2 .
Bien que la conversion soit possible, elle ne se fait pas toujours facilement. En effet,
les algorithmes connus pour ce type de conversion sont assez complexes et ne donnent
pas n´ ecessairement la forme conjonctive normale dans un d´ elai raisonnable. Cependant,
dans plusieurs probl` emes, l’´ enonc´ e est d´ ej` a sous forme conjonctive normale et ne n´ ecessite pas cette traduction laborieuse. Ainsi, dans le cas de l’exemple 13.44, il suffit de
choisir C 1 = x 1 ∨ x 2 et C 2 = ¬x 3 .
Pour satisfaire ` a un ´ enonc´ e de la forme C 1 ∧ · · · ∧ C m , on doit satisfaire `
a C 1 et on
doit satisfaire ` a C 2 et on doit satisfaire ` a · · · C m .
La conversion `
a la forme conjonctive normale sert ` a guider l’extraction de la solution.
On prend l’´ enonc´ e C 1 et on extrait de l’´ eprouvette toutes les chaˆ ınes qui correspondent
` a ces crit` eres. Dans notre exemple, C 1 = x 1 ∨ x 2 . Ceci veut dire qu’on extrait toutes les
chaˆ ınes o` u au moins une des deux variables x 1 et x 2 vaut 1.
Ceci peut se faire en extrayant en premier lieu toutes les chaˆ ınes o` u x 1 = 1. Pour
ce faire, on peut utiliser des techniques similaires `
a celles d’Adleman. En effet, on peut
mettre dans l’´ eprouvette de d´ epart (´ eprouvette A) des petites billes de fer auxquelles
sont attach´ ees des amorces constitu´ ees des compl´ ements des chaˆ ınes d’ADN repr´ esentant