Publicado en Science: Eco-evo-devo y cómo los alelos raros pueden derivar en nuevas especies

Eco-evo-devo (ecological evolutionary developmental biology) es el paradigma de moda en biología evolutiva. Los agentes del medio alteran la expresión genética y seleccionan un fenotipo particular entre todo el repertorio heredado de fenotipos posibles. Si bien un biólogo es quien debería de hablar de estos temas, me ha sorprendido un artículo publicado en Science repleto de fórmulas matemáticas sobre estos temas. Sí, me ha sorprendido ver ecuaciones integrodiferenciales en un artículo de biología publicado en esta prestigiosa revista, aunque sea un modelo logístico con un kernel exponencial. No puedo resistirme a ofreceros (a la izquierda) la ecuación del modelo estudiado en este artículo, cuya utilidad biológica no estoy preparado para discutir, pero cuya formulación matemática es simple y efectiva, para un matemático, aunque me huelo que casi incomprensible para un biólogo. Sin entrar en más detalles, el artículo técnico, cuyo título es espectacular “Complejidad y Diversidad,” como debe ser para que llegue a aparecer en Science, es Michael Doebeli, Iaroslav Ispolatov, “Complexity and Diversity,” Science 328: 494-497, 23 April 2010 (información suplementaria gratis).

Un modelo unidimensional, tradicional en ecología teórica y teoría de la evolución, donde los individuos tienen un fenotipo escalar (x) que determina sus preferencias por los recursos. La competencia entre los individuos con fenotipos x e y se describe mediante un núcleo (kernel) que los autores asumen como una función unimodal de la distancia entre los fenotipos |xy| con un valor máximo en |xy| = 0. Los individuos con un fenotipo raro tienen pocos individuos similares en la población por lo que experimentan una gran competencia por parte de muchos otros individuos. La ecución integrodiferencial en derivadas parciales para la densidad de fenotipos φ(x) presenta un término integral con un kernel α(x, y) que representa el impacto de la competencia del resto de los individuos de la población. La función unimodal K(x), con un máximo en x=0, representa la capacidad de la población en el estado de equilibrio (término típico de una ecuación logística). Los parámetros a>0 y k>0 en el kernel de competencia y en la capacidad miden la importancia relativa de la dependencia con la frecuencia de los efectos de la competencia y la selección, y los exponentes n , nK > 2, en ambas fórmulas son parámetros de forma. El modelo gaussiano se obtiene para  n = nK = 2. Para k > a, la dinámica de la ecuación integrodiferencial converge a una función delta centrada en x = 0. Para k < a, la dinámica converge a una distribución de equilibrio que es similar a una distribución normal con varianza positiva. En una interpretación eco-evo-devo, para k > a, la población evoluciona hacia una nueva especie y para k < a, la diversidad de fenotipos en la población se mantiene. Bueno, no me enrollo más, que es ya muy tarde y la mente de uno se satura con estos temas, …

La simulación eficiente del modelo de Hubbard para los electrones en un sólido implicará la igualdad de las clases de complejidad P=NP=QMA

Dibujo20091028_currently_complexity_classes_inclusions_P_NP_QMA_NP-hard_QMA-hard

Las clases de complejidad clásicas y cuánticas se relacionan entre sí de una forma complicada que todavía no conocemos en detalle y por ahora todo son hipótesis. Las clases P y BQP son las clases de problemas resolubles de forma eficiente (polinómica) en ordenadores clásicos y cuánticos, resp. Las clases NP y QMA contienen los problemas de decisión que creemos que son más difíciles para ordenadores clásicos y cuánticos, resp., para los que existen algoritmos eficientes, clásicos y cuánticos, resp.,  que permiten decidir si una solución es correcta o no. Un artículo reciente en Nature Physics ha demostrado que las clases QMA, NP y P colapsarían (serían iguales entre sí), resolviendo la conjetura P versus NP con una igualdad, si se puede resolver de forma eficiente la simulación de sistemas cuánticos descritos por la teoría del funcional densidad (DFT). Por ejemplo, si un modelo concreto, el modelo cuántico de Hubbard, se puede simular en tiempo polinómico. Nadie cree que esto sea posible, pero carecemos de una demostración, todavía. Nos lo cuenta el experto en la teoría de la complejidad cuántica Scott Aaronson, “Computational complexity: Why quantum chemistry is hard,” Nature Physics 5: 707-708, 2009, haciéndose eco del artículo técnico de Norbert Schuch & Frank Verstraete, “Computational complexity of interacting electrons and fundamental limitations of density functional theory,” Nature Physics 5: 732-735, 2009.

La clase de complejidad del Protocolo Merlín-Arturo (MA) es la clase de problemas de decisión resolubles por el protocolo siguiente. Merlín tiene  recursos computacionales ilimitados y envía a Arturo una demostración de tamaño polinómico que prueba que la respuesta es “sí.” Arturo puede verificar dicha prueba en la clase BPP (en tiempo polinómico con un algoritmo probabilístico). Si la respuesta es “sí” existe una demostración que Arturo aceptará como correcta con una probabilidad mayor que 2/3 y si la respuesta es “no” todas las demostraciones serán aceptadas por Arturo con una probabilidad menor que 1/3.

La clase de complejidad cuántica del Protocolo Merlín-Arturo (QMA) es la versión cuántica de MA y corresponde a un Merlín que envía una mensaje con una prueba cuántica que Arturo puede verificar en la clase BQP (en tiempo polinómico utilizando un algoritmo cuántico). Si la respuesta es “sí” existe un estado cuántico (demostración) que Arturo aceptará como correcta con una probabilidad mayor que 2/3 y si la respuesta es “no” todos los estados (demostraciones) serán rechazados por Arturo con un probabilidad mayor que 2/3.

El modelo de Hubbard describe un gas de electrones fuertemente acoplados por potenciales de Coulomb en la retícula de un sólido y permite comprender la transición entre un material conductor y uno aislante. La técnica matemática más utilizada para simular este modelo físico es la llamada teoría del funcional densidad (density functional theory). El nuevo artículo demuestra que si dicho problema se puede simular de forma eficiente, las clases de complejidad QMA y P serán iguales. Esto implica un gran avance en dos frentes. Por un lado, en la propia teoría de la complejidad de algoritmos cuánticos. Y por otro lado, impone un límite fundamental a la propia teoría del funcional densidad ya que una demostración de que P =!= NP (lo que todo el mundo cree) implicaría que nunca podremos simular eficientemente problemas “aparentemente” tan sencillos como el modelo de Hubbard incluso utilizando ordenadores cuánticos.

Esto sorprenderá a muchos ya que la mayoría pensaba que la utilidad más importante de los ordenadores cuánticos (cuando los haya) será la simulación de sistemas cuánticos. Pero si un sistema cuántico tan sencillo como el modelo de Hubbard es tan complejo de simular en un ordenador cuántico como en uno clásico, dicha ventaja se cae por su propio peso. Los avances en computación cuántica no cesan y cada día nos sorprenden más a los que somos aficionados a este “arte,” a esta ciencia.

El arte moderno de la complejidad genómica en biología

Dibujo20091008_Modules_correlated_transcripts_associated_organismal_phenotypes_left_Competitive_fitness_right_Starvation_stress_resistance

Hace años un gen estaba asociado a una característica física del fenotipo. Hoy sabemos que esto no es verdad. La biología de sistemas ha demostrado que cada una depende de la interacción de una compleja red de genes entre sí y con el entorno. La figura de arriba muestra dos diagramas de correlación entre los genes expresados para dos fenotipos diferentes en la mosca de la fruta. Hay similitudes pero también hay muchas diferencias. Viendo estos diagramas es muy difícil distinguir qué genes son los responsables últimos de dichos fenotipos. Todo está imbricado y regiones muy alejadas del genoma se ven afectadas. Estos diagramas de colores, que parecen cuadros de arte moderno, aparecen cada día con más asiduidad en los artículos técnicos. Sin entrar en los detalles, esta visualización científica de estos datos multidimensionales ofrece al lego una obra artística abstracta con cierta belleza, la propia del arte moderno. La visualización científica, la rama de la ciencias computacionales que estudia como representar datos multidimensionales mostrando sus interrelaciones, destacando lo “funcional” en lo estrictamente complejo, tiene muchas veces más de arte que de ciencia, la artesanía de los datos. Nos lo cuenta Judith E. Mank, “Journal Club,” Nature 461: 701, 8 october 2009.

Judith nos recuerda que Trudy Mackay, en la Universidad Estatal de Carolina del Norte, en Raleigh, EEUU, y sus colaboradores están estudiando las bases genéticas de los fenotipos más distintivos de la mosca de la fruta, Drosophila melanogaster. Su enfoque sistémico está basado en el estudio de más de 10.000 genes que son correlacionados entre sí y con diferentes expresiones fenotípicas. La elegancia de esta complejidad se expresa en figuras geométricas de vivos colores que podrían ocupar las paredes de cualquier galería de arte moderno. El artículo técnico J. F. Ayroles et al. “Systems genetics of complex traits in Drosophila melanogaster,” Nature Genetics 41: 299–307, 2009. La belleza de esta figura se conjuga con nuevos datos que muestran las conexiones entre conceptos clásicos como la herencia y conceptos nuevos como la pleitropía (un gen como responsable de efectos fenotípicos o caracteres distintos y no relacionados).

Dibujo20091008_Pleiotropy_between_phenotypic_modules_connected_with_significant_overlap

El estado actual del problema P distinto de NP

Dibujo20090905_p_versus_np_in_the_simpsons_tv_series

El estado actual del problema P versus NP se resume en que el problema sigue abierto. Aunque se han hecho grandes avances, no se atisba que una demostración vaya a ser obtenida en las próximas décadas. ¿Pueden los computadores cuánticos resolver los problemas NP completos en tiempo polinomial? Nadie lo sabe, pero la respuesta oficial es que parece que no pueden. El millón de dólares para quien demuestre que P≠NP seguirá generando intereses. ¿Qué pasaría si alguien demuestra que P=NP? Según los estatutos del Premio del Milenio, no recibirá ni un solo dólar, aunque sí fama mundial. Bueno, en serio, recibiría 5 millones de dólares ya que podría resolver el resto de los 7 problemas del Milenio en un tiempo razonable con un demostrador automático si las correspondientes demostraciones tienen, digamos, 100 páginas de longitud. Nos lo cuenta Lance Fortnow, “Review article. The Status of the P Versus NP Problem,” Communications of the ACM 52: 78-86, 2009 [versión gratis html]. Un resumen breve en la presentación PowerPoint de la reciente charla de Scott Aaronson del MIT en “Has There Been Progress on the P vs. NP Question?” (visto en su blog “Barriers to snarky blogging,” Shtetl-Optimized, August 27th, 2009).

¿Qué es el problema P versus NP? Un algoritmo para resolver un problema es eficiente si su coste en tiempo es un polinomio dado en el tamaño de los datos de entrada. La clase de problemas para los que existen algoritmos que los resuelven de forma eficiente se denomina clase P (problemas resolubles en tiempo polinómico). Hay problemas para los que una posible solución se puede verificar en tiempo polinomial (hay un algoritmo en P que decide la validez de una solución). Este tipo de problemas se encuentran en la clase NP (problemas resolubles de forma no determinista en tiempo polinómico). El problema P versus NP trata de estudiar si es cierto o no que P=NP, es decir, que todo problema para el que se puede verificar eficientemente su solución es un problema para el que se puede calcular su solución de forma eficiente.

La clase de problemas NP completos (NP-c) es una clase de problemas que son equivalentes entre sí de tal manera que si alguien encuentra un algoritmo eficiente para uno de ellos, automáticamente obtiene una algoritmo eficiente para todos los demás problemas en NP-c, más aún, también lo será para todos los problemas en NP. Es decir, un algoritmo eficiente para un problema NP-c automáticamente implica que P=NP. Hoy en día se conocen cientos de problemas NP-c (y cientos de demostraciones falsas (“fake“) de que se encuentran en P).

La mayoría de los investigadores en informática teórica cree que P≠NP, pero desde 1972 múltiples intentos de demostrar esta conjetura han sido infructuosos. En el año 2000, uno de los problemas del milenio del Instituto Clay de Matemáticas donará un millón de dólares a quien demuestre que P≠NP, aunque ni un solo dólar a quien demuestre que P=NP. En un mundo donde P=NP muchos estarían contentos, habría algoritmos eficientes (“rápidos”) para muchos problemas, sin embargo, muchos otros estarían tristes, la criptografía (cifrado) de clave pública sería inútil (habría algoritmos que desvelarían las claves secretas “rápidamente”). La mayoría de los expertos en teoría de la complejidad creen que P≠NP y que su demostración sólo es cuestión de tiempo.

¿Cómo se puede demostrar que P≠NP? Se han estudiado muchísimos caminos prometedores en los que se ha llegado a un callejón sin salida. Se ha avanzado mucho, pero todavía no se ve la luz al final del camino. Por ejemplo, si alguien encontrara un algoritmo en NP capaz de simular todos los problemas en P, entonces se podría utilizar un argumento de diagonalización (similar al usado por Turing para el Problema de la Parada) para demostrar que P≠NP. Los avances más importantes en los últimos años vienen en la línea que utiliza la geometría algebraica y la computación con números reales. Más detalles en el artículo de Fortnow, que se lee fácil para cualquier informático.

¿Pueden los ordenadores cuánticos resolver problemas NP completos? Peter Shor demostró que el problema de factorizar números enteros en factores primos y el problema de calcular logaritmos discretos se pueden resolver en tiempo polinómico con un algoritmo cuántico. Sin embargo, nadie sabe si estos problemas se encuentran en NP-c. De hecho, los expertos creen que el trabajo de Shor apunta a una demostración de que no lo están. Más aún, los trabajos de Grover parecen indicar que los algoritmos cuánticos (salvo excepciones como el algoritmo de Shor) sólo pueden lograr un speed-up cuadrático.

Para acabar, ¿en qué se ha avanzado en el problema P versus NP las últimas décadas? Básicamente se han obtenido resultados particulares (algunos con demostraciones muy complicadas), que según los expertos deberán estar incluidos en cualquier demostración del resultado general. Estos resultados permiten saber rápidamente si cualquier nueva “demostración” es correcta o no sólo echándole un vistazo. Si no incluye estos resultados particulares, debe ser incorrecta y los expertos “pasan” de prestarle más atención. Según Scott Aaranson es como el problema de la gravedad cuántica, cualquier propuesta debe demostrar que incluye la mecánica cuántica y la gravedad de Einstein, si no lo hace, nadie creerá que es la respuesta correcta.