Variability in the Insect and Plant Adhesins, Mad1 and Mad2, within the Fungal Genus Metarhizium Suggest Plant Adaptation as an Evolutionary Force

Several species of the insect pathogenic fungus Metarhizium are associated with certain plant types and genome analyses suggested a bifunctional lifestyle; as an insect pathogen and as a plant symbiont. Here we wanted to explore whether there was more variation in genes devoted to plant association (Mad2) or to insect association (Mad1) overall in the genus Metarhizium. Greater divergence within the genus Metarhizium in one of these genes may provide evidence for whether host insect or plant is a driving force in adaptation and evolution in the genus Metarhizium. We compared differences in variation in the insect adhesin gene, Mad1, which enables attachment to insect cuticle, and the plant adhesin gene, Mad2, which enables attachment to plants. Overall variation for the Mad1 promoter region (7.1%), Mad1 open reading frame (6.7%), and Mad2 open reading frame (7.4%) were similar, while it was higher in the Mad2 promoter region (9.9%). Analysis of the transcriptional elements within the Mad2 promoter region revealed variable STRE, PDS, degenerative TATA box, and TATA box-like regions, while this level of variation was not found for Mad1. Sequences were also phylogenetically compared to EF-1a, which is used for species identification, in 14 isolates representing 7 different species in the genus Metarhizium. Phylogenetic analysis demonstrated that the Mad2 phylogeny is more congruent with 59 EF-1a than Mad1. This would suggest that Mad2 has diverged among Metarhizium lineages, contributing to clade- and species-specific variation, while it appears that Mad1 has been largely conserved. While other abiotic and biotic factors cannot be excluded in contributing to divergence, these results suggest that plant relationships, rather than insect host, have been a major driving factor in the divergence of the genus Metarhizium.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Predicting Physical, Verbal, Social, Racial, and Sexual Bullying with Individual and Environmental Factors from an Evolutionary Ecological Framework

Evidence exists for subtypes of bullying, but there is a lack of studies simultaneously investigating the factors that influence each subtype. The purpose of my thesis was to investigate how individual and environmental factors independently and interactively predict physical, verbal, social, racial, and sexual bullying using an evolutionary ecological framework. Adolescents (N = 225, M = 14.05, SD = 1.54) completed self-reports on demographics, HEXACO personality, Rothbart’s temperament, parenting, friendship quality, school connectedness, and socio-economic status. Subtypes were predicted by low Honesty-Humility in addition to other personality and demographic factors with the exception of physical bullying, which was predicted by environmental factors. Results suggest adolescents adaptively and selectively use bullying to exploit victims and obtain resources, although the subtype used may depend on individual factors bullies possess within Bronfenbrenner’s microsystem, instead of the meso- and exo- systems. Anti-bullying efforts should target these factors and reinforce alternative strategies to obtain resources.

Variability in the Insect and Plant Adhesins, Mad1 and Mad2, within the Fungal Genus Metarhizium Suggest Plant Adaptation as an Evolutionary Force

Several species of the insect pathogenic fungus Metarhizium are associated with certain plant types and genome analyses suggested a bifunctional lifestyle; as an insect pathogen and as a plant symbiont. Here we wanted to explore whether there was more variation in genes devoted to plant association (Mad2) or to insect association (Mad1) overall in the genus Metarhizium. Greater divergence within the genus Metarhizium in one of these genes may provide evidence for whether host insect or plant is a driving force in adaptation and evolution in the genus Metarhizium. We compared differences in variation in the insect adhesin gene, Mad1, which enables attachment to insect cuticle, and the plant adhesin gene, Mad2, which enables attachment to plants. Overall variation for the Mad1 promoter region (7.1%), Mad1 open reading frame (6.7%), and Mad2 open reading frame (7.4%) were similar, while it was higher in the Mad2 promoter region (9.9%). Analysis of the transcriptional elements within the Mad2 promoter region revealed variable STRE, PDS, degenerative TATA box, and TATA box-like regions, while this level of variation was not found for Mad1. Sequences were also phylogenetically compared to EF-1a, which is used for species identification, in 14 isolates representing 7 different species in the genus Metarhizium. Phylogenetic analysis demonstrated that the Mad2 phylogeny is more congruent with 59 EF-1a than Mad1. This would suggest that Mad2 has diverged among Metarhizium lineages, contributing to clade- and species-specific variation, while it appears that Mad1 has been largely conserved. While other abiotic and biotic factors cannot be excluded in contributing to divergence, these results suggest that plant relationships, rather than insect host, have been a major driving factor in the divergence of the genus Metarhizium.

Characterizing Dynamic Optimization Benchmarks for the Comparison of Multi-Modal Tracking Algorithms

Population-based metaheuristics, such as particle swarm optimization (PSO), have been employed to solve many real-world optimization problems. Although it is of- ten sufficient to find a single solution to these problems, there does exist those cases where identifying multiple, diverse solutions can be beneficial or even required. Some of these problems are further complicated by a change in their objective function over time. This type of optimization is referred to as dynamic, multi-modal optimization. Algorithms which exploit multiple optima in a search space are identified as niching algorithms. Although numerous dynamic, niching algorithms have been developed, their performance is often measured solely on their ability to find a single, global optimum. Furthermore, the comparisons often use synthetic benchmarks whose landscape characteristics are generally limited and unknown. This thesis provides a landscape analysis of the dynamic benchmark functions commonly developed for multi-modal optimization. The benchmark analysis results reveal that the mechanisms responsible for dynamism in the current dynamic bench- marks do not significantly affect landscape features, thus suggesting a lack of representation for problems whose landscape features vary over time. This analysis is used in a comparison of current niching algorithms to identify the effects that specific landscape features have on niching performance. Two performance metrics are proposed to measure both the scalability and accuracy of the niching algorithms. The algorithm comparison results demonstrate the algorithms best suited for a variety of dynamic environments. This comparison also examines each of the algorithms in terms of their niching behaviours and analyzing the range and trade-off between scalability and accuracy when tuning the algorithms respective parameters. These results contribute to the understanding of current niching techniques as well as the problem features that ultimately dictate their success.

Psychopathy and the Ability to Detect Cheaters: An Evolutionary Perspective

This research examined psychopathy as an evolutionary adaptation that involves cheating and deception. I theorized that this strategy should be associated with certain abilities. This research examined the association between psychopathic traits and the ability to detect cheaters, altruism, deception, and psychopathic traits. Results indicated that psychopathic traits were not significantly associated with the ability to detect cheaters or altruism. Results indicated that high Factor 1 psychopathy scores, and low Factor 2 psychopathy scores, were indicative of higher ratings of deception when viewing deceptive videos. Conversely, when viewing truthful videos, Factor 1 was a significant predictor of higher ratings of deception. Finally, our results indicated that total psychopathy scores were associated the ability to identify psychopathic traits in others. Taken together the results provide mixed support for the evolutionary perspective of psychopathy.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

A Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization

Many real-world optimization problems contain multiple (often conflicting) goals to be optimized concurrently, commonly referred to as multi-objective problems (MOPs). Over the past few decades, a plethora of multi-objective algorithms have been proposed, often tested on MOPs possessing two or three objectives. Unfortunately, when tasked with solving MOPs with four or more objectives, referred to as many-objective problems (MaOPs), a large majority of optimizers experience significant performance degradation. The downfall of these optimizers is that simultaneously maintaining a well-spread set of solutions along with appropriate selection pressure to converge becomes difficult as the number of objectives increase. This difficulty is further compounded for large-scale MaOPs, i.e., MaOPs possessing large amounts of decision variables. In this thesis, we explore the challenges of many-objective optimization and propose three new promising algorithms designed to efficiently solve MaOPs. Experimental results demonstrate the proposed optimizers to perform very well, often outperforming state-of-the-art many-objective algorithms.

Models, algorithms, and heuristics for multiobjetive commercial territory design.

Tesis (Doctor en Ingeniería de Sistemas) UANL, 2010.

Models and algorithms for transit network planning.

Tesis (Doctor en Ingeniería con Especialidad en Ingeniería de Sistemas) UANL, 2012.

Conception des réseaux maillés sans fil à multiples-radios multiples-canaux

Généralement, les problèmes de conception de réseaux consistent à sélectionner les arcs et les sommets d’un graphe G de sorte que la fonction coût est optimisée et l’ensemble de contraintes impliquant les liens et les sommets dans G sont respectées. Une modification dans le critère d’optimisation et/ou dans l’ensemble de contraintes mène à une nouvelle représentation d’un problème différent. Dans cette thèse, nous nous intéressons au problème de conception d’infrastructure de réseaux maillés sans fil (WMN- Wireless Mesh Network en Anglais) où nous montrons que la conception de tels réseaux se transforme d’un problème d’optimisation standard (la fonction coût est optimisée) à un problème d’optimisation à plusieurs objectifs, pour tenir en compte de nombreux aspects, souvent contradictoires, mais néanmoins incontournables dans la réalité. Cette thèse, composée de trois volets, propose de nouveaux modèles et algorithmes pour la conception de WMNs où rien n’est connu à l’ avance. Le premiervolet est consacré à l’optimisation simultanée de deux objectifs équitablement importants : le coût et la performance du réseau en termes de débit. Trois modèles bi-objectifs qui se différent principalement par l’approche utilisée pour maximiser la performance du réseau sont proposés, résolus et comparés. Le deuxième volet traite le problème de placement de passerelles vu son impact sur la performance et l’extensibilité du réseau. La notion de contraintes de sauts (hop constraints) est introduite dans la conception du réseau pour limiter le délai de transmission. Un nouvel algorithme basé sur une approche de groupage est proposé afin de trouver les positions stratégiques des passerelles qui favorisent l’extensibilité du réseau et augmentent sa performance sans augmenter considérablement le coût total de son installation. Le dernier volet adresse le problème de fiabilité du réseau dans la présence de pannes simples. Prévoir l’installation des composants redondants lors de la phase de conception peut garantir des communications fiables, mais au détriment du coût et de la performance du réseau. Un nouvel algorithme, basé sur l’approche théorique de décomposition en oreilles afin d’installer le minimum nombre de routeurs additionnels pour tolérer les pannes simples, est développé. Afin de résoudre les modèles proposés pour des réseaux de taille réelle, un algorithme évolutionnaire (méta-heuristique), inspiré de la nature, est développé. Finalement, les méthodes et modèles proposés on été évalués par des simulations empiriques et d’événements discrets.

Approches algorithmiques pour l’inférence d’histoires de duplication en tandem avec inversions et délétions pour des familles multigéniques

[Français] Une fraction importante des génomes eucaryotes est constituée de Gènes Répétés en Tandem (GRT). Un mécanisme fondamental dans l’évolution des GRT est la recombinaison inégale durant la méiose, entrainant la duplication locale (en tandem) de segments chromosomiques contenant un ou plusieurs gènes adjacents. Différents algorithmes ont été proposés pour inférer une histoire de duplication en tandem pour un cluster de GRT. Cependant, leur utilisation est limitée dans la pratique, car ils ne tiennent pas compte d’autres événements évolutifs pourtant fréquents, comme les inversions, les duplications inversées et les délétions. Cette thèse propose différentes approches algorithmiques permettant d’intégrer ces événements dans le modèle de duplication en tandem classique. Nos contributions sont les suivantes: • Intégrer les inversions dans un modèle de duplication en tandem simple (duplication d’un gène à la fois) et proposer un algorithme exact permettant de calculer le nombre minimal d’inversions s’étant produites dans l’évolution d’un cluster de GRT. • Généraliser ce modèle pour l’étude d’un ensemble de clusters orthologues dans plusieurs espèces. • Proposer un algorithme permettant d’inférer l’histoire évolutive d’un cluster de GRT en tenant compte des duplications en tandem, duplications inversées, inversions et délétions de segments chromosomiques contenant un ou plusieurs gènes adjacents.

Algorithmes pour la réconciliation d’un arbre de gènes avec un arbre d’espèces

Une réconciliation entre un arbre de gènes et un arbre d’espèces décrit une histoire d’évolution des gènes homologues en termes de duplications et pertes de gènes. Pour inférer une réconciliation pour un arbre de gènes et un arbre d’espèces, la parcimonie est généralement utilisée selon le nombre de duplications et/ou de pertes. Les modèles de réconciliation sont basés sur des critères probabilistes ou combinatoires. Le premier article définit un modèle combinatoire simple et général où les duplications et les pertes sont clairement identifiées et la réconciliation parcimonieuse n’est pas la seule considérée. Une architecture de toutes les réconciliations est définie et des algorithmes efficaces (soit de dénombrement, de génération aléatoire et d’exploration) sont développés pour étudier les propriétés combinatoires de l’espace de toutes les réconciliations ou seulement les plus parcimonieuses. Basée sur le processus classique nommé naissance-et-mort, un algorithme qui calcule la vraisemblance d’une réconciliation a récemment été proposé. Le deuxième article utilise cet algorithme avec les outils combinatoires décrits ci-haut pour calculer efficacement (soit approximativement ou exactement) les probabilités postérieures des réconciliations localisées dans le sous-espace considéré. Basé sur des taux réalistes (selon un modèle probabiliste) de duplication et de perte et sur des données réelles/simulées de familles de champignons, nos résultats suggèrent que la masse probabiliste de toute l’espace des réconciliations est principalement localisée autour des réconciliations parcimonieuses. Dans un contexte d’approximation de la probabilité d’une réconciliation, notre approche est une alternative intéressante face aux méthodes MCMC et peut être meilleure qu’une approche sophistiquée, efficace et exacte pour calculer la probabilité d’une réconciliation donnée. Le problème nommé Gene Tree Parsimony (GTP) est d’inférer un arbre d’espèces qui minimise le nombre de duplications et/ou de pertes pour un ensemble d’arbres de gènes. Basé sur une approche qui explore tout l’espace des arbres d’espèces pour les génomes considérés et un calcul efficace des coûts de réconciliation, le troisième article décrit un algorithme de Branch-and-Bound pour résoudre de façon exacte le problème GTP. Lorsque le nombre de taxa est trop grand, notre algorithme peut facilement considérer des relations prédéfinies entre ensembles de taxa. Nous avons testé notre algorithme sur des familles de gènes de 29 eucaryotes.

Statistical potentials for evolutionary studies

Les séquences protéiques naturelles sont le résultat net de l’interaction entre les mécanismes de mutation, de sélection naturelle et de dérive stochastique au cours des temps évolutifs. Les modèles probabilistes d’évolution moléculaire qui tiennent compte de ces différents facteurs ont été substantiellement améliorés au cours des dernières années. En particulier, ont été proposés des modèles incorporant explicitement la structure des protéines et les interdépendances entre sites, ainsi que les outils statistiques pour évaluer la performance de ces modèles. Toutefois, en dépit des avancées significatives dans cette direction, seules des représentations très simplifiées de la structure protéique ont été utilisées jusqu’à présent. Dans ce contexte, le sujet général de cette thèse est la modélisation de la structure tridimensionnelle des protéines, en tenant compte des limitations pratiques imposées par l’utilisation de méthodes phylogénétiques très gourmandes en temps de calcul. Dans un premier temps, une méthode statistique générale est présentée, visant à optimiser les paramètres d’un potentiel statistique (qui est une pseudo-énergie mesurant la compatibilité séquence-structure). La forme fonctionnelle du potentiel est par la suite raffinée, en augmentant le niveau de détails dans la description structurale sans alourdir les coûts computationnels. Plusieurs éléments structuraux sont explorés : interactions entre pairs de résidus, accessibilité au solvant, conformation de la chaîne principale et flexibilité. Les potentiels sont ensuite inclus dans un modèle d’évolution et leur performance est évaluée en termes d’ajustement statistique à des données réelles, et contrastée avec des modèles d’évolution standards. Finalement, le nouveau modèle structurellement contraint ainsi obtenu est utilisé pour mieux comprendre les relations entre niveau d’expression des gènes et sélection et conservation de leur séquence protéique.