Probability Steiner trees and maximum parsimony in phylogenetic analysis

The phylogenetic tree (PT) problem has been studied by a number of researchers as an application of the Steiner tree problem, a well-known network optimisation problem. Of all the methods developed for phylogenies the maximum parsimony (MP) method is a simple and commonly used method because it relies on directly observable changes in the input nucleotide or amino acid sequences. In this paper we show that the non-uniqueness of the evolutionary pathways in the MP method leads us to consider a new model of PTs. In this so-called probability representation model, for each site a node in a PT is modelled by a probability distribution of nucleotide or amino acid states, and hence the PT at a given site is a probability Steiner tree, i.e. a Steiner tree in a high-dimensional vector space. In spite of the generality of the probability representation model, in this paper we restrict our study to constructing probability phylogenetic trees (PPT) using the parsimony criterion, as well as discussing and comparing our approach with the classical MP method. We show that for a given input set although the optimal topology as well as the total tree length of the PPT is the same as the PT constructed by the classical MP method, the inferred ancestral states and branch lengths are different and the results given by our method provide a plausible alternative to the classical ones.     

Constructing phylogenetic supernetworks based on simulated annealing

Different partial phylogenetic trees can be derived from different sources of evidence and different methods. One important problem is to summarize these partial phylogenetic trees using a supernetwork. We propose a novel simulated annealing based method called SNSA which uses an optimization function to produce a simple network that still retains a great deal of phylogenetic information. We report the performance of this new method on real and simulated datasets.     

Stochastic search strategy for estimation of maximum likelihood phylogenetic trees

The maximum likelihood (ML) method of phylogenetic tree construction is not as widely used as other tree construction methods (e.g., parsimony, neighbor-joining) because of the prohibitive amount of time required to find the ML tree when the number of sequences under consideration is large. To overcome this difficulty, we propose a stochastic search strategy for estimation of the ML tree that is based on a simulated annealing algorithm. The algorithm works by moving through tree space by way of a "local rearrangement" strategy so that topologies that improve the likelihood are always accepted, whereas those that decrease the likelihood are accepted with a probability that is related to the proportionate decrease in likelihood. Besides greatly reducing the time required to estimate the ML tree, the stochastic search strategy is less likely to become trapped in local optima than are existing algorithms for ML tree estimation. We demonstrate the success of the modified simulated annealing algorithm by comparing it with two existing algorithms (Swofford's PAUP* and Felsenstein's DNAMLK) for several theoretical and real data examples.     

Probabilistic methods outperform parsimony in the phylogenetic analysis of data simulated without a probabilistic model

To understand patterns and processes of the diversification of life, we require an accurate understanding of taxon interrelationships. Recent studies have suggested that analyses of morphological character data using the Bayesian and maximum likelihood Mk model provide phylogenies of higher accuracy compared to parsimony methods. This has proved controversial, particularly studies simulating morphology‐data under Markov models that assume shared branch lengths for characters, as it is claimed this leads to bias favouring the Bayesian or maximum likelihood Mk model over parsimony models which do not explicitly make this assumption. We avoid these potential issues by employing a simulation protocol in which character states are randomly assigned to tips, but datasets are constrained to an empirically realistic distribution of homoplasy as measured by the consistency index. Datasets were analysed with equal weights and implied weights parsimony, and the maximum likelihood and Bayesian Mk model. We find that consistent (low homoplasy) datasets render method choice largely irrelevant, as all methods perform well with high consistency (low homoplasy) datasets, but the largest discrepancies in accuracy occur with low consistency datasets (high homoplasy). In such cases, the Bayesian Mk model is significantly more accurate than alternative models and implied weights parsimony never significantly outperforms the Bayesian Mk model. When poorly supported branches are collapsed, the Bayesian Mk model recovers trees with higher resolution compared to other methods. As it is not possible to assess homoplasy independently of a tree estimate, the Bayesian Mk model emerges as the most reliable approach for categorical morphological analyses.     

Exhaustive conformational search and simulated annealing for models of lattice peptides

We consider simple lattice models for short peptide chains whose states can be exhaustively enumerated to find the lowest energy conformation. Using these exact results and numerical simulations, we compute the distributions for the mean time t_N, required to find the global minimum energy state by simulated annealing (SA), as a function of N, the number of units in the chain. On the basis of scaling arguments, the time t_N, to find the global minimum energy of longer chains, beyond the range covered by exhaustive enumeration, can be estimated. On the basis of the observed exponential increase in folding time of the standard SA algorithms, it is imperative that better algorithms be found for minimizing longer chains. © 1993 John Wiley & Sons, Inc.     

Constructing circular phylogenetic networks from weighted quartets using simulated annealing

In this paper, we present a heuristic algorithm based on the simulated annealing, SAQ-Net, as a method for constructing phylogenetic networks from weighted quartets. Similar to QNet algorithm, SAQ-Net constructs a collection of circular weighted splits of the taxa set. This collection is represented by a split network. In order to show that SAQ-Net performs better than QNet, we apply these algorithm to both the simulated and actual data sets containing salmonella, Bees, Primates and Rubber data sets. Then we draw phylogenetic networks corresponding to outputs of these algorithms using SplitsTree4 and compare the results. We find that SAQ-Net produces a better circular ordering and phylogenetic networks than QNet in most cases. SAQ-Net has been implemented in Matlab and is available for download at http://bioinf.cs.ipm.ac.ir/softwares/saq.net.     

Computationally difficult parsimony problems in phylogenetic systematics

A basic problem in phylogenetic systematics is to construct an evolutionary hypothesis, or phylogenetic tree, from available data for a set of operational taxonomic units (OTUs). Associated with the edges of such trees are weights that usually are interpreted as lengths. Methods proposed for constructing phylogenetic trees attempt to select from among the myriad alternatives a tree that optimizes in some sense the fit of tree topology and edge lengths with the original data. One optimization criterion seeks a most parsimonious tree in which the sum of edge lengths is a minimum. Researchers have failed to develop efficient algorithms to compute optimal solutions for important variations of the parsimonious tree construction problem. Recently Graham & Foulds (1982) proved that a special case of the problem is NP-complete, thus making it unlikely that the computational problem for this case can be solved efficiently. I describe three other parsimonious tree construction problems and prove that they, too, are NP-complete.     

Statistics for phylogenetic trees

This paper poses the problem of estimating and validating phylogenetic trees in statistical terms. The problem is hard enough to warrant several tacks: we reason by analogy to rounding real numbers, and dealing with ranking data. These are both cases where, as in phylogeny the parameters of interest are not real numbers. Then we pose the problem in geometrical terms, using distances and measures on a natural space of trees. We do not solve the problems of inference on tree space, but suggest some coherent ways of tackling them.     

Gene tree parsimony vs uninode coding for phylogenetic reconstruction

have suggested that there are important weaknesses of gene tree parsimony in reconstructing phylogeny in the face of gene duplication, weaknesses that are addressed by method of uninode coding. Here, we discuss Simmons and Freudenstein's criticisms and suggest a number of reasons why gene tree parsimony is preferable to uninode coding. During this discussion we introduce a number of recent developments of gene tree parsimony methods overlooked by Simmons and Freudenstein. Finally, we present a re-analysis of data from that produces a more reasonable phylogeny than that found by Simmons and Freudenstein, suggesting that gene tree parsimony outperforms uninode coding, at least on these data.     

The use of parsimony in testing phylogenetic hypotheses

With the advance of cladistic theory differences in principle between it and other systematic techniques are few but of fundamental importance. In the mechanics of classification they are confined to ranking and the rejection of paraphyletic taxa. In cladistic analysis, leading to cladograms, trees and phylogeny reconstruction, inconsistencies in apparent synapomorphies are said to be resolved using Popper's hypothetico-deductive method together with the principle of parsi However, not only do cladists not use Popper's methodology, which is inconsistent with parsimony, but their use of parsimony is invalid as a test of phylo The only accepted extrinsic test of a classification is that enunciated by John Stuart Mill. It has been claimed that cladistic classifications yield the best results when judged by Mill's criteria, but this is only possibly the case with analytic classifications produced by numerical techniques. No satisfactory test exists in normal (synthetic) cladism for distinguishing synapomorphy from homoplasy. The effects of this are particularly dire in cladograms and classifications involving fossils in which a Stufenreihe arrangement is adopted.     

Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databases

MOTIVATION: Comparative sequence analysis is widely used to study genome function and evolution. This approach first requires the identification of homologous genes and then the interpretation of their homology relationships (orthology or paralogy). To provide help in this complex task, we developed three databases of homologous genes containing sequences, multiple alignments and phylogenetic trees: HOBACGEN, HOVERGEN and HOGENOM. In this paper, we present two new tools for automating the search for orthologs or paralogs in these databases. RESULTS: First, we have developed and implemented an algorithm to infer speciation and duplication events by comparison of gene and species trees (tree reconciliation). Second, we have developed a general method to search in our databases the gene families for which the tree topology matches a peculiar tree pattern. This algorithm of unordered tree pattern matching has been implemented in the FamFetch graphical interface. With the help of a graphical editor, the user can specify the topology of the tree pattern, and set constraints on its nodes and leaves. Then, this pattern is compared with all the phylogenetic trees of the database, to retrieve the families in which one or several occurrences of this pattern are found. By specifying ad hoc patterns, it is therefore possible to identify orthologs in our databases.     

DupTree: a program for large-scale phylogenetic analyses using gene tree parsimony

DupTree is a new software program for inferring rooted species trees from collections of gene trees using the gene tree parsimony approach. The program implements a novel algorithm that significantly improves upon the run time of standard search heuristics for gene tree parsimony, and enables the first truly genome-scale phylogenetic analyses. In addition, DupTree allows users to examine alternate rootings and to weight the reconciliation costs for gene trees. DupTree is an open source project written in C++. Availability: DupTree for Mac OS X, Windows, and Linux along with a sample dataset and an on-line manual are available at http://genome.cs.iastate.edu/CBL/DupTree     

Visualizations for taxonomic and phylogenetic trees

MOTIVATION: Despite substantial efforts to develop and populate the back-ends of biological databases, front-ends to these systems often rely on taxonomic expertise. This research applies techniques from human-computer interaction research to the biodiversity domain. RESULTS: We developed an interactive node-link tool, TaxonTree, illustrating the value of a carefully designed interaction model, animation, and integrated searching and browsing towards retrieval of biological names and other information. Users tested the tool using a new, large integrated dataset of animal names with phylogenetic-based and classification-based tree structures. These techniques also translated well for a tool, DoubleTree, to allow comparison of trees using coupled interaction. Our approaches will be useful not only for biological data but as general portal interfaces.     

Gene tree parsimony for incomplete gene trees: addressing true biological loss

Motivation

Species tree estimation from gene trees can be complicated by gene duplication and loss, and “gene tree parsimony” (GTP) is one approach for estimating species trees from multiple gene trees. In its standard formulation, the objective is to find a species tree that minimizes the total number of gene duplications and losses with respect to the input set of gene trees. Although much is known about GTP, little is known about how to treat inputs containing some incomplete gene trees (i.e., gene trees lacking one or more of the species).

Results

We present new theory for GTP considering whether the incompleteness is due to gene birth and death (i.e., true biological loss) or taxon sampling, and present dynamic programming algorithms that can be used for an exact but exponential time solution for small numbers of taxa, or as a heuristic for larger numbers of taxa. We also prove that the “standard” calculations for duplications and losses exactly solve GTP when incompleteness results from taxon sampling, although they can be incorrect when incompleteness results from true biological loss. The software for the DP algorithm is freely available as open source code at https://github.com/smirarab/DynaDup.

     

Genetic algorithm for large-scale maximum parsimony phylogenetic analysis of proteins

Inferring phylogeny is a difficult computational problem. For example, for only 13 taxa, there are more then 13 billion possible unrooted phylogenetic trees. Heuristics are necessary to minimize the time spent evaluating non-optimal trees. We describe here an approach for heuristic searching, using a genetic algorithm, that can reduce the time required for weighted maximum parsimony phylogenetic inference, especially for data sets involving a large number of taxa. It is the first implementation of a weighted maximum parsimony criterion using amino acid sequences. To validate the weighted criterion, we used an artificial data set and compared it to a number of other phylogenetic methods. Genetic algorithms mimic the natural selection's ability to solve complex problems. We have identified several parameters affecting the genetic algorithm. Methods were developed to validate these parameters, ensuring optimal performance. This approach allows the construction of phylogenetic trees with over 200 taxa in practical time on a regular PC.     

Multipolar consensus for phylogenetic trees

Collections of phylogenetic trees are usually summarized using consensus methods. These methods build a single tree, supposed to be representative of the collection. However, in the case of heterogeneous collections of trees, the resulting consensus may be poorly resolved (strict consensus, majority-rule consensus, ...), or may perform arbitrary choices among mutually incompatible clades, or splits (greedy consensus). Here, we propose an alternative method, which we call the multipolar consensus (MPC). Its aim is to display all the splits having a support above a predefined threshold, in a minimum number of consensus trees, or poles. We show that the problem is equivalent to a graph-coloring problem, and propose an implementation of the method. Finally, we apply the MPC to real data sets. Our results indicate that, typically, all the splits down to a weight of 10% can be displayed in no more than 4 trees. In addition, in some cases, biologically relevant secondary signals, which would not have been present in any of the classical consensus trees, are indeed captured by our method, indicating that the MPC provides a convenient exploratory method for phylogenetic analysis. The method was implemented in a package freely available at http://www.lirmm.fr/~cbonnard/MPC.html     

Fitting models predicting dates of flowering of temperate-zone trees using simulated annealing

The aim of the present study was to test the four commonly used models to predict the dates of flowering of temperate-zone trees, the spring warming, sequential, parallel and alternating models. Previous studies concerning the performance of these models have shown that they were unable to make accurate predictions based on external data. One of the reasons for such inaccuracy may be wrong estimations of the parameters of each model due to the non-convergence of the optimization algorithm towards their maximum likelihood. We proposed to fit these four models using a simulated annealing method which is known to avoid local extrema of any kind of function, and thus is particularly well adapted to fit budburst models, as their likelihood function presents many local maxima. We tested this method using a phenological dataset deduced from aeropalynological data. Annual pollen spectra were used to estimate the dates of flowering of the populations around the sampling station. The results show that simulated annealing provides a better fit than traditional methods. Despite this improvement, classical models still failed to predict external data. We expect the simulated annealing method to allow reliable comparisons among models, leading to a selection of biologically relevant ones.     

Inferring phylogenetic networks by the maximum parsimony criterion: a case study

Horizontal gene transfer (HGT) may result in genes whose evolutionary histories disagree with each other, as well as with the species tree. In this case, reconciling the species and gene trees results in a network of relationships, known as the "phylogenetic network" of the set of species. A phylogenetic network that incorporates HGT consists of an underlying species tree that captures vertical inheritance and a set of edges which model the "horizontal" transfer of genetic material. In a series of papers, Nakhleh and colleagues have recently formulated a maximum parsimony (MP) criterion for phylogenetic networks, provided an array of computationally efficient algorithms and heuristics for computing it, and demonstrated its plausibility on simulated data. In this article, we study the performance and robustness of this criterion on biological data. Our findings indicate that MP is very promising when its application is extended to the domain of phylogenetic network reconstruction and HGT detection. In all cases we investigated, the MP criterion detected the correct number of HGT events required to map the evolutionary history of a gene data set onto the species phylogeny. Furthermore, our results indicate that the criterion is robust with respect to both incomplete taxon sampling and the use of different site substitution matrices. Finally, our results show that the MP criterion is very promising in detecting HGT in chimeric genes, whose evolutionary histories are a mix of vertical and horizontal evolution. Besides the performance analysis of MP, our findings offer new insights into the evolution of 4 biological data sets and new possible explanations of HGT scenarios in their evolutionary history.