Computación evolutiva de bosques de expansión mínimos con restricción de grado y de rol

Encontrar el árbol de expansión mínimo con restricción de grado de un grafo (DCMST por sus siglas en inglés) es un problema NP-complejo ampliamente estudiado. Una de sus aplicaciones más importantes es el dise~no de redes. Aquí nosotros tratamos una nueva variante del problema DCMST, que consiste en encontrar el árbol de expansión mínimo no solo con restricciones de grado, sino también con restricciones de rol (DRCMST), es decir, a~nadimos restricciones para restringir el rol que los nodos tienen en el árbol. Estos roles pueden ser nodo raíz, nodo intermedio o nodo hoja. Por otra parte, no limitamos el número de nodos raíz a uno, por lo que, en general, construiremos bosques de DRCMSTs. El modelado en los problemas de dise~no de redes puede beneficiarse de la posibilidad de generar más de un árbol y determinar el rol de los nodos en la red. Proponemos una nueva representación basada en permutaciones para codificar los bosques de DRCMSTs. En esta nueva representación, una permutación codifica simultáneamente todos los árboles que se construirán. Nosotros simulamos una amplia variedad de problemas DRCMST que optimizamos utilizando ocho algoritmos de computación evolutiva diferentes que codifican los individuos de la población utilizando la representación propuesta. Los algoritmos que utilizamos son: algoritmo de estimación de distribuciones (EDA), algoritmo genético generacional (gGA), algoritmo genético de estado estacionario (ssGA), estrategia evolutiva basada en la matriz de covarianzas (CMAES), evolución diferencial (DE), estrategia evolutiva elitista (ElitistES), estrategia evolutiva no elitista (NonElitistES) y optimización por enjambre de partículas (PSO). Los mejores resultados fueron para el algoritmo de estimación de distribuciones utilizado y ambos tipos de algoritmos genéticos, aunque los algoritmos genéticos fueron significativamente más rápidos.---ABSTRACT---Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode the forest of DRCMSTs. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight diferent evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm (EDA), generational genetic algorithm (gGA), steady-state genetic algorithm (ssGA), covariance matrix adaptation evolution strategy (CMAES), diferential evolution (DE), elitist evolution strategy (ElististES), non-elitist evolution strategy (NonElististES) and particle swarm optimization (PSO). The best results are for the estimation of distribution algorithm and both types of genetic algorithms, although the genetic algorithms are significantly faster. iv

Modelo de computación conexionista inspirado en las redes de procesadores evolutivos y su aprendizaje

La informática teórica es una disciplina básica ya que la mayoría de los avances en informática se sustentan en un sólido resultado de esa materia. En los últimos a~nos debido tanto al incremento de la potencia de los ordenadores, como a la cercanía del límite físico en la miniaturización de los componentes electrónicos, resurge el interés por modelos formales de computación alternativos a la arquitectura clásica de von Neumann. Muchos de estos modelos se inspiran en la forma en la que la naturaleza resuelve eficientemente problemas muy complejos. La mayoría son computacionalmente completos e intrínsecamente paralelos. Por este motivo se les está llegando a considerar como nuevos paradigmas de computación (computación natural). Se dispone, por tanto, de un abanico de arquitecturas abstractas tan potentes como los computadores convencionales y, a veces, más eficientes: alguna de ellas mejora el rendimiento, al menos temporal, de problemas NPcompletos proporcionando costes no exponenciales. La representación formal de las redes de procesadores evolutivos requiere de construcciones, tanto independientes, como dependientes del contexto, dicho de otro modo, en general una representación formal completa de un NEP implica restricciones, tanto sintácticas, como semánticas, es decir, que muchas representaciones aparentemente (sintácticamente) correctas de casos particulares de estos dispositivos no tendrían sentido porque podrían no cumplir otras restricciones semánticas. La aplicación de evolución gramatical semántica a los NEPs pasa por la elección de un subconjunto de ellos entre los que buscar los que solucionen un problema concreto. En este trabajo se ha realizado un estudio sobre un modelo inspirado en la biología celular denominado redes de procesadores evolutivos [55, 53], esto es, redes cuyos nodos son procesadores muy simples capaces de realizar únicamente un tipo de mutación puntual (inserción, borrado o sustitución de un símbolo). Estos nodos están asociados con un filtro que está definido por alguna condición de contexto aleatorio o de pertenencia. Las redes están formadas a lo sumo de seis nodos y, teniendo los filtros definidos por una pertenencia a lenguajes regulares, son capaces de generar todos los lenguajes enumerables recursivos independientemente del grafo subyacente. Este resultado no es sorprendente ya que semejantes resultados han sido documentados en la literatura. Si se consideran redes con nodos y filtros definidos por contextos aleatorios {que parecen estar más cerca a las implementaciones biológicas{ entonces se pueden generar lenguajes más complejos como los lenguajes no independientes del contexto. Sin embargo, estos mecanismos tan simples son capaces de resolver problemas complejos en tiempo polinomial. Se ha presentado una solución lineal para un problema NP-completo, el problema de los 3-colores. Como primer aporte significativo se ha propuesto una nueva dinámica de las redes de procesadores evolutivos con un comportamiento no determinista y masivamente paralelo [55], y por tanto todo el trabajo de investigación en el área de la redes de procesadores se puede trasladar a las redes masivamente paralelas. Por ejemplo, las redes masivamente paralelas se pueden modificar de acuerdo a determinadas reglas para mover los filtros hacia las conexiones. Cada conexión se ve como un canal bidireccional de manera que los filtros de entrada y salida coinciden. A pesar de esto, estas redes son computacionalmente completas. Se pueden también implementar otro tipo de reglas para extender este modelo computacional. Se reemplazan las mutaciones puntuales asociadas a cada nodo por la operación de splicing. Este nuevo tipo de procesador se denomina procesador splicing. Este modelo computacional de Red de procesadores con splicing ANSP es semejante en cierto modo a los sistemas distribuidos en tubos de ensayo basados en splicing. Además, se ha definido un nuevo modelo [56] {Redes de procesadores evolutivos con filtros en las conexiones{ , en el cual los procesadores tan solo tienen reglas y los filtros se han trasladado a las conexiones. Dicho modelo es equivalente, bajo determinadas circunstancias, a las redes de procesadores evolutivos clásicas. Sin dichas restricciones el modelo propuesto es un superconjunto de los NEPs clásicos. La principal ventaja de mover los filtros a las conexiones radica en la simplicidad de la modelización. Otras aportaciones de este trabajo ha sido el dise~no de un simulador en Java [54, 52] para las redes de procesadores evolutivos propuestas en esta Tesis. Sobre el término "procesador evolutivo" empleado en esta Tesis, el proceso computacional descrito aquí no es exactamente un proceso evolutivo en el sentido Darwiniano. Pero las operaciones de reescritura que se han considerado pueden interpretarse como mutaciones y los procesos de filtrado se podrían ver como procesos de selección. Además, este trabajo no abarca la posible implementación biológica de estas redes, a pesar de ser de gran importancia. A lo largo de esta tesis se ha tomado como definición de la medida de complejidad para los ANSP, una que denotaremos como tama~no (considerando tama~no como el número de nodos del grafo subyacente). Se ha mostrado que cualquier lenguaje enumerable recursivo L puede ser aceptado por un ANSP en el cual el número de procesadores está linealmente acotado por la cardinalidad del alfabeto de la cinta de una máquina de Turing que reconoce dicho lenguaje L. Siguiendo el concepto de ANSP universales introducido por Manea [65], se ha demostrado que un ANSP con una estructura de grafo fija puede aceptar cualquier lenguaje enumerable recursivo. Un ANSP se puede considerar como un ente capaz de resolver problemas, además de tener otra propiedad relevante desde el punto de vista práctico: Se puede definir un ANSP universal como una subred, donde solo una cantidad limitada de parámetros es dependiente del lenguaje. La anterior característica se puede interpretar como un método para resolver cualquier problema NP en tiempo polinomial empleando un ANSP de tama~no constante, concretamente treinta y uno. Esto significa que la solución de cualquier problema NP es uniforme en el sentido de que la red, exceptuando la subred universal, se puede ver como un programa; adaptándolo a la instancia del problema a resolver, se escogerín los filtros y las reglas que no pertenecen a la subred universal. Un problema interesante desde nuestro punto de vista es el que hace referencia a como elegir el tama~no optimo de esta red.---ABSTRACT---This thesis deals with the recent research works in the area of Natural Computing {bio-inspired models{, more precisely Networks of Evolutionary Processors first developed by Victor Mitrana and they are based on P Systems whose father is Georghe Paun. In these models, they are a set of processors connected in an underlying undirected graph, such processors have an object multiset (strings) and a set of rules, named evolution rules, that transform objects inside processors[55, 53],. These objects can be sent/received using graph connections provided they accomplish constraints defined at input and output filters processors have. This symbolic model, non deterministic one (processors are not synchronized) and massive parallel one[55] (all rules can be applied in one computational step) has some important properties regarding solution of NP-problems in lineal time and of course, lineal resources. There are a great number of variants such as hybrid networks, splicing processors, etc. that provide the model a computational power equivalent to Turing machines. The origin of networks of evolutionary processors (NEP for short) is a basic architecture for parallel and distributed symbolic processing, related to the Connection Machine as well as the Logic Flow paradigm, which consists of several processors, each of them being placed in a node of a virtual complete graph, which are able to handle data associated with the respective node. All the nodes send simultaneously their data and the receiving nodes handle also simultaneously all the arriving messages, according to some strategies. In a series of papers one considers that each node may be viewed as a cell having genetic information encoded in DNA sequences which may evolve by local evolutionary events, that is point mutations. Each node is specialized just for one of these evolutionary operations. Furthermore, the data in each node is organized in the form of multisets of words (each word appears in an arbitrarily large number of copies), and all the copies are processed in parallel such that all the possible events that can take place do actually take place. Obviously, the computational process just described is not exactly an evolutionary process in the Darwinian sense. But the rewriting operations we have considered might be interpreted as mutations and the filtering process might be viewed as a selection process. Recombination is missing but it was asserted that evolutionary and functional relationships between genes can be captured by taking only local mutations into consideration. It is clear that filters associated with each node allow a strong control of the computation. Indeed, every node has an input and output filter; two nodes can exchange data if it passes the output filter of the sender and the input filter of the receiver. Moreover, if some data is sent out by some node and not able to enter any node, then it is lost. In this paper we simplify the ANSP model considered in by moving the filters from the nodes to the edges. Each edge is viewed as a two-way channel such that the input and output filters coincide. Clearly, the possibility of controlling the computation in such networks seems to be diminished. For instance, there is no possibility to loose data during the communication steps. In spite of this and of the fact that splicing is not a powerful operation (remember that splicing systems generates only regular languages) we prove here that these devices are computationally complete. As a consequence, we propose characterizations of two complexity classes, namely NP and PSPACE, in terms of accepting networks of restricted splicing processors with filtered connections. We proposed a uniform linear time solution to SAT based on ANSPFCs with linearly bounded resources. This solution should be understood correctly: we do not solve SAT in linear time and space. Since any word and auxiliary word appears in an arbitrarily large number of copies, one can generate in linear time, by parallelism and communication, an exponential number of words each of them having an exponential number of copies. However, this does not seem to be a major drawback since by PCR (Polymerase Chain Reaction) one can generate an exponential number of identical DNA molecules in a linear number of reactions. It is worth mentioning that the ANSPFC constructed above remains unchanged for any instance with the same number of variables. Therefore, the solution is uniform in the sense that the network, excepting the input and output nodes, may be viewed as a program according to the number of variables, we choose the filters, the splicing words and the rules, then we assign all possible values to the variables, and compute the formula.We proved that ANSP are computationally complete. Do the ANSPFC remain still computationally complete? If this is not the case, what other problems can be eficiently solved by these ANSPFCs? Moreover, the complexity class NP is exactly the class of all languages decided by ANSP in polynomial time. Can NP be characterized in a similar way with ANSPFCs?

Efecto de la infección por virus persistentes y no persistentes sobre el comportamiento alimenticio, la preferencia, tasa de aterrizaje y asentamiento y la eficacia biológica de Aphis gossypii Glover

En el complejo de plagas que atacan a los principales cultivos hortícolas protegidos, destacan principalmente los Hemípteros, y dentro de estos los pulgones, dada su importancia como vectores de virus que provocan considerables daños y pérdidas económicas. Debido a que la dispersión de la mayoría de los virus de plantas puede ser eficaz con densidades bajas de vectores y su control es muy complicado al no existir métodos curativos para su control, es necesario generar nuevos conocimientos sobre las interacciones virus-vector con el fin de desarrollar nuevas y eficaces estrategias de control. Por ello, el objetivo general de esta Tesis ha sido conocer el efecto de la infección viral (directo-mediado por la presencia del virus en el vector- e indirecto-mediado por las alteraciones físico-químicas que se originan en la planta como consecuencia de la infección viral-) sobre el comportamiento y eficacia biológica del vector Aphis gossypii Glover y sus posibles repercusiones en la epidemiología de virosis de transmisión no persistente (Cucumber mosaic virus, CMV, Cucumovirus) y persistente (Cucurbit aphid-borne yellows virus, CABYV, Polerovirus). El primer objetivo de esta Tesis Doctoral, se centró en el estudio del efecto indirecto del virus de transmisión no persistente CMV sobre el comportamiento alimenticio y la preferencia del pulgón A. gossypii en el cultivo de pepino. Los ensayos de despegue y aterrizaje mostraron que los pulgones que fueron liberados en las plantas de pepino infectadas con CMV tuvieron una mayor propensión en migrar hacia las plantas no infectadas (60, 120 y 180 minutos después de la liberación) que aquellos que fueron sometidos al tratamiento contrario (planta no infectada hacia planta infectada con CMV). El estudio de preferencia y asentamiento mostró que el vector A. gossypii prefiere asentarse en plantas infectadas con CMV en una etapa temprana de evaluación (30 minutos después de la liberación). Sin embargo, este comportamiento se revirtió en una etapa posterior (4 y 48 horas después de la liberación), donde los pulgones se asentaron más en las plantas no infectadas. A través de la técnica de Gráficos de Penetración Eléctrica (EPG) se observó un efecto indirecto del virus CMV, revelado por un cambio brusco en el comportamiento de prueba del pulgón a lo largo del tiempo, cuando éstos fueron expuestos a las plantas infectadas con CMV. Los primeros 15 minutos de registro EPG mostraron que los pulgones hicieron un número mayor de punciones intracelulares (potencial drops - pds) y pruebas en las plantas infectadas con CMV que en las plantas no infectadas. Por otra parte, la duración de la primera prueba fue más corta y la duración total de las pds por insecto fue mucho más larga en las plantas infectadas con CMV. Se observaron diferencias significativas en el tiempo transcurrido desde el final de la última pd hasta el final de la prueba, siendo ese tiempo más corto para los pulgones que estaban alimentándose en plantas infectadas con CMV. En la segunda hora de registro los pulgones rechazaron las plantas infectadas con CMV como fuente de alimento, permaneciendo menos tiempo en las fases de prueba en floema (fase de salivación – E1 y fase de ingestión del floema – E2). El comportamiento alimenticio observado sobre las plantas infectadas con CMV favorece la adquisición y posterior transmisión de los virus de transmisión no persistente, los cuales son adquiridos e inoculados durante la realización de pruebas intracelulares en las primeras pruebas de corta duración. En el segundo objetivo de la Tesis se evaluó el efecto directo e indirecto del virus de transmisión persistente CABYV en el comportamiento alimenticio y preferencia del pulgón A. gossypii en cultivo de pepino, especie susceptible al virus, y algodón, especie inmune al virus. No se observó un efecto directo del virus relevante en el comportamiento alimenticio del vector, ya que los resultados obtenidos a nivel floemático en plantas de pepino no se observaron en plantas de algodón, inmune al virus CABYV. Esto sugiere que los resultados obtenidos en pepino, pueden deberse a un “posible efecto indirecto” originado por la infección de las plantas susceptibles al virus durante la realización del ensayo, lo que indirectamente puede modificar el comportamiento del pulgón durante la fase de evaluación. Sin embargo, el virus CABYV modificó indirectamente el comportamiento alimenticio de su vector a través de cambios en la planta infectada. Los pulgones tardaron menos tiempo en llegar al floema, realizaron un mayor número de pruebas floemáticas y permanecieron durante más tiempo en actividades floemáticas en plantas infectadas con CABYV. El comportamiento observado sobre las plantas infectadas con CABYV favorece la adquisición de virus persistentes, los cuales son adquiridos durante la alimentación sostenida en floema. El estudio de preferencia y asentamiento de A. gossypii mostró que los pulgones virulíferos prefieren asentarse en plantas no infectadas a corto y largo plazo de evaluación (2, 4 y 48 horas después de la liberación). Los ensayos de despegue y aterrizaje mostraron que los pulgones virulíferos que fueron liberados en las plantas de pepino infectadas con CABYV tuvieron una mayor propensión en migrar hacia las plantas no infectadas (3, 6, 24 y 48 horas después de la liberación) que aquellos que fueron sometidos al tratamiento contrario (planta no infectada hacia planta infectada con CABYV). Sin embargo, los pulgones no virulíferos no mostraron preferencia por plantas de pepino no infectadas o infectadas con CABYV en ninguno de los ensayos (preferencia o despegue) o periodos evaluados (corto y largo plazo). Los resultados indican que el virus CABYV es capaz de modificar indirectamente el comportamiento alimenticio de su vector a través de cambios en la planta infectada, favoreciendo su adquisición por su principal vector, A. gossypii. Una vez que los pulgones tienen capacidad de transmitir el virus (virulíferos) se produce un cambio en su comportamiento prefiriendo asentarse sobre plantas no infectadas optimizándose así la dispersión viral. El tercer objetivo de la Tesis, fue evaluar los efectos directos e indirectos del virus CABYV así como los efectos indirectos del virus CMV en la eficacia biológica del vector A. gossypii. Los resultados obtenidos en los ensayos realizados con el virus persistente CABYV indican que el virus parece no modificar directamente ni indirectamente la eficacia biológica del vector en plantas de pepino o algodón, no observándose diferencias estadísticas en ninguno de los parámetros poblacionales evaluados (tiempo de desarrollo, tasa intrínseca de crecimiento, tiempo generacional medio, tasa media de crecimiento relativo y ninfas totales). En cuanto a los ensayos realizados con el virus no persistente, CMV, los resultados muestran un efecto indirecto del virus sobre la biología del vector. Así resultó que tanto la tasa intrínseca de crecimiento natural (rm) como la tasa media de crecimiento relativo (RGR) fueron más altas para pulgones crecidos sobre plantas infectadas con CMV que sobre plantas no infectadas, favoreciendo la reproducción y crecimiento poblacional del vector sobre plantas infectadas con CMV. Los resultados obtenidos en la presente Tesis, ofrecen un ejemplo de como los virus de plantas pueden manipular directa e indirectamente a su vector, maximizando así su dispersión entre las plantas. Esos nuevos conocimientos generados tienen implicaciones importantes en la transmisión, dispersión y en la epidemiología de los virus y deben ser considerados para diseñar o ajustar los modelos de simulación existentes y patrones de dispersión que describen las epidemias de estos virus. ABSTRACT The main objective of this Thesis has been to understand the effect of the viral infection (direct-mediated by the presence of the virus in the vector and indirect mediated by the chemical and physical changes originated in the plant as a consequence of the viral infection) on the behaviour and biological efficacy of the vector Aphis gossypii Glover and its consequences in the epidemiology of two viral diseases, one with non-persistent transmission (Cucumber mosaic virus, CMV, Cucumovirus) and another with persistent transmission (Cucurbit aphid-borne yellows virus, CABYV, Polerovirus). The first objective of this Thesis was the study of the indirect effect of the nonpersistent virus CMV on the feeding behaviour and preference of the aphid A. gossypii in cucumber plants. The results of the alighting and settling behaviour studies showed that aphids exhibited no preference to migrate from CMV-infected to mock-inoculated plants at short time intervals (1, 10 and 30 min after release), but showed a clear shift in preference to migrate from CMV-infected to mock-inoculated plants 60 min after release. Our free-choice preference assays showed that A. gossypii alates preferred CMV-infected over mockinoculated plants at an early stage (30 min), but this behaviour was reverted at a later stage and aphids preferred to settle and reproduce on mock-inoculated plants. The electrical penetration graph (EPG) technique revealed a sharp change in aphid probing behaviour over time when exposed to CMV-infected plants. At the beginning (first 15 min) aphid vectors dramatically increased the number of short superficial probes and intracellular punctures when exposed to CMV-infected plants. At a later stage (second hour of recording) aphids diminished their feeding on CMV-infected plants as indicated by much less time spent in phloem salivation and ingestion (E1 and E2). This particular probing behaviour including an early increase in the number of short superficial probes and intracellular punctures followed by a phloem feeding deterrence is known to enhance the transmission efficiency of viruses transmitted in a NP manner. We conclude that CMV induces specific changes in a plant host that modify the alighting, settling and probing behaviour of its main vector A. gossypii, leading to optimum transmission and spread of the virus. The second objective of this work was to evaluate the effects that the persistently aphid transmitted Cucurbit aphid-borne yellows virus (CABYV) can induce directly and indirectly on the alighting, settling and probing behaviour activities of the cotton aphid A. gossypii. Only minor direct changes on aphid feeding behaviour was observed due to CABYV when viruliferous aphids fed on mock-inoculated plants. However, the feeding behaviour of non-viruliferous aphids was very different on CABYV-infected than on mockinoculated plants. Non-viruliferous aphids spent longer time feeding from the phloem when plants were infected by CABYV than on mock-inoculated plants, suggesting that CABYV indirectly manipulates aphid feeding behaviour through its shared host plant in order to favour viral acquisition. The vector alighting and settling preference was compared between nonviruliferous and viruliferous aphids. Viruliferous aphids showed a clear preference for mockinoculated over CABYV-infected plants at short and long time, while such behaviour was not observed for non-viruliferous aphids. Overall, our results indicate that CABYV induces changes in its host plant that modifies aphid feeding behaviour in a way that virus acquisition from infected plants is enhanced. Once the aphids become viruliferous they prefer to settle on healthy plants, leading to optimize the transmission and spread of the virus. The third objective was to evaluate the direct and indirect effects of CABYV and indirect effects of the CMV on the A. gossypii fitness. Obtained results for the persistent virus CABYV showed that the virus did not modify the vector fitness in cucumber or cotton plants. None of the evaluated variables was statistically significant (development time (d), intrinsic growth rate (rm), mean relative growth rate (RGR) and total number of nymphs). On the other hand, data obtained for the non-persistent virus (CMV) showed an indirect effect of the virus on the vector fitness. Thus, the rm and RGR were higher for aphids grown on CMV-infected plants compared to aphids grown on mock-inoculated plants. Overall, the obtained results are clear examples of how plant viruses could manipulate directly and indirectly vector behaviour to optimize its own dispersion. These results are important for a better understanding of transmission, dispersion and epidemiology of plant viruses transmitted by vectors. This information could be also considered to design or adjust simulation models and dispersion patterns that describe plant virus epidemics.