Modèle NK

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Le modèle NK est un modèle mathématique formulé par Stuart Kauffman et permettant de décrire un paysage adaptatif "rugueux adaptable". Cette "rugosité" suppose que, à la fois la taille globale du paysage et le nombre de "pics" et "vallées" locales peuvent être ajustés via des changements dans ses deux paramètres et définis plus bas. Le modèle NK a des applications dans une grande variété de domaines, dont l'étude théorique de la biologie évolutive, l'immunologie, l'optimisation combinatoire, l'évolution technologique et les systèmes complexes. Le modèle a été également adopté en théorie des organisations, où on l'utilise pour décrire la façon dont un agent (entité individuelle ou collective comme un organisme ou un groupe) peut faire des recherches dans un paysage en manipulant plusieurs de ses caractéristiques. Par exemple, un agent peut être une organisation, les pics et les vallées représentent le profit (ou les changements de celui-ci), et le mouvement au sein du paysage nécessite des décisions organisationnelles (comme le fait d'ajouter des lignes de produit ou de modifier la structure organisationnelle), qui tendent à interagir entre elles et affecter le profit d'une manière complexe[1].

Une première version du modèle a été présentée par Kauffman et Levin et 1987[2], qui considérait seulement les paysages les plus lisses () et les plus rugueux (). Le modèle sous sa forme actuelle est apparu la première fois dans la publication de Kauffman et Weinberger de 1989[3].

L'une des raisons pour lesquelles le modèle a attiré l'attention de la part de la communauté scientifique en optimisation est qu'il s'agit d'un exemple particulièrement simple d'un problème dit NP-complet[4].

Détails mathématiques[modifier | modifier le code]

Visualisation en 2D d'un paysage adaptatif NK. Les flèches représentent divers chemins mutationnels que la population est capable de suivre lors de son évolution dans le paysage adaptatif.

Le modèle NK définit un espace des phases combinatoire, dans lequel chaque chaîne de caractères (choisie à partir d'un alphabet donné) de longueur . Pour chaque chaîne dans cet espace de recherche, une valeur scalaire (appelée fonction de fitness) est définie. Si une distance métrique est définie entre les chaînes, la structure résultante constitue un paysage.

Les valeurs de fitness sont définies selon une incarnation spécifique du modèle, mais la caractéristique-clé du modèle NK est que la fitness d'une chaîne donnée correspond à la somme des contributions de chaque locus dans la chaîne :

et la contribution de chaque locus en général dépend de la valeur des autre loci :

où les correspondent aux autres loci dont dépend la fitness des .

Ainsi, la fonction de fitness est une cartographie entre des chaînes de longueur K+1 et des scalaires, ce que Weinberger a appelé plus tard les contributions à la fitness. De telles contributions à la fitness sont souvent choisies de façon aléatoire à partir d'une certaine distribution de probabilité spécifique.

En 1991[5], Weinberger a publié une analyse détaillée du cas où et les contributions à la fitness sont choisies aléatoirement. Son estimation analytique du nombre d'optima locaux s'est par la suite révélée imparfaite. Cependant, des expériences numériques incluses dans l'analyse de Weinberger sont en faveur de son résultat analytique selon lequel la fitness attendue d'une chaîne suit une distribution normale avec une moyenne approximative de

et une variance approximative de

.

Exemple[modifier | modifier le code]

Illustration d'une topologie ajustable dans le modèle NK. Les nœuds correspondent à des chaînes individuelles binaires, et les arêtes les connectent par une distance de Hamming de valeur exacte 1. Gauche : N = 5, K = 0 ; Centre : N = 5, K = 1 ; Droite : N = 5, K = 2. La couleur d'un nœud indique sa fitness, avec des valeurs plus vers le rouge ayant une fitness plus forte. Le plongement de l'hypercube est choisi de telle sorte que la valeur maximale de fitness est au centre. Noter que le paysage où K = 0 apparaît plus lisse que les cas où K est plus élevé.

Par souci de simplicité et de compréhension, on va travailler dans cet exemple avec des chaînes binaires. On considère un modèle NK avec N = 5 et K = 1. Ici, la fitness d'une chaîne est donnée par la somme des contributions à la fitness individuelles de chacun des 5 loci. Chaque contribution à la fitness dépend de la valeur du locus local ainsi que d'une autre. On va utiliser la convention selon laquelle , de façon que chaque locus est affecté par son voisin, ainsi que pour la cyclicité. Si l'on choisit par exemple les fonctions de fitness f(0, 0) = 0, f(1, 0) = 1, f(1, 0) = 2 et f(1, 1) = 0, les valeurs de fitness des deux exemples de chaînes se calculent comme suit :

Topologie ajustable[modifier | modifier le code]

La valeur de K contrôle le degré d'épistasie dans le modèle NK, ou bien à quel point les autres loci affectent la contribution à la fitness d'un locus donné. Avec K = 0, la fitness d'une chaîne donnée est une somme simple des contributions individuelles des loci : pour des fonctions de fitness non triviales, on a la présence d'un optimum global facile à localiser (le génome de tous les 0 si f(0) > f(1), ou de tous les 1 si f(1) > f(0)). Pour K non nul, la fitness d'une chaîne est la somme des fitness des sous-chaînes, qui peuvent interagir pour frustrer le système (voir la façon dont on obtient la fitness optimale dans l'exemple ci-dessus). Augmenter la valeur de K augmente ainsi la rugosité du paysage adaptatif.

Variations dans les espaces neutres[modifier | modifier le code]

Le modèle NK de base ne supporte pas le phénomène d'espace neutre, c'est-à-dire les groupes de génomes connectés par des mutations simples ayant la même valeur de fitness. Deux adaptations ont été proposées pour inclure cette structure biologiquement importante :

  • le modèle NKP introduit un paramètre  : une proportion des contributions à la fitness est mis à zéro, de sorte que les contributions de plusieurs motifs génétiques dégénèrent ;
  • le modèle NKQ introduit un paramètre et renforce une discrétisation sur les valeurs possibles de contribution à la fitness de sorte que chaque contribution prend l'une des valeurs possibles de , introduisant de nouveau une dégénérescence dans les contributions à partir de certains motifs génétiques.

Le modèle NK de base correspond aux cas où et dans ces conditions de paramétrisation.

Applications[modifier | modifier le code]

Le modèle NK a trouvé son utilité dans de nombreux domaines, dont l'étude des verres de spin, l'épistasie et la pléiotropie en biologie évolutive, ainsi que l'optimisation combinatoire.

Voir aussi[modifier | modifier le code]

Notes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Daniel A. Levinthal, « Adaptation on Rugged Landscapes », Management Science, vol. 43, no 7,‎ , p. 934–950 (ISSN 0025-1909, DOI 10.1287/mnsc.43.7.934, lire en ligne, consulté le 25 octobre 2017)
  2. Stuart Kauffman et Simon Levin, « Towards a general theory of adaptive walks on rugged landscapes », Journal of Theoretical Biology, vol. 128, no 1,‎ , p. 11–45 (DOI 10.1016/S0022-5193(87)80029-2, lire en ligne, consulté le 25 octobre 2017)
  3. Stuart A. Kauffman et Edward D. Weinberger, « The NK model of rugged fitness landscapes and its application to maturation of the immune response », Journal of Theoretical Biology, vol. 141, no 2,‎ , p. 211–245 (DOI 10.1016/S0022-5193(89)80019-0, lire en ligne, consulté le 25 octobre 2017)
  4. Yong Gao et Joseph Culberson, « An Analysis of Phase Transition in NK Landscapes », J. Artif. Int. Res., vol. 17, no 1,‎ , p. 309–332 (ISSN 1076-9757, lire en ligne, consulté le 25 octobre 2017)
  5. Edward D. Weinberger, « Local properties of Kauffman's N-k model: A tunably rugged energy landscape », Physical Review A, vol. 44, no 10,‎ , p. 6399–6413 (DOI 10.1103/PhysRevA.44.6399, lire en ligne, consulté le 25 octobre 2017)