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.

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.

Worldwide sequence conservation of transmission-blocking vaccine candidate Pvs230 in Plasmodium vivax

Pfs230, surface protein of gametocyte/gamete of the human malaria parasite, Plasmodium falciparum, is a prime candidate of malaria transmission-blocking vaccine. Plasmodium vivax has an ortholog of Pfs230 (Pvs230), however, there has been no study in any aspects on Pvs230 to date. To investigate whether Pvs230 can be a vivax malaria transmission-blocking vaccine, we performed evolutionary and population genetic analysis of the Pvs230 gene (pvs230: PVX_003905). Our analysis of Pvs230 and its orthologs in eight Plasmodium species revealed two distinctive parts: an interspecies variable part (IVP) containing species-specific oligopeptide repeats at the N-terminus and a 7.5 kb interspecies conserved part (ICP) containing 14 cysteine-rich domains. Pvs230 was closely related to its orthologs, Pks230 and Pcys230, in monkey malaria parasites. Analysis of 113 pvs230 sequences obtained from worldwide, showed that nucleotide diversity is remarkably low in the non-repeat 8-kb region of pvs230 (theta pi = 0.00118) with 77 polymorphic nucleotide sites, 40 of which results in amino acid replacements. A signature of purifying selection but not of balancing selection was seen on pvs230. Functional and/or structural constraints may limit the level of polymorphism in pvs230. The observed limited polymorphism in pvs230 should ground for utilization of Pvs230 as an effective transmission-blocking vaccine. (C) 2011 Elsevier Ltd. 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 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.

Crop rotation scheduling with adjacency constraints

In this article we propose a 0-1 optimization model to determine a crop rotation schedule for each plot in a cropping area. The rotations have the same duration in all the plots and the crops are selected to maximize plot occupation. The crops may have different production times and planting dates. The problem includes planting constraints for adjacent plots and also for sequences of crops in the rotations. Moreover, cultivating crops for green manuring and fallow periods are scheduled into each plot. As the model has, in general, a great number of constraints and variables, we propose a heuristics based on column generation. To evaluate the performance of the model and the method, computational experiments using real-world data were performed. The solutions obtained indicate that the method generates good results.

Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints

This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. (C) 2007 Elsevier B.V. All rights reserved.

Evolutionary model trees for handling continuous classes in machine learning

Model trees are a particular case of decision trees employed to solve regression problems. They have the advantage of presenting an interpretable output, helping the end-user to get more confidence in the prediction and providing the basis for the end-user to have new insight about the data, confirming or rejecting hypotheses previously formed. Moreover, model trees present an acceptable level of predictive performance in comparison to most techniques used for solving regression problems. Since generating the optimal model tree is an NP-Complete problem, traditional model tree induction algorithms make use of a greedy top-down divide-and-conquer strategy, which may not converge to the global optimal solution. In this paper, we propose a novel algorithm based on the use of the evolutionary algorithms paradigm as an alternate heuristic to generate model trees in order to improve the convergence to globally near-optimal solutions. We call our new approach evolutionary model tree induction (E-Motion). We test its predictive performance using public UCI data sets, and we compare the results to traditional greedy regression/model trees induction algorithms, as well as to other evolutionary approaches. Results show that our method presents a good trade-off between predictive performance and model comprehensibility, which may be crucial in many machine learning applications. (C) 2010 Elsevier Inc. All rights reserved.

Observational constraints on the dark energy and dark matter mutual coupling

We examine different phenomenological interaction models for Dark Energy and Dark Matter by performing statistical joint analysis with observational data arising from the 182 Gold type la supernova samples, the shift parameter of the Cosmic Microwave Background given by the three-year Wilkinson Microwave Anisotropy Probe observations, the baryon acoustic oscillation measurement from the Sloan Digital Sky Survey and age estimates of 35 galaxies. Including the time-dependent observable, we add sensitivity of measurement and give complementary results for the fitting. The compatibility among three different data sets seem to imply that the coupling between dark energy and dark matter is a small positive value, which satisfies the requirement to solve the coincidence problem and the second law of thermodynamics, being compatible with previous estimates. (c) 2008 Elsevier B.V. All rights reserved.