Modelo NK

El modelo NK es un modelo matemático descrito por su inventor principal, Stuart Kauffman, como un paisaje de aptitud "ajustablemente accidentado" . La "ajustabilidad accidentada" captura la intuición de que tanto el tamaño general del paisaje como el número de sus "colinas y valles" locales pueden ajustarse mediante cambios en sus dos parámetros.${\displaystyle N}$y${\displaystyle K}$, con${\displaystyle N}$siendo la longitud de una cadena de evolución y${\displaystyle K}$determinar el grado de accidentado del paisaje.

El modelo NK se ha aplicado en una amplia variedad de campos, incluyendo el estudio teórico de la biología evolutiva , la inmunología , la optimización , la evolución tecnológica , la ciencia de equipos ^{[ 1 ]} y los sistemas complejos . El modelo también se adoptó en la teoría organizacional , donde se utiliza para describir la forma en que un agente puede explorar un entorno manipulando diversas características de sí mismo. Por ejemplo, un agente puede ser una organización , las colinas y los valles representan las ganancias (o sus cambios), y el movimiento en el entorno requiere decisiones organizacionales (como agregar líneas de productos o modificar la estructura organizacional), las cuales tienden a interactuar entre sí y afectar las ganancias de manera compleja. ^{[ 2 ]}

Una versión temprana del modelo, que consideraba solo los más suaves (${\displaystyle K=0}$) y los más resistentes (${\displaystyle K=N-1}$) paisajes, fue presentado en Kauffman y Levin (1987). ^{[ 3 ]} El modelo tal como se conoce actualmente apareció por primera vez en Kauffman y Weinberger (1989). ^{[ 4 ]}

Una de las razones por las que el modelo ha atraído tanta atención en optimización es que es una instancia particularmente simple de un problema denominado NP-completo ^{[ 5 ],} lo que significa que es difícil encontrar óptimos globales. Recientemente, se demostró que el modelo NK para K > 1 también es PLS-completo ^{[ 6 ]} , lo que significa que, en general, es difícil encontrar incluso óptimos de aptitud locales. Esto tiene consecuencias para el estudio de la evolución abierta .

Un plásmido es un pequeño círculo de ADN dentro de ciertas células que puede replicarse independientemente de sus células huésped. Supongamos que deseamos estudiar la aptitud de los plásmidos.

Para simplificar, modelamos un plásmido como un anillo de N genes posibles, siempre en el mismo orden, y cada uno puede tener dos estados posibles (activo o inactivo, tipo X o tipo Y, etc.). Entonces, el plásmido se modela mediante una cadena binaria de longitud N , y por lo tanto la función de aptitud es${\displaystyle F:\{0,1\}^{N}\to \mathbb {R} }$.

El modelo más simple implicaría que los genes no interactúan entre sí, y así obtenemos$${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1})+f_{2}(S_{2})+\cdots +f_{N}(S_{N})}$$donde cada${\displaystyle f_{i}(S_{i})}$denota la contribución a la aptitud del gen${\displaystyle S_{i}}$en la ubicación${\displaystyle i}$.

Para modelar la epistasis , introducimos otro factor K , el número de otros genes con los que interactúa un gen. Es razonable suponer que en un plásmido, dos genes interactúan si son adyacentes, dando así como$${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1},S_{2})+f_{2}(S_{2},S_{3})+\cdots +f_{N-1}(S_{N-1},S_{N})+f_{N}(S_{N},S_{1})}$$Por ejemplo, cuando K = 1 y N = 5 ,

${\displaystyle F(00101)=f_{1}(0,0)+f_{2}(0,1)+f_{3}(1,0)+f_{4}(0,1)+f_{5}(1,0)}$

El modelo NK generaliza esto al permitir valores arbitrarios y finitos de K y N, así como una definición arbitraria de la adyacencia de los genes (los genes no necesariamente se encuentran en un círculo o un segmento de línea).

El modelo NK define un espacio de fase combinatorio , que consiste en cada cadena (elegida de un alfabeto dado) de longitud${\displaystyle N}$Para cada cadena en este espacio de búsqueda, se define un valor escalar (llamado aptitud ). Si se define una métrica de distancia entre cadenas, la estructura resultante es un paisaje .

Los valores de aptitud se definen según la encarnación específica del modelo, pero la característica clave del modelo NK es que la aptitud de una cadena dada${\displaystyle S}$es la suma de las contribuciones de cada locus${\displaystyle f_{i}(S)}$en la cadena:

${\displaystyle F(S)=\sum _{i}{\tilde {f}}_{i}(S),}$

y la contribución de cada locus en general depende de su estado y del estado de${\displaystyle K}$otros loci,:

${\displaystyle {\tilde {f}}_{i}(S)=f_{i}(S_{i},S_{k_{i1}},\dots ,S_{k_{iK}}),}$

dónde${\displaystyle k_{ij}}$es el índice de la${\displaystyle j}$vecino del locus${\displaystyle i}$.

Por lo tanto, la función de aptitud${\displaystyle f_{i}}$es una correspondencia entre cadenas de longitud K  +  1 y escalares, que el trabajo posterior de Weinberger denomina "contribuciones de aptitud". Dichas contribuciones de aptitud suelen elegirse aleatoriamente a partir de alguna distribución de probabilidad especificada .

El valor de K controla el grado de epistasis en el modelo NK, o cuánto influyen otros loci en la contribución de aptitud de un locus dado. Con K = 0, la aptitud de una cadena dada es una simple suma de las contribuciones individuales de los loci: para funciones de aptitud no triviales, existe un óptimo global que es fácil de localizar (el genoma de todos 0 si f (0) > f (1), o todos 1 si f (1) > f (0)). Para K distinto de cero , la aptitud de una cadena es una suma de las aptitudes de las subcadenas, que pueden interactuar para frustrar el sistema (considere cómo lograr la aptitud óptima en el ejemplo anterior). Por lo tanto, aumentar K incrementa la complejidad del paisaje de aptitud.

En 1991, Weinberger publicó un análisis detallado ^{[ 7 ]} del caso en el que${\displaystyle 1<<k\leq N}$y las contribuciones de aptitud se eligen aleatoriamente. Posteriormente se demostró que su estimación analítica del número de óptimos locales era errónea . Sin embargo, los experimentos numéricos incluidos en el análisis de Weinberger respaldan su resultado analítico de que la aptitud esperada de una cadena se distribuye normalmente con una media de aproximadamente

${\displaystyle \mu +\sigma {\sqrt {{2\ln(k+1)} \over {k+1}}}}$

y una variación de aproximadamente

${\displaystyle {{(k+1)\sigma ^{2}} \over {N[k+1+2(k+2)\ln(k+1)]}}}$.

El modelo NK se ha utilizado en muchos campos, incluyendo el estudio de vidrios de espín , la resolución colectiva de problemas , ^{[ 8 ]} la epistasis y la pleiotropía en biología evolutiva y la optimización combinatoria .