On the Structural Difference between the Evolutionary Approach of Young and that of Kandori, Mailath, and Rob

We provide robust examples of symmetric two-player coordination games in normal form that reveal that equilibrium selection by the evolutionary model of Young (1993) is essentially different from equilibrium selection by the evolutionary model of Kandori, Mailath and Rob (1993).

A novel bioinformatics pipeline to discover genes related to arbuscular mycorrhizal symbiosis based on their evolutionary conservation pattern among higher plants.

BACKGROUND: Genes involved in arbuscular mycorrhizal (AM) symbiosis have been identified primarily by mutant screens, followed by identification of the mutated genes (forward genetics). In addition, a number of AM-related genes has been identified by their AM-related expression patterns, and their function has subsequently been elucidated by knock-down or knock-out approaches (reverse genetics). However, genes that are members of functionally redundant gene families, or genes that have a vital function and therefore result in lethal mutant phenotypes, are difficult to identify. If such genes are constitutively expressed and therefore escape differential expression analyses, they remain elusive. The goal of this study was to systematically search for AM-related genes with a bioinformatics strategy that is insensitive to these problems. The central element of our approach is based on the fact that many AM-related genes are conserved only among AM-competent species. RESULTS: Our approach involves genome-wide comparisons at the proteome level of AM-competent host species with non-mycorrhizal species. Using a clustering method we first established orthologous/paralogous relationships and subsequently identified protein clusters that contain members only of the AM-competent species. Proteins of these clusters were then analyzed in an extended set of 16 plant species and ranked based on their relatedness among AM-competent monocot and dicot species, relative to non-mycorrhizal species. In addition, we combined the information on the protein-coding sequence with gene expression data and with promoter analysis. As a result we present a list of yet uncharacterized proteins that show a strongly AM-related pattern of sequence conservation, indicating that the respective genes may have been under selection for a function in AM. Among the top candidates are three genes that encode a small family of similar receptor-like kinases that are related to the S-locus receptor kinases involved in sporophytic self-incompatibility. CONCLUSIONS: We present a new systematic strategy of gene discovery based on conservation of the protein-coding sequence that complements classical forward and reverse genetics. This strategy can be applied to diverse other biological phenomena if species with established genome sequences fall into distinguished groups that differ in a defined functional trait of interest.

A polynomial algorithm for special case of the one-machine scheduling problem with time-lags

The standard one-machine scheduling problem consists in schedulinga set of jobs in one machine which can handle only one job at atime, minimizing the maximum lateness. Each job is available forprocessing at its release date, requires a known processing timeand after finishing the processing, it is delivery after a certaintime. There also can exists precedence constraints between pairsof jobs, requiring that the first jobs must be completed beforethe second job can start. An extension of this problem consistsin assigning a time interval between the processing of the jobsassociated with the precedence constrains, known by finish-starttime-lags. In presence of this constraints, the problem is NP-hardeven if preemption is allowed. In this work, we consider a specialcase of the one-machine preemption scheduling problem with time-lags, where the time-lags have a chain form, and propose apolynomial algorithm to solve it. The algorithm consist in apolynomial number of calls of the preemption version of the LongestTail Heuristic. One of the applicability of the method is to obtainlower bounds for NP-hard one-machine and job-shop schedulingproblems. We present some computational results of thisapplication, followed by some conclusions.

Large-scale evolutionary trends of Acrochordiceratidae Arthaber, 1911 (Ammonoidea, Middle Triassic) and Cope's rule

Directed evolution of life through millions of years, such as increasing adult body size, is one of the most intriguing patterns displayed by fossil lineages. Processes and causes of such evolutionary trends are still poorly understood. Ammonoids (externally shelled marine cephalopods) are well known to have experienced repetitive morphological evolutionary trends of their adult size, shell geometry and ornamentation. This study analyses the evolutionary trends of the family Acrochordiceratidae Arthaber, 1911 from the Early to Middle Triassic (251228 Ma). Exceptionally large and bed-rock-controlled collections of this ammonoid family were obtained from strata of Anisian age (Middle Triassic) in north-west Nevada and north-east British Columbia. They enable quantitative and statistical analyses of its morphological evolutionary trends. This study demonstrates that the monophyletic clade Acrochordiceratidae underwent the classical evolute to involute evolutionary trend (i.e. increasing coiling of the shell), an increase in its shell adult size (conch diameter) and an increase in the indentation of its shell suture shape. These evolutionary trends are statistically robust and seem more or less gradual. Furthermore, they are nonrandom with the sustained shift in the mean, the minimum and the maximum of studied shell characters. These results can be classically interpreted as being constrained by the persistence and common selection pressure on this mostly anagenetic lineage characterized by relatively moderate evolutionary rates. Increasing involution of ammonites is traditionally interpreted by increasing adaptation mostly in terms of improved hydrodynamics. However, this trend in ammonoid geometry can also be explained as a case of Copes rule (increasing adult body size) instead of functional explanation of coiling, because both shell diameter and shell involution are two possible paths for ammonoids to accommodate size increase.

Learning ability and longevity: a symmetrical evolutionary trade-off in Drosophila.

Learning ability can be substantially improved by artificial selection in animals ranging from Drosophila to rats. Thus these species have not used their evolutionary potential with respect to learning ability, despite intuitively expected and experimentally demonstrated adaptive advantages of learning. This suggests that learning is costly, but this notion has rarely been tested. Here we report correlated responses of life-history traits to selection for improved learning in Drosophila melanogaster. Replicate populations selected for improved learning lived on average 15% shorter than the corresponding unselected control populations. They also showed a minor reduction in fecundity late in life and possibly a minor increase in dry adult mass. Selection for improved learning had no effect on egg-to-adult viability, development rate, or desiccation resistance. Because shortened longevity was the strongest correlated response to selection for improved learning, we also measured learning ability in another set of replicate populations that had been selected for extended longevity. In a classical olfactory conditioning assay, these long-lived flies showed an almost 40% reduction in learning ability early in life. This effect disappeared with age. Our results suggest a symmetrical evolutionary trade-off between learning ability and longevity in Drosophila.

Evolutionary genetics of arbuscular mycorrhizal fungi - causes and consequences of multiple genomes in Glomus intraradices

Résumé Les champignons endomycorhiziens arbusculaires (CEA) forment des symbioses avec la plupart des plantes terrestres. Les CEA influencent la croissance des plantes et la biodiversité. Ils sont supposés avoir évolué de manière asexuée pendant au moins 400 millions d'années et aucune diversification morphologique majeure n'a été constatée. Pour ces raisons, les CEA sont considérés comme d'anciens asexués. Très peu d'espèces sont connues actuellement. Les individus de ces champignons contiennent des noyaux génétiquement différents dans un cytoplasme continu. La signification évolutive, la variabilité et la maintenance des génomes multiples au sein des individus sont inconnues. Ce travail a démontré qu'une population du CEA Glomus intraradices est génétiquement très variable. Nous avons conclu que les plantes hôtes plutôt que la différenciation géographique devraient être responsables de cette grande diversité. Puis nous avons cherché l'existence de recombinaison entre génotypes dans une population. Nous avons détecté un groupe recombinant au sein de la population, ce qui met en doute l'état d'anciens asexués des CEA. Nous avons également détecté l'occurrence de fusions d'hyphes et l'échange de noyaux entre isolats génétiquement différents. La descendance hybride issue de cet échange était viable et distincte phénotypiquement des isolats parentaux. En résumé, ce travail identifie des événements cruciaux dans le cycle de vie des CEA qui ont le potentiel d'influencer l'évolution de génomes multiples. L'étude des conséquences de ces événements sur les interactions avec les plantes hôtes pourrait éclaircir significativement la compréhension de la symbiose entre plantes et CEA. Abstract Arbuscular mycorrhizal fungi (AMF) are important symbionts of most land plants. AMF influence plant growth and biodiversity. Very few extant species are described. AMF are thought to have evolved asexually for at least 400 million years and no major morphological diversification has occurred. Due to these reasons, they were termed `ancient asexuals'. Fungal individuals harbour genetically different nuclei in a continuous cytoplasm. The variability, maintenance and evolutionary significance of multiple genomes within individuals are unknown. This work showed that a population of the AMF Glomus intraradices harbours very high genetic diversity. We concluded that host plants rather than geographic differentiation were responsible for this diversity. Furthermore, we investigated whether recombination occurred among genotypes of a G. intraradices population. The identification of a core group of recombining genotypes in the population refutes the assumption of ancient asexuality in AMF. We found that genetically different isolates can form hyphal fusions and exchange nuclei. The hybrid progeny produced by the exchange was viable and phenotypically distinct from the parental isolates. Taken together, this work provided evidence for key events in the AMF life cycle, that influence the evolution of multiple genomes. Studying the consequences of these events on the interaction with host plants may significantly further the understanding of the AMF-plant symbiosis.

Assigning proctors to exams with scatter search

In this paper we present an algorithm to assign proctors toexams. This NP-hard problem is related to the generalized assignmentproblem with multiple objectives. The problem consists of assigningteaching assistants to proctor final exams at a university. We formulatethis problem as a multiobjective integer program (IP) with a preferencefunction and a workload-fairness function. We then consider also a weightedobjective that combines both functions. We develop a scatter searchprocedure and compare its outcome with solutions found by solving theIP model with CPLEX 6.5. Our test problems are real instances from aUniversity in Spain.

Implementation, elimination of weakly dominated strategies and evolutionary dynamics

This paper is concerned with the realism of mechanisms that implementsocial choice functions in the traditional sense. Will agents actually playthe equilibrium assumed by the analysis? As an example, we study theconvergence and stability properties of Sj\"ostr\"om's (1994) mechanism, onthe assumption that boundedly rational players find their way to equilibriumusing monotonic learning dynamics and also with fictitious play. Thismechanism implements most social choice functions in economic environmentsusing as a solution concept the iterated elimination of weakly dominatedstrategies (only one round of deletion of weakly dominated strategies isneeded). There are, however, many sets of Nash equilibria whose payoffs maybe very different from those desired by the social choice function. Withmonotonic dynamics we show that many equilibria in all the sets ofequilibria we describe are the limit points of trajectories that havecompletely mixed initial conditions. The initial conditions that lead tothese equilibria need not be very close to the limiting point. Furthermore,even if the dynamics converge to the ``right'' set of equilibria, it stillcan converge to quite a poor outcome in welfare terms. With fictitious play,if the agents have completely mixed prior beliefs, beliefs and play convergeto the outcome the planner wants to implement.

Communication, coordination and efficiency in evolutionary one-population models

We analyze the role of commitment in pre-play communication for ensuringefficient evolutionarily stable outcomes in coordination games. All players are a priori identical as they are drawn from the same population. In games where efficient outcomes can be reached by players coordinating on the same action we find commitment to be necessary to enforce efficiency. In games where efficienct outcomes only result from play of different actions, communication without commitment is most effective although efficiency can no longer be guaranteed. Only when there are many messages then inefficient outcomes are negligible as their basins of attraction become very small.

Phenetic, biogeographical, and evolutionary study ofOrnithogalum subg.Heliocharmos (Hyacinthaceae) in the western Mediterranean basin

A macromorphological study is made on taxa of the genusOrnithogalum subg.Heliocharmos in North Africa, Spain, and France. The results obtained are consistent with data from cytogenetics, reproductive biology and strategies of reproduction. They allow the retention of two species:O. algeriense and O. umbellatum. A biogeographical and phylogenetic interpretation of the subgenus is proposed for the western Mediterranean. Theoretical views on phenetics are discussed.

On the efficiency and sensitivity of a pyramidal classification algorithm

In this paper we propose a Pyramidal Classification Algorithm,which together with an appropriate aggregation index producesan indexed pseudo-hierarchy (in the strict sense) withoutinversions nor crossings. The computer implementation of thealgorithm makes it possible to carry out some simulation testsby Monte Carlo methods in order to study the efficiency andsensitivity of the pyramidal methods of the Maximum, Minimumand UPGMA. The results shown in this paper may help to choosebetween the three classification methods proposed, in order toobtain the classification that best fits the original structureof the population, provided we have an a priori informationconcerning this structure.