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 "ajustable accidentada" captura la intuición de que tanto el tamaño general del paisaje como la cantidad de sus "colinas y valles" locales se pueden ajustar mediante cambios en sus dos parámetros, y , siendo la longitud de una cadena de evolución y determinando el nivel de accidentada del paisaje. ${\displaystyle N}$ ${\displaystyle K}$ ${\displaystyle N}$ ${\displaystyle K}$

El modelo NK ha encontrado aplicación 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 fue adoptado en la teoría organizacional , donde se utiliza para describir la forma en que un agente puede buscar en un paisaje manipulando varias características de sí mismo. Por ejemplo, un agente puede ser una organización , las colinas y los valles representan ganancias (o cambios en las mismas), y el movimiento en el paisaje requiere decisiones organizacionales (como agregar líneas de productos o alterar la estructura organizacional), que tienden a interactuar entre sí y afectar las ganancias de una manera compleja. ^[2]

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

Una de las razones por las que el modelo ha atraído una amplia atención en la optimización es que es un ejemplo particularmente simple de un problema llamado 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 local. Esto tiene consecuencias para el estudio de la evolución abierta.

Ejemplo prototípico: aptitud del plásmido

Un plásmido es un pequeño círculo de ADN dentro de ciertas células que puede replicarse independientemente de sus células hospedadoras. 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...). Luego, el plásmido se modela mediante una cadena binaria con longitud N , por lo que la función de aptitud es . ${\displaystyle F:\{0,1\}^{N}\to \mathbb {R} }$

El modelo más simple tendría los genes sin interactuar entre sí, y así obtenemos donde cada uno denota la contribución a la aptitud del gen en la ubicación . $${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1})+f_{2}(S_{2})+\cdots +f_{N}(S_{N})}$$ ${\displaystyle f_{i}(S_{i})}$ ${\displaystyle S_{i}}$ ${\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, lo que da Por ejemplo, cuando K = 1 y N = 5 , $${\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})}$$

${\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 K, N finitos arbitrarios, así como también al permitir una definición arbitraria de adyacencia de genes (los genes no necesariamente se encuentran en un círculo o en un segmento de línea).

Definición matemática

El modelo NK define un espacio de fase combinatorio , que consiste en cada cadena (seleccionada de un alfabeto dado) de longitud . 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 . ${\displaystyle N}$

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 es la suma de las contribuciones de cada locus en la cadena: ${\displaystyle S}$ ${\displaystyle f_{i}(S)}$

${\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 otros locus: ${\displaystyle K}$

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

donde es el índice del vecino n° del lugar geométrico . ${\displaystyle k_{ij}}$ ${\displaystyle j}$ ${\displaystyle i}$

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

Visualización de dos dimensiones de un panorama de aptitud de NK. Las flechas representan diversas rutas mutacionales que la población podría seguir mientras evoluciona en el panorama de aptitud

Ejemplo: los modelos de vidrio espín

El modelo de Ising 1D del vidrio de espín se escribe habitualmente como donde es el hamiltoniano, que puede considerarse como energía. $${\displaystyle H=-\sum _{i=1}^{N}J_{i,i+1}S_{i}S_{i+1}-\mu \sum _{i=1}^{N}h_{i}S_{i}}$$ ${\displaystyle H}$

Podemos reformularlo como un caso especial del modelo NK con K=1 : definiendo En general, el modelo de Ising m-dimensional en una cuadrícula cuadrada es un modelo NK con . $${\displaystyle H=F(S)=\sum _{i,j}f_{i,j}(S_{i},S_{j})}$$ $${\displaystyle f_{i}(S_{i},S_{i+1})=-J_{i,i+1}S_{i}S_{i+1}-\mu h_{i}S_{i}}$$ ${\displaystyle \{1,2,...,n\}^{m}}$ ${\displaystyle N=n^{m},K=m}$

Dado que K mide aproximadamente la "rugosidad" del panorama de aptitud (ver más abajo), vemos que a medida que aumenta la dimensión del modelo de Ising, también aumenta su robustez.

Cuando , este es el modelo de Edwards-Anderson, que es exactamente solucionable. ${\displaystyle \mu =0}$

El modelo de Sherrington-Kirkpatrick generaliza el modelo de Ising al permitir que todos los pares posibles de espines interactúen (en lugar de un gráfico de cuadrícula , utilice el gráfico completo ), por lo que también es un modelo NK con . ${\displaystyle K=N-1}$

Al permitir que todas las posibles subsecuencias de espines interactúen, en lugar de simplemente pares, obtenemos el modelo de rango infinito, que también es un modelo NK con . ${\displaystyle K=N-1}$

Topología ajustable

Ilustración de la topología ajustable en el modelo NK. Los nodos son cadenas binarias individuales, las aristas conectan cadenas con una distancia de Hamming de exactamente uno. (izquierda) N = 5, K = 0. (centro) N = 5, K = 1. (derecha) N = 5, K = 2. El color de un nodo indica su aptitud; los valores más rojos tienen una aptitud más alta. La incrustación del hipercubo se elige de modo que el máximo de aptitud esté en el centro. Observe que el paisaje K = 0 parece más suave que los casos con K más alto.

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

Variaciones con espacios neutros

El modelo NK desnudo no admite el fenómeno del espacio neutral , es decir, conjuntos de genomas conectados por mutaciones individuales que tienen el mismo valor de aptitud. Se han propuesto dos adaptaciones para incluir esta estructura biológicamente importante . El modelo NKP introduce un parámetro : una proporción de las contribuciones de aptitud se establece en cero, de modo que las contribuciones de varios motivos genéticos son degeneradas ^{[ cita requerida ]} . El modelo NKQ introduce un parámetro e impone una discretización en los posibles valores de contribución de aptitud de modo que cada contribución toma uno de los valores posibles, introduciendo nuevamente la degeneración en las contribuciones de algunos motivos genéticos ^{[ cita requerida ]} . El modelo NK desnudo corresponde a los casos y bajo estas parametrizaciones. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle 2^{K}}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle P=0}$ ${\displaystyle Q=\infty }$

Resultados conocidos

En 1991, Weinberger publicó un análisis detallado ^[7] del caso en el que y las contribuciones de aptitud se eligen aleatoriamente. Su estimación analítica del número de óptimos locales se demostró más tarde que era errónea ^{[ cita requerida ]} . 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 cuerda se distribuye normalmente con una media de aproximadamente ${\displaystyle 1<<k\leq N}$

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

y una varianza de aproximadamente

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

Aplicaciones

El modelo NK ha encontrado uso en muchos campos, incluido 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 .

Referencias

1. Boroomand, Amin; Smaldino, Paul E. (2023). "El sesgo de superioridad y el ruido de comunicación pueden mejorar la resolución colectiva de problemas". Revista de sociedades artificiales y simulación social . 26 (3). doi : 10.18564/jasss.5154 .
2. Levinthal, DA (1997). "Adaptación en paisajes accidentados". Management Science . 43 (7): 934–950. doi :10.1287/mnsc.43.7.934.
3. Kauffman, S.; Levin, S. (1987). "Hacia una teoría general de los paseos adaptativos en paisajes accidentados". Revista de biología teórica . 128 (1): 11–45. Bibcode :1987JThBi.128...11K. doi :10.1016/s0022-5193(87)80029-2. PMID  3431131.
4. Kauffman, S.; Weinberger, E. (1989). "El modelo NK de paisajes accidentados de aptitud y su aplicación a la maduración de la respuesta inmune". Revista de biología teórica . 141 (2): 211–245. Bibcode :1989JThBi.141..211K. doi :10.1016/s0022-5193(89)80019-0. PMID  2632988.
5. Weinberger, E. (1996), "NP-completitud del modelo Nk de Kauffman, un paisaje de aptitud ajustable y robusto", Documento de trabajo del Instituto Santa Fe, 96-02-003.
6. Kaznatcheev, Artem (2019). "Complejidad computacional como una restricción última en la evolución". Genética . 212 (1): 245–265. doi :10.1534/genetics.119.302000. PMC 6499524 . PMID  30833289. 
7. Weinberger, Edward (15 de noviembre de 1991). "Propiedades locales del modelo Nk de Kauffman: un paisaje energético ajustable y accidentado". Physical Review A . 10. 44 (10): 6399–6413. Bibcode :1991PhRvA..44.6399W. doi :10.1103/physreva.44.6399. PMID  9905770.
8. Boroomand, A. y Smaldino, PE, 2021. Trabajo duro, toma de riesgos y diversidad en un modelo de resolución colectiva de problemas. Revista de sociedades artificiales y simulación social, 24(4).