Evolutionary history of Ramphastos toucans: Molecular phylogenetics, temporal diversification, and biogeography

The toucan genus Ramphastos (Piciformes: Ramphastidae) has been a model in the formulation of Neotropical paleobiogeographic hypotheses. Weckstein (2005) reported on the phylogenetic history of this genus based on three mitochondrial genes, but some relationships were weakly supported and one of the subspecies of R. vitellinus (citreolaemus) was unsampled. This study expands on Weckstein (2005) by adding more DNA sequence data (including a nuclear marker) and more samples, including R v. citreolaemus. Maximum parsimony, maximum likelihood, and Bayesian methods recovered similar trees, with nodes showing high support. A monophyletic R. vitellinus complex was strongly supported as the sister-group to R. brevis. The results also confirmed that the southeastern and northern populations of R. vitellinus ariel are paraphyletic. X v. citreolaemus is sister to the Amazonian subspecies of the vitellinus complex. Using three protein-coding genes (COI, cytochrome-b and ND2) and interval-calibrated nodes under a Bayesian relaxed-clock framework, we infer that ramphastid genera originated in the middle Miocene to early Pliocene, Ramphastos species originated between late Miocene and early Pleistocene, and intra-specific divergences took place throughout the Pleistocene. Parsimony-based reconstruction of ancestral areas indicated that evolution of the four trans-Andean Ramphastos taxa (R. v. citreolaemus, R. a. swainsonii, R. brevis and R. sulfuratus) was associated with four independent dispersals from the cis-Andean region. The last pulse of Andean uplift may have been important for the evolution of R. sulfuratus, whereas the origin of the other trans-Andean Ramphastos taxa is consistent with vicariance due to drying events in the lowland forests north of the Andes. Estimated rates of molecular evolution were higher than the ""standard"" bird rate of 2% substitutions/site/million years for two of the three genes analyzed (cytochrome-b and ND2). (C) 2009 Elsevier Inc. All rights reserved.

Evolutionary history of Dengue virus type 4: Insights into genotype phylodynamics

Dengue virus type 4 (DENV-4) circulates in tropical and subtropical countries from Asia and the Americas. Despite the importance of dengue virus distribution, little is known about the worldwide viral spread. Following a Bayesian phylogenetic approach we inferred the evolutionary history of 310 isolates sampled from 37 countries during the time period 1956-2008 and the spreading dynamics for genotypes I and II. The region (tropical rainforest biome) comprised by Malaysia-Thailand was the most likely ancestral area from which the serotype has originated and spread. Interestingly, cross-correlation analysis on demographic time series with the Asian sequences showed a statistically significant negative correlation that could be suggestive of competition among genotypes within the same serotype. (C) 2011 Elsevier B.V. All rights reserved.

Replacement of the arginine biosynthesis operon in Xanthomonadales by ateral gene transfer

The role of lateral gene transfer (LGT) in prokaryotes has been shown to rapidly change the genome content, providing new gene tools for environmental adaptation. Features related to pathogenesis and resistance to strong selective conditions have been widely shown to be products of gene transfer between bacteria. The genomes of the gamma-proteobacteria from the genus Xanthomonas, composed mainly of phytopathogens, have potential genomic islands that may represent imprints of such evolutionary processes. In this work, the evolution of genes involved in the pathway responsible for arginine biosynthesis in Xanthomonadales was investigated, and several lines of evidence point to the foreign origin of the arg genes clustered within a potential operon. Their presence inside a potential genomic island, bordered by a tRNA gene, the unusual ranking of sequence similarity, and the atypical phylogenies indicate that the metabolic pathway for arginine biosynthesis was acquired through LGT in the Xanthomonadales group. Moreover, although homologues were also found in Bacteroidetes (Flavobacteria group), for many of the genes analyzed close homologues are detected in different life domains (Eukarya and Archaea), indicating that the source of these arg genes may have been outside the Bacteria clade. The possibility of replacement of a complete primary metabolic pathway by LGT events supports the selfish operon hypothesis and may occur only under very special environmental conditions. Such rare events reveal part of the history of these interesting mosaic Xanthomonadales genomes, disclosing the importance of gene transfer modifying primary metabolism pathways and extending the scenario for bacterial genome evolution.

Evolutionary placement of Xanthomonadales based on conserved protein signature sequences

Xanthomonadales comprises one of the largest phytopathogenic bacterial groups, and is currently classified within the gamma-proteobacteria. However, the phylogenetic placement of this group is not clearly resolved, and the results of different studies contradict one another. In this work, the evolutionary position of Xanthomonadales was determined by analyzing the presence of shared insertions and deletions (INDELs) in highly conserved proteins. Several distinctive insertions found in most of the members of the gamma-proteobacteria are absent in Xanthomonadales and groups such as Legionelalles, Chromatiales, Methylococcales, Thiotrichales and Cardiobacteriales. These INDELs were most likely introduced after the branching of Xanthomonadales from most of the gamma-proteobacteria and provide evidence for the phylogenetic placement of the early gamma-proteobacteria. Moreover, other proteins contain insertions exclusive to the Xanthomonadales order, confirming that this is a monophyletic group and provide important specific genetic markers. Thus, the data presented clearly support the Xanthomonadales group as an independent subdivision, and constitute one of the deepest branching lineage within the gamma-proteobacteria clade. (C) 2009 Elsevier Inc. All rights reserved.

Divergence Involving Global Regulatory Gene Mutations in an Escherichia coli Population Evolving under Phosphate Limitation

Many of the important changes in evolution are regulatory in nature. Sequenced bacterial genomes point to flexibility in regulatory circuits but we do not know how regulation is remodeled in evolving bacteria. Here, we study the regulatory changes that emerge in populations evolving under controlled conditions during experimental evolution of Escherichia coli in a phosphate-limited chemostat culture. Genomes were sequenced from five clones with different combinations of phenotypic properties that coexisted in a population after 37 days. Each of the distinct isolates contained a different mutation in 1 of 3 highly pleiotropic regulatory genes (hfq, spoT, or rpoS). The mutations resulted in dissimilar proteomic changes, consistent with the documented effects of hfq, spoT, and rpoS mutations. The different mutations do share a common benefit, however, in that the mutations each redirect cellular resources away from stress responses that are redundant in a constant selection environment. The hfq mutation lowers several individual stress responses as well the small RNA-dependent activation of rpoS translation and hence general stress resistance. The spoT mutation reduces ppGpp levels, decreasing the stringent response as well as rpoS expression. The mutations in and upstream of rpoS resulted in partial or complete loss of general stress resistance. Our observations suggest that the degeneracy at the core of bacterial stress regulation provides alternative solutions to a common evolutionary challenge. These results can explain phenotypic divergence in a constant environment and also how evolutionary jumps and adaptive radiations involve altered gene regulation.

Phylogeography and evolutionary history of dengue virus type 3

In this study, we revisited the phylogeography of the three of major DENV-3 genotypes and estimated its rate of evolution, based on the analysis of the envelope (E) gene of 200 strains isolated from 31 different countries around the world over a time period of 50 years (1956-2006). Our phylogenetic analysis revealed a geographical subdivision of DENV-3 population in several country-specific clades. Migration patterns of the main DENV-3 genotypes showed that genotype I was mainly circumspect to the maritime portion of Southeast-Asia and South Pacific, genotype 11 stayed within continental areas in South-East Asia, while genotype III spread across Asia, East Africa and into the Americas. No evidence for rampant co-circulation of distinct genotypes in a single locality was found, suggesting that some factors, other than geographic proximity, may limit the continual dispersion and reintroduction of new DENV-3 variants. Estimates of the evolutionary rate revealed no significant differences among major DENV-3 genotypes. The mean evolutionary rate of DENV-3 in areas with long-term endemic transmissions (i.e., Indonesia and Thailand) was similar to that observed in the Americas, which have been experiencing a more recent dengue spread. We estimated the origin of DENV-3 virus around 1890, and the emergence of current diversity of main DENV-3 genotypes between the middle 1960s and the middle 1970s, coinciding with human population growth, urbanization, and massive human movement, and with the description of the first cases of DENV-3 hemorrhagic fever in Asia. (C) 2008 Elsevier B.V. All rights reserved.

Evolutionary dynamics of the immunodominant repeats of the Plasmodium vivax malaria-vaccine candidate circumsporozoite protein (CSP)

The circumsporozoite protein (CSP) of Plasmodium vivax, a major target for malaria vaccine development, has immunodominant B-cell epitopes mapped to central nonapeptide repeat arrays. To determine whether rearrangements of repeat motifs during mitotic DNA replication of parasites create significant CSP diversity under conditions of low effective meiotic recombination rates, we examined csp alleles from sympatric P. vivax isolates systematically sampled from an area of low malaria endemicity in Brazil over a period of 14 months. Nine unique csp types, comprising six different nona peptide repeats, were observed in 45 isolates analyzed. Identical or nearly identical repeats predominated in most arrays, consistent with their recent expansion. We found strong linkage disequilibrium at sites across the chromosome 8 segment flanking the csp locus, consistent with rare meiotic recombination in this region. We conclude that CSP repeat diversity may not be severely constrained by rare meiotic recombination in areas of low malaria endemicity. New repeat variants may be readily created by nonhomologous recombination even when meiotic recombination is rare, with potential implications for CSP-based vaccine development. (C) 2010 Elsevier B.V. All rights reserved.

Sequence diversity and evolutionary dynamics of the dimorphic antigen merozoite surface protein-6 and other Msp genes of Plasmodium falciparum

Immune evasion by Plasmodium falciparum is favored by extensive allelic diversity of surface antigens. Some of them, most notably the vaccine-candidate merozoite surface protein (MSP)-1, exhibit a poorly understood pattern of allelic dimorphism, in which all observed alleles group into two highly diverged allelic families with few or no inter-family recombinants. Here we describe contrasting levels and patterns of sequence diversity in genes encoding three MSP-1-associated surface antigens of P. falciparum, ranging from an ancient allelic dimorphism in the Msp-6 gene to a near lack of allelic divergence in Msp-9 to a more classical multi-allele polymorphism in Msp-7 Other members of the Msp-7 gene family exhibit very little polymorphism in non-repetitive regions. A comparison of P. falciparum Msp-6 sequences to an orthologous sequence from P. reichenowi provided evidence for distinct evolutionary histories of the 5` and 3` segments of the dimorphic region in PfMsp-6, consistent with one dimorphic lineage having arisen from recombination between now-extinct ancestral alleles. In addition. we uncovered two surprising patterns of evolution in repetitive sequence. Firsts in Msp-6, large deletions are associated with (nearly) identical sequence motifs at their borders. Second, a comparison of PfMsp-9 with the P. reichenowi ortholog indicated retention of a significant inter-unit diversity within an 18-base pair repeat within the coding region of P. falciparum, but homogenization in P. reichenowi. (C) 2009 Elsevier B.V. All rights reserved.

Evolutionary history of trypanosomes from South American caiman (Caiman yacare) and African crocodiles inferred by phylogenetic analyses using SSU rDNA and gGAPDH genes

In this study, using a combined data set of SSU rDNA and gGAPDH gene sequences, we provide phylogenetic evidence that supports Clustering of crocodilian trypanosomes from the Brazilian Caiman yacare (Alligatoridae) and Trypanosoma grayi, a species that Circulates between African crocodiles (Crocodilydae) and tsetse flies. In a survey of trypanosomes in Caiman yacare from the Brazilian Pantanal, the prevalence of trypanosome infection was 35% as determined by microhaematocrit and haemoculture, and 9 cultures were obtained. The morphology of trypomastigotes from caiman blood and tissue imprints was compared with those described for other crocodilian trypanosomes. Differences in morphology and growth behaviour of caiman trypanosomes were corroborated by molecular polymorphism that revealed 2 genotypes. Eight isolates were ascribed to genotype Cay01 and 1 to genotype Cay02. Phylogenetic inferences based on concatenated SSU rDNA and gGAPDII sequences showed that caiman isolates are closely related to T. grayi, constituting a well-supported monophyletic assemblage (clade T. grayi). Divergence time estimates based on clade composition, and biogeographical and geological events were used to discuss the relationships between the evolutionary histories of crocodilian trypanosomes and their hosts.

Efficiency issues of evolutionary k-means

One of the top ten most influential data mining algorithms, k-means, is known for being simple and scalable. However, it is sensitive to initialization of prototypes and requires that the number of clusters be specified in advance. This paper shows that evolutionary techniques conceived to guide the application of k-means can be more computationally efficient than systematic (i.e., repetitive) approaches that try to get around the above-mentioned drawbacks by repeatedly running the algorithm from different configurations for the number of clusters and initial positions of prototypes. To do so, a modified version of a (k-means based) fast evolutionary algorithm for clustering is employed. Theoretical complexity analyses for the systematic and evolutionary algorithms under interest are provided. Computational experiments and statistical analyses of the results are presented for artificial and text mining data sets. (C) 2010 Elsevier B.V. All rights reserved.

Evolutionary fuzzy clustering of relational data

This paper is concerned with the computational efficiency of fuzzy clustering algorithms when the data set to be clustered is described by a proximity matrix only (relational data) and the number of clusters must be automatically estimated from such data. A fuzzy variant of an evolutionary algorithm for relational clustering is derived and compared against two systematic (pseudo-exhaustive) approaches that can also be used to automatically estimate the number of fuzzy clusters in relational data. An extensive collection of experiments involving 18 artificial and two real data sets is reported and analyzed. (C) 2011 Elsevier B.V. All rights reserved.

On the efficiency of evolutionary fuzzy clustering

This paper tackles the problem of showing that evolutionary algorithms for fuzzy clustering can be more efficient than systematic (i.e. repetitive) approaches when the number of clusters in a data set is unknown. To do so, a fuzzy version of an Evolutionary Algorithm for Clustering (EAC) is introduced. A fuzzy cluster validity criterion and a fuzzy local search algorithm are used instead of their hard counterparts employed by EAC. Theoretical complexity analyses for both the systematic and evolutionary algorithms under interest are provided. Examples with computational experiments and statistical analyses are also presented.

Evolutionary tuning of SVM parameter values in multiclass problems

Support vector machines (SVMs) were originally formulated for the solution of binary classification problems. In multiclass problems, a decomposition approach is often employed, in which the multiclass problem is divided into multiple binary subproblems, whose results are combined. Generally, the performance of SVM classifiers is affected by the selection of values for their parameters. This paper investigates the use of genetic algorithms (GAs) to tune the parameters of the binary SVMs in common multiclass decompositions. The developed GA may search for a set of parameter values common to all binary classifiers or for differentiated values for each binary classifier. (C) 2008 Elsevier B.V. All rights reserved.

A hybrid case adaptation approach for case-based reasoning

Case-Based Reasoning is a methodology for problem solving based on past experiences. This methodology tries to solve a new problem by retrieving and adapting previously known solutions of similar problems. However, retrieved solutions, in general, require adaptations in order to be applied to new contexts. One of the major challenges in Case-Based Reasoning is the development of an efficient methodology for case adaptation. The most widely used form of adaptation employs hand coded adaptation rules, which demands a significant knowledge acquisition and engineering effort. An alternative to overcome the difficulties associated with the acquisition of knowledge for case adaptation has been the use of hybrid approaches and automatic learning algorithms for the acquisition of the knowledge used for the adaptation. We investigate the use of hybrid approaches for case adaptation employing Machine Learning algorithms. The approaches investigated how to automatically learn adaptation knowledge from a case base and apply it to adapt retrieved solutions. In order to verify the potential of the proposed approaches, they are experimentally compared with individual Machine Learning techniques. The results obtained indicate the potential of these approaches as an efficient approach for acquiring case adaptation knowledge. They show that the combination of Instance-Based Learning and Inductive Learning paradigms and the use of a data set of adaptation patterns yield adaptations of the retrieved solutions with high predictive accuracy.

A hybrid approach to learn with imbalanced classes using evolutionary algorithms

There is an increasing interest in the application of Evolutionary Algorithms (EAs) to induce classification rules. This hybrid approach can benefit areas where classical methods for rule induction have not been very successful. One example is the induction of classification rules in imbalanced domains. Imbalanced data occur when one or more classes heavily outnumber other classes. Frequently, classical machine learning (ML) classifiers are not able to learn in the presence of imbalanced data sets, inducing classification models that always predict the most numerous classes. In this work, we propose a novel hybrid approach to deal with this problem. We create several balanced data sets with all minority class cases and a random sample of majority class cases. These balanced data sets are fed to classical ML systems that produce rule sets. The rule sets are combined creating a pool of rules and an EA is used to build a classifier from this pool of rules. This hybrid approach has some advantages over undersampling, since it reduces the amount of discarded information, and some advantages over oversampling, since it avoids overfitting. The proposed approach was experimentally analysed and the experimental results show an improvement in the classification performance measured as the area under the receiver operating characteristics (ROC) curve.