Modelo NK

Este artículo proporciona un contexto insuficiente para quienes no están familiarizados con el tema . Por favor, ayuda a mejorar el artículo por proporcionar más contexto para el lector . ( Abril de 2021 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

El modelo NK es un modelo matemático descrito por su inventor principal, Stuart Kauffman, como un paisaje de fitness "sintonizablemente accidentado" . La "rugosidad sintonizable" captura la intuición de que tanto el tamaño general del paisaje como el número 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 la determinación de la nivel de rugosidad del paisaje.${\displaystyle N}$${\displaystyle K}$${\displaystyle N}$${\displaystyle K}$

El modelo NK ha encontrado aplicación en una amplia variedad de campos, incluido el estudio teórico de la biología evolutiva , inmunología , optimización , evolución tecnológica y 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 buscar 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 de los mismos), 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 afectan las ganancias de una manera compleja. ^[1]

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

Una de las razones por las que el modelo ha atraído una gran atención en la optimización es que es una instancia particularmente simple del llamado problema NP-completo ^{[4], 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 ^{[5], 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 .

Detalles matemáticos

El modelo NK define un espacio de fase combinatorio , que consta de cada cadena (elegida 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 de acuerdo con 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 loci:${\displaystyle K}$

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

donde es el índice del th vecino del locus . ${\displaystyle k_{ij}}$${\displaystyle j}$${\displaystyle i}$

Por tanto, la función de aptitud es un mapeo entre cadenas de longitud K  + 1 y escalares, que el trabajo posterior de Weinberger llama "contribuciones de aptitud". Estas contribuciones a la aptitud a menudo se eligen al azar de alguna distribución de probabilidad especificada.${\displaystyle f_{i}}$

En 1991, Weinberger publicó un análisis detallado ^[6] del caso en el que y las contribuciones a la aptitud se eligen al azar. Más tarde se demostró que su estimación analítica del número de óptimos locales era defectuosa ^{[ cita requerida ]} . Sin embargo, los experimentos numéricos incluidos en el análisis de Weinberger apoyan 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)]}}}$.

Visualización de dos dimensiones de un panorama de fitness NK. Las flechas representan varios caminos mutacionales que la población podría seguir mientras evoluciona en el panorama del fitness.

Ejemplo

Para simplificar, trabajaremos con cadenas binarias . Considere un modelo NK con N = 5, K = 1. Aquí, la aptitud de una cuerda viene dada por la suma de las contribuciones de aptitud individual de cada uno de los 5 loci. Cada contribución a la aptitud depende del valor del locus local y de otro. Emplearemos la convención que , para que cada locus sea afectado por su vecino, y por ciclicidad. Si elegimos, por ejemplo, la función de aptitud f (0, 0) = 0; f (0, 1) = 1; f (1, 0) = 2; f (1, 1) = 0, los valores de aptitud de dos cadenas de ejemplo son:${\displaystyle f(S_{i})=f(S_{i},S_{i+1})}$${\displaystyle f(S_{5})=f(S_{5},S_{1})}$

${\displaystyle F(00101)=f(0,0)+f(0,1)+f(1,0)+f(0,1)+f(1,0)=0+1+2+1+2=6.}$

${\displaystyle F(11100)=f(1,1)+f(1,1)+f(1,0)+f(0,0)+f(0,1)=0+0+2+0+1=3.}$

Topología ajustable

Ilustración de topología ajustable en el modelo NK. Los nodos son cadenas binarias individuales, los bordes 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 denota su aptitud, y los valores más rojos tienen una mayor aptitud. La incrustación del hipercubo se elige de modo que el máximo de fitness esté en el centro. Observe que el paisaje de K = 0 parece más suave que los casos de K más alto.

El valor de K controla el grado de epistasis en el modelo NK, o cuánto afectan otros loci a 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 ceros si f (0)> f (1 ), o todos unos si f (1)> f (0)). Para K distinto de cero , la aptitud de una cuerda es una suma de la aptitud de las subcadenas, que pueden interactuar para frustrar el sistema (considere cómo lograr una aptitud óptima en el ejemplo anterior). K creciente aumenta así la dureza del paisaje de fitness.

Variaciones con espacios neutros

El modelo NK desnudo no admite el fenómeno del espacio neutral , es decir, conjuntos de genomas conectados por mutaciones únicas 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 se degeneran ^{[ cita requerida ]} . El modelo NKQ introduce un parámetro y aplica una discretización sobre los posibles valores de contribución de aptitud para que cada contribución tome uno de${\displaystyle P}$${\displaystyle P}$${\displaystyle 2^{K}}$${\displaystyle Q}$${\displaystyle Q}$valores posibles, nuevamente introduciendo 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=0}$${\displaystyle Q=\infty }$

Aplicaciones

El modelo NK se ha utilizado en muchos campos, incluido el estudio de los vidrios giratorios , la epistasis y la pleiotropía en biología evolutiva y la optimización combinatoria .

Referencias

1. Levinthal, DA (1997). "Adaptación sobre paisajes accidentados". Ciencias de la gestión . 43 (7): 934–950. doi : 10.1287 / mnsc.43.7.934 .
2. Kauffman, S .; Levin, S. (1987). "Hacia una teoría general de caminatas adaptativas sobre paisajes accidentados". Revista de Biología Teórica . 128 (1): 11–45. doi : 10.1016 / s0022-5193 (87) 80029-2 . PMID 3431131 . 
3. Kauffman, S .; Weinberger, E. (1989). "El modelo NK de paisajes de fitness accidentados y su aplicación a la maduración de la respuesta inmune". Revista de Biología Teórica . 141 (2): 211–245. doi : 10.1016 / s0022-5193 (89) 80019-0 . PMID 2632988 . 
4. Weinberger, E. (1996), "NP-completitud del modelo Nk de Kauffman, un paisaje de fitness sintonizablemente rugoso", Documento de trabajo del Instituto de Santa Fe, 96-02-003.
5. Kaznatcheev, Artem (2019). "Complejidad computacional como una restricción última de la evolución" . Genética . 212 (1): 245–265. doi : 10.1534 / genetics.119.302000 . PMC 6499524 . PMID 30833289 .  
6. Weinberger, Edward (15 de noviembre de 1991). "Propiedades locales del modelo Nk de Kauffman: un paisaje energético sintonizablemente accidentado". Physical Review A . 10. 44 (10): 6399–6413. Código Bibliográfico : 1991PhRvA..44.6399W . doi : 10.1103 / physreva.44.6399 . PMID 9905770 .