Data size sufficiency analyses of haplotype inference algortihms

We present experimental and theoretical analyses of data requirements for haplotype inference algorithms. Our experiments include a broad range of problem sizes under two standard models of tree distribution and were designed to yield statistically robust results despite the size of the sample space. Our results validate Gusfield's conjecture that a population size of n log n is required to give (with high probability) sufficient information to deduce the n haplotypes and their complete evolutionary history. The experimental results inspired our experimental finding with theoretical bounds on the population size. We also analyze the population size required to deduce some fixed fraction of the evolutionary history of a set of n haplotypes and establish linear bounds on the required sample size. These linear bounds are also shown theoretically.

Evolutionary switch and genetic convergence on rbcL following the evolution of C4 photosynthesis.

Rubisco is responsible for the fixation of CO2 into organic compounds through photosynthesis and thus has a great agronomic importance. It is well established that this enzyme suffers from a slow catalysis, and its low specificity results into photorespiration, which is considered as an energy waste for the plant. However, natural variations exist, and some Rubisco lineages, such as in C4 plants, exhibit higher catalytic efficiencies coupled to lower specificities. These C4 kinetics could have evolved as an adaptation to the higher CO2 concentration present in C4 photosynthetic cells. In this study, using phylogenetic analyses on a large data set of C3 and C4 monocots, we showed that the rbcL gene, which encodes the large subunit of Rubisco, evolved under positive selection in independent C4 lineages. This confirms that selective pressures on Rubisco have been switched in C4 plants by the high CO2 environment prevailing in their photosynthetic cells. Eight rbcL codons evolving under positive selection in C4 clades were involved in parallel changes among the 23 independent monocot C4 lineages included in this study. These amino acids are potentially responsible for the C4 kinetics, and their identification opens new roads for human-directed Rubisco engineering. The introgression of C4-like high-efficiency Rubisco would strongly enhance C3 crop yields in the future CO2-enriched atmosphere.

Multi-scale support vector algorithms for hot spot detection and modelling

The algorithmic approach to data modelling has developed rapidly these last years, in particular methods based on data mining and machine learning have been used in a growing number of applications. These methods follow a data-driven methodology, aiming at providing the best possible generalization and predictive abilities instead of concentrating on the properties of the data model. One of the most successful groups of such methods is known as Support Vector algorithms. Following the fruitful developments in applying Support Vector algorithms to spatial data, this paper introduces a new extension of the traditional support vector regression (SVR) algorithm. This extension allows for the simultaneous modelling of environmental data at several spatial scales. The joint influence of environmental processes presenting different patterns at different scales is here learned automatically from data, providing the optimum mixture of short and large-scale models. The method is adaptive to the spatial scale of the data. With this advantage, it can provide efficient means to model local anomalies that may typically arise in situations at an early phase of an environmental emergency. However, the proposed approach still requires some prior knowledge on the possible existence of such short-scale patterns. This is a possible limitation of the method for its implementation in early warning systems. The purpose of this paper is to present the multi-scale SVR model and to illustrate its use with an application to the mapping of Cs137 activity given the measurements taken in the region of Briansk following the Chernobyl accident.

The origins of C4 grasslands: integrating evolutionary and ecosystem science.

The evolution of grasses using C4 photosynthesis and their sudden rise to ecological dominance 3 to 8 million years ago is among the most dramatic examples of biome assembly in the geological record. A growing body of work suggests that the patterns and drivers of C4 grassland expansion were considerably more complex than originally assumed. Previous research has benefited substantially from dialog between geologists and ecologists, but current research must now integrate fully with phylogenetics. A synthesis of grass evolutionary biology with grassland ecosystem science will further our knowledge of the evolution of traits that promote dominance in grassland systems and will provide a new context in which to evaluate the relative importance of C4 photosynthesis in transforming ecosystems across large regions of Earth.

Two's company, three's a crowd: experimental evaluation of the evolutionary maintenance of trioecy in Mercurialis annua (Euphorbiaceae).

Trioecy is an uncommon sexual system in which males, females, and hermaphrodites co-occur as three clearly different gender classes. The evolutionary stability of trioecy is unclear, but would depend on factors such as hermaphroditic sex allocation and rates of outcrossing vs. selfing. Here, trioecious populations of Mercurialis annua are described for the first time. We examined the frequencies of females, males and hermaphrodites across ten natural populations and evaluated the association between the frequency of females and plant densities. Previous studies have shown that selfing rates in this species are density-dependent and are reduced in the presence of males, which produce substantially more pollen than hermaphrodites. Accordingly, we examined the evolutionary stability of trioecy using an experiment in which we (a) indirectly manipulated selfing rates by altering plant densities and the frequency of males in a fully factorial manner across 20 experimental plots and (b) examined the effect of these manipulations on the frequency of the three sex phenotypes in the next generation of plants. In the parental generation, we measured the seed and pollen allocations of hermaphrodites and compared them with allocations by unisexual plants. In natural populations, females occurred at higher frequencies in denser patches, a finding consistent with our expectations. Under our experimental conditions, however, no combination of plant densities and male frequencies was associated with increased frequencies of females. Our results suggest that the factors that regulate female frequencies in trioecious populations of M. annua are independent of those regulating male frequencies (density), and that the stable co-existence of all three sex phenotypes within populations is unlikely.

Evidence for transcript networks composed of chimeric RNAs in human cells.

The classic organization of a gene structure has followed the Jacob and Monod bacterial gene model proposed more than 50 years ago. Since then, empirical determinations of the complexity of the transcriptomes found in yeast to human has blurred the definition and physical boundaries of genes. Using multiple analysis approaches we have characterized individual gene boundaries mapping on human chromosomes 21 and 22. Analyses of the locations of the 5' and 3' transcriptional termini of 492 protein coding genes revealed that for 85% of these genes the boundaries extend beyond the current annotated termini, most often connecting with exons of transcripts from other well annotated genes. The biological and evolutionary importance of these chimeric transcripts is underscored by (1) the non-random interconnections of genes involved, (2) the greater phylogenetic depth of the genes involved in many chimeric interactions, (3) the coordination of the expression of connected genes and (4) the close in vivo and three dimensional proximity of the genomic regions being transcribed and contributing to parts of the chimeric RNAs. The non-random nature of the connection of the genes involved suggest that chimeric transcripts should not be studied in isolation, but together, as an RNA network.

Fast numerical algorithms for the computation of invariant tori in Hamiltonian systems

In this paper, we develop numerical algorithms that use small requirements of storage and operations for the computation of invariant tori in Hamiltonian systems (exact symplectic maps and Hamiltonian vector fields). The algorithms are based on the parameterization method and follow closely the proof of the KAM theorem given in [LGJV05] and [FLS07]. They essentially consist in solving a functional equation satisfied by the invariant tori by using a Newton method. Using some geometric identities, it is possible to perform a Newton step using little storage and few operations. In this paper we focus on the numerical issues of the algorithms (speed, storage and stability) and we refer to the mentioned papers for the rigorous results. We show how to compute efficiently both maximal invariant tori and whiskered tori, together with the associated invariant stable and unstable manifolds of whiskered tori. Moreover, we present fast algorithms for the iteration of the quasi-periodic cocycles and the computation of the invariant bundles, which is a preliminary step for the computation of invariant whiskered tori. Since quasi-periodic cocycles appear in other contexts, this section may be of independent interest. The numerical methods presented here allow to compute in a unified way primary and secondary invariant KAM tori. Secondary tori are invariant tori which can be contracted to a periodic orbit. We present some preliminary results that ensure that the methods are indeed implementable and fast. We postpone to a future paper optimized implementations and results on the breakdown of invariant tori.

Evolutionary genomics and HIV restriction factors.

PURPOSE OF REVIEW: To provide updated insights into innate antiviral immunity and highlight prototypical evolutionary features of well characterized HIV restriction factors. RECENT FINDINGS: Recently, a new HIV restriction factor, Myxovirus resistance 2, has been discovered and the region/residue responsible for its activity identified using an evolutionary approach. Furthermore, IFI16, an innate immunity protein known to sense several viruses, has been shown to contribute to the defense to HIV-1 by causing cell death upon sensing HIV-1 DNA. SUMMARY: Restriction factors against HIV show characteristic signatures of positive selection. Different patterns of accelerated sequence evolution can distinguish antiviral strategies--offense or defence--as well as the level of specificity of the antiviral properties. Sequence analysis of primate orthologs of restriction factors serves to localize functional domains and sites responsible for antiviral action. We use recent discoveries to illustrate how evolutionary genomic analyses help identify new antiviral genes and their mechanisms of action.

New insights into the phylogenetics and biogeography of Arum (Araceae): unravelling its evolutionary history

The heat- and odour-producing genus Arum (Araceae) has interested scientists for centuries. This long-term interest has allowed a deep knowledge of some complex processes, such as the physiology and dynamics of its characteristic lure-and-trap pollination system, to be built up. However, mainly because of its large distributional range and high degree of morphological variation, species' limits and relationships are still under discussion. Today, the genus comprises 28 species subdivided into two subgenera, two sections and six subsections. In this study, the phylogeny of the genus is inferred on the basis of four plastid regions, and the evolution of several morphological characters is investigated. Our phylogenetic hypothesis is not in agreement with the current infrageneric classification of the genus and challenges the monophyly of several species. This demonstrates the need for a new infrageneric classification based on characters reflecting the evolution of this enigmatic genus. To investigate the biogeography of Arum deeply, further spatiotemporal analyses were performed, addressing the importance of the Mediterranean basin in the diversification of Arum. Our results suggest that its centre of origin was the European-Aegean region, and that major diversification happened during the last 10 Myr.

The evolution of inbred social systems in spiders and other organisms: from short-term gains to long-term evolutionary dead-ends?

The question of why some social systems have evolved close inbreeding is particularly intriguing given expected short- and long-term negative effects of this breeding system. Using social spiders as a case study, we quantitatively show that the potential costs of avoiding inbreeding through dispersal and solitary living could have outweighed the costs of inbreeding depression in the origin of inbred spider sociality. We further review the evidence that despite being favored in the short term, inbred spider sociality may constitute in the long run an evolutionary dead end. We also review other cases, such as the naked mole rats and some bark and ambrosia beetles, mites, psocids, thrips, parasitic ants, and termites, in which inbreeding and sociality are associated and the evidence for and against this breeding system being, in general, an evolutionary dead end.

Gains from switching and evolutionary stability in multi-player matrix games.

In this paper we unify, simplify, and extend previous work on the evolutionary dynamics of symmetric N-player matrix games with two pure strategies. In such games, gains from switching strategies depend, in general, on how many other individuals in the group play a given strategy. As a consequence, the gain function determining the gradient of selection can be a polynomial of degree N-1. In order to deal with the intricacy of the resulting evolutionary dynamics, we make use of the theory of polynomials in Bernstein form. This theory implies a tight link between the sign pattern of the gains from switching on the one hand and the number and stability of the rest points of the replicator dynamics on the other hand. While this relationship is a general one, it is most informative if gains from switching have at most two sign changes, as is the case for most multi-player matrix games considered in the literature. We demonstrate that previous results for public goods games are easily recovered and extended using this observation. Further examples illustrate how focusing on the sign pattern of the gains from switching obviates the need for a more involved analysis.

A Survey of Active Learning Algorithms for Supervised Remote Sensing Image Classification

Defining an efficient training set is one of the most delicate phases for the success of remote sensing image classification routines. The complexity of the problem, the limited temporal and financial resources, as well as the high intraclass variance can make an algorithm fail if it is trained with a suboptimal dataset. Active learning aims at building efficient training sets by iteratively improving the model performance through sampling. A user-defined heuristic ranks the unlabeled pixels according to a function of the uncertainty of their class membership and then the user is asked to provide labels for the most uncertain pixels. This paper reviews and tests the main families of active learning algorithms: committee, large margin, and posterior probability-based. For each of them, the most recent advances in the remote sensing community are discussed and some heuristics are detailed and tested. Several challenging remote sensing scenarios are considered, including very high spatial resolution and hyperspectral image classification. Finally, guidelines for choosing the good architecture are provided for new and/or unexperienced user.

The snail hosts of schistosomiasis: some evolutionary and ecological perspectives in relation to control

Despite opportunities for radiation provided by spatio-temporal isolation, the basic morphological plan of pulmonate snails has remained conservative. In consequence of the resulting dearth of morphological characters and their plasticity, there is a case for using biochemical characters such as exogenous chemicals released by the snails (e.g. amino acids) and their chemoreception niche as taxonomic aids to classify snails of medical importance. As these same chemicals are used by snails to distinguish conspecifics they could also be used as "environmental antibodies" in controlled release formulations (CRF's) designed to remove target snails in a specific, cost-effective and ecologically acceptable manner. The snails, surface-living bacteria, algae and macrophytic plants are considered as co-evolved, interactive modular systems with strong mutualistic elements. Recently, anthropogenic perturbations such as deforestation, and damming of flowing waters, have benefited these modules whereas others such as river canalization, acid deposition, accumulation of pesticide residues and eutrophication have harmed them. Research is needed to elucidate the factors which limit the growth of snails in primitive habitats, uninfluenced by man, as well as in those subject to harmful anthropogenic factors. The understanding thus gained could be applied to develop cost-effective primary health care strategies to reduce or prevent transmission of schistosomiasis and other water related diseases.