sábado, 29 de agosto de 2009

Algoritmos genéticos y simulación en genética de poblaciones. Dinámica de sistemas multiloci

En genética de poblaciones modelar la dinámica, esto es la evolución a lo largo del tiempo, de un cierto número de genes en presencia de selección, mutación y recombinación exige usar el método de simulación de Montecarlo. Nótese que si no hay recombinación los genes se comportan como uno sólo y estaríamos hablando de un modelo de un sólo gen (o locus si nos referimos al lugar que ocupa el gen en el genoma). Este es el único caso en que la dinámica del sistema, el conocimiento de puntos de equilibrio y su estabilidad, es perfectamente conocida.

Sin embargo, en cuanto consideramos más de un gen, incluso en el caso de sólo dos, la situación se complica. Se podría pensar que a estas alturas el caso de un mísero par de genes bialélicos debería estar perfectamente resuelto para cualquier modelo de eficacia biológica o fitness. Lo cierto es que a pesar de que sí ha sido muy estudiado, sobre todo para casos especiales de la función de “fitness” (véase una interesante revisión en [1]), dista de estar completamente resuelto incluso en el caso sin mutación pudiendo aparecer dinámicas de comportamiento bastante complejo [2]. Que no decir si hablamos de tres o más genes [3, 4]. En cuanto a la dinámica de estos sistemas multiloci podemos considerar la selección a nivel haploide (sobre los gametos) o diploide (sobre los zigotos) teniendo en cuenta que la correspondencia entre unos modelos y otros dependerá del esquema de fitness asumido [5]. En cualquier caso y debido a la dificultad para analizar estos modelos multigénicos o multiloci, surge el uso de la herramienta de simulación la cual permite estudiar la evolución de los susodichos sistemas bajo distintas condiciones de mutación, selección, recombinación, tamaño poblacional etc.

El algoritmo de simulación clásico, que implementa el modelo de reproducción de Wright-Fisher y sus diferentes variantes incluyendo selección, mutación y recombinación es similar a un algoritmo genético (AG) en su versión básica, el conocido SGA (Simple Genetic Algorithm), con la peculiaridad de que los genes no son resultado de una codificación para representar un problema dado sino que podríamos decir que se representan a sí mismos o más precisamente a un fenotipo P = f(G,E) donde G es el genoma o conjunto de genes y f es la función, incluyendo la identidad, que mapea el fenotipo a partir de un genotipo y ambiente E dados. La fitness será a su vez una función sobre P. Es decir, el modelo de simulación en genética de poblaciones es formalmente un SGA pero que evita el problema de la representación asociado al caso de codificación binaria porque no es necesario inventarse una codificación genética para los puntos del espacio de soluciones de un problema dado pues los individuos bajo estudio ya incorporan su propio código genético. A parte de esto, lo que diferencia a ambos enfoques es simplemente la finalidad con la que utilizamos el algoritmo. En el caso del SGA nosotros dirigimos el proceso evolutivo mediante la función de fitness de modo que esta es máxima en la dirección en que se resuelve nuestro problema ya sea este de maximización, minimización, estimación, control, etc. Esto es, ignoramos el valor exacto de la solución pero conocemos la dirección y el sentido del vector solución y definimos la función de fitness en consecuencia. Lo que esperamos del algoritmo es que el proceso evolutivo vía selección, mutación y recombinación baraje la combinación adecuada de genes que nos lleve al punto o región deseada. Esa combinación genética al decodificarla nos dará la solución que buscamos. En genética de poblaciones el tipo de problema es bien distinto puesto que de entrada no dirigimos el proceso evolutivo si no más bien deseamos comprender ese mismo proceso y las diferentes relaciones entre los parámetros implicados y de estos con la función de fitness, el ambiente e incluso determinados factores estocásticos generados por el tamaño poblacional finito. En este sentido los algoritmos genéticos (AGs) en general son interesantes porque se caracterizan por manejar tamaños de población muy pequeños y con un componente selectivo grande. Desde el punto de vista evolutivo este es un terreno adecuado para el efecto de Hill-Robertson [6, 7] el cual predice que tenderán a aparecer combinaciones genéticas intermedias es decir gametos con alelos favorables en unos loci y desfavorables en otros. El que, de un modo u otro, cierto tipo de combinaciones se vean favorecidas genera lo que se conoce como desequilibrio de ligamiento, en este caso negativo (al favorecerse combinaciones intermedias) lo que a su vez provoca que la recombinación tenga un efecto beneficioso sobre la fitness poblacional.

Dicho lo anterior, podemos esperar que en los algoritmos genéticos el efecto de la recombinación sea especialmente importante. En cuanto a la selección, el modelo clásico en el SGA es el de selección proporcional a la fitness que garantiza que, en promedio, los individuos serán seleccionados en proporción a su fitness de modo que cuanto mayor es esta, mayor es la opción de reproducirse. El problema aquí es lo comentado sobre los tamaños poblacionales pequeños, debido a la elevada estocasticidad (deriva genética en la terminología de la genética de poblaciones) que ello genera, se pierde la garantía de que las mejores combinaciones sean seleccionadas. Por ello se utilizan a menudo AGs con otros esquemas de selección alejados del modelo biológico como la selección elitista (nos quedamos con los mejores) o por torneo (combina elitista y proporcional). El problema de estos modelos es la pérdida de variabilidad que subyace en sus estrategias; obviamente si encontrar la solución fuera tan simple como ir siguiendo las variantes óptimas de cada generación apenas necesitaríamos usar la estrategia evolutiva. En realidad la clave en el uso de la estrategia de selección proporcional a la fitness sería una adecuada combinación de los parámetros de intensidad de selección, tamaño poblacional, mutación y recombinación. Justamente, comprender la relación entre estos parámetros es el objetivo de la genética de poblaciones teórica. En el caso específico de los AGs y dado su bajo tamaño poblacional, el estudio de las condiciones del efecto de H-R y la recombinación deberían ser los aspectos principales a tener en cuenta. En este sentido, aunque desde una perspectiva puramente heurística, se han desarrollado algoritmos meta-genéticos que autoajustan los propios parámetros de búsqueda (mutación y recombinación), así como metapoblaciones de AGs realizando búsquedas independientes que se comunican vía migración esporádica de soluciones de una población a otra.

Otro aspecto que se plantea desde el punto de vista de la teoría de control y optimización, donde los AGs inicialmente surgen [8], es porqué y cómo funcionan los algoritmos genéticos. El porqué es, al menos desde el punto de vista de la genética de poblaciones, obvio. Funcionan porque las combinaciones peores se reproducen menos y las mejores más por tanto, dadas unas fuentes de variabilidad primaria, la mutación y secundaria, la recombinación, con el paso del tiempo obtenemos un conjunto de soluciones óptimas o cuasi-óptimas. Respecto al cómo, se han hecho incursiones teóricas en la dinámica de los algoritmos usando herramientas de matemática avanzada como la mecánica estadística de la física cuántica [9, 10] sin embargo, tal y como hemos comentado al principio, si ya la dinámica de unos pocos genes es compleja, difícil es obtener soluciones explícitas para el caso de muchos genes. Con todo, es interesante percatarse de que mientras la genética de poblaciones se ha centrado siempre en descripciones de la evolución de la frecuencia de las distintas combinaciones genéticas y la conexión de estas con los parámetros del modelo y con los correspondientes valores de fitness, en el ámbito de los AGs el enfoque ha sido, quizás no sorprendentemente, mucho más mecanicista. Es decir, la explicación del camino a la solución o a la fitness final se da en términos de la construcción de los bloques genéticos adecuados y no del contexto que lleva a ello. Una de las hipótesis más significativas, aunque todavía sometida a debate, sobre el funcionamiento de los AGs es el teorema de los esquemas que viene a decir que la solución se obtiene construyendo con pequeños bloques o esquemas formados por grupos de unos pocos buenos genes no muy distantes unos de otros. Lo de pocos sería para que la probabilidad de que la mutación altere los genes buenos sea baja y lo de próximos para que la recombinación no rompa esas combinaciones.

La diferencia entre ambos planteamientos, genética de poblaciones versus AGs, es fiel reflejo de las distintas finalidades en ambos campos, como ya se dijo, una se centra en el propio proceso evolutivo, el otro quiere llegar a un objetivo sin que importe el contexto en que ello ocurre. Sin embargo, la cuestión sobre cómo trabajan los AGs para encontrar la solución a un problema, es la misma que se mencionó al comienzo, esto es, conocer las pautas de comportamiento a lo largo del tiempo de un conjunto de genes, dados unos valores de mutación, recombinación y selección con la dificultad añadida de que el tamaño poblacional es apreciablemente finito lo que incorpora una importante componente estocástica al problema.

Es pues este un ejemplo de cómo un modelo que es sencillo de simular en el ordenador, se muestra tremendamente complejo a la hora de analizar su dinámica. Lo interesante es percibir cómo dos ámbitos absolutamente separados, a saber, la genética de poblaciones en biología y las áreas relacionadas con problemas de optimización, automatización, y control en ingeniería, han tratado de teorizar sobre esta dinámica realizando, curiosamente, muy poco trabajo interdisciplinar. En mi opinión, todos tienen mucho que ganar aquí: los teóricos de los AGs con el enfoque de la genética de poblaciones, pues el contexto se mostrará clave en cuanto a la resolución eficiente de problemas difíciles. Así mismo, los biólogos tienen en el campo de los algoritmos genéticos, por un lado una aplicación muy interesante de los modelos evolutivos y por otro la posibilidad de combinar sus conocimientos del contexto, las interacciones entre selección, deriva, mutación, recombinación etc con el nuevo enfoque donde se trata de ver el modo en que los diferentes bloques genotípicos son parcialmente construidos mediante esquemas.

Bibliografía

1. Li CC: Genetic equilibrium under selection. Biometrics 1967, 23(3):397-484.

2. Bürger R: The Mathematical theory of selection, recombination, and mutation. Chichester: John Wiley; 2000.

3. Robinson WP, Asmussen MA, Thomson G: Three-locus systems impose additional constraints on pairwise disequilibria. Genetics 1991, 129(3):925-930.

4. Baake M, Baake E: Erratum to: An exactly solved model for mutation, recombination and selection. Canadian Journal of Mathematics 2008, 60(2):264-265.

5. Kirzhner V, Lyubich Y: Multilocus dynamics under haploid selection. J Math Biol 1997, 35(4):391-408.

6. Hill WG, Robertson A: The effect of linkage on limits to artificial selection. Genet Res 1966, 8(3):269-294.

7. Zeng Z-B: The Hill-Robertson effect is a consequence of interplay between linkage, selection and drift: a commentary on The effect of linkage on limits to artificial selection by W. G. Hill and A. Robertson. Genet Res 2008, 89(Special Issue 5-6):309-310.

8. Goldberg DE: Genetic algorithms in search, optimization, and machine learning. Reading, Mass.: Addison-Wesley; 1989.

9. Prugel-Bennett A, Shapiro J: The dynamics of a genetic algorithm for simple random Ising systems. Phys D 1997, 104(1):75-114.

10. Shapiro J, Prugel Bennett A, Rattray M: A Statistical Mechanical Formulation of the Dynamics of Genetic Algorithms. In: Selected Papers from AISB Workshop on Evolutionary Computing. Springer-Verlag; 1994.