The effect of natural selection on the performance of maximum parsimony

Background  

Maximum parsimony is one of the most commonly used and extensively studied phylogeny reconstruction methods. While current evaluation methodologies such as computer simulations provide insight into how well maximum parsimony reconstructs phylogenies, they tell us little about how well maximum parsimony performs on taxa drawn from populations of organisms that evolved subject to natural selection in addition to the random factors of drift and mutation. It is clear that natural selection has a significant impact on Among Site Rate Variation (ASRV) and the rate of accepted substitutions; that is, accepted mutations do not occur with uniform probability along the genome and some substitutions are more likely to occur than other substitutions. However, little is know about how ASRV and non-uniform character substitutions impact the performance of reconstruction methods such as maximum parsimony. To gain insight into these issues, we study how well maximum parsimony performs with data generated by Avida, a digital life platform where populations of digital organisms evolve subject to natural selective pressures.     

On the best evolutionary rate for phylogenetic analysis

The effect of the evolutionary rate of a gene on the accuracy of phylogeny reconstruction was examined by computer stimulation. The evolutionary rate is measured by the tree length, that is, the expected total number of nucleotide substitutions per site on the phylogeny. DNA sequence data were simulated using both fixed trees with specified branch lengths and random trees with branch lengths generated from a model of cladogenesis. The parsimony and likelihood methods were used for phylogeny reconstruction, and the proportion of correctly recovered branch partitions by each method was estimated. Phylogenetic methods including parsimony appear quite tolerant of multiple substitutions at the same site. The optimum levels of sequence divergence were even higher than upper limits previously suggested for saturation of substitutions, indicating that the problem of saturation may have been exaggerated. Instead, the lack of information at low levels of divergence should be seriously considered in evaluation of a gene's phylogenetic utility, especially when the gene sequence is short. The performance of parsimony, relative to that of likelihood, does not necessarily decrease with the increase of the evolutionary rate.     

Testing for treeness: lateral gene transfer,phylogenetic inference,and model selection

A phylogeny that allows for lateral gene transfer (LGT) can be thought of as a strictly branching tree (all of whose branches are vertical) to which lateral branches have been added. Given that the goal of phylogenetics is to depict evolutionary history, we should look for the best supported phylogenetic network and not restrict ourselves to considering trees. However, the obvious extensions of popular tree-based methods such as maximum parsimony and maximum likelihood face a serious problem—if we judge networks by fit to data alone, networks that have lateral branches will always fit the data at least as well as any network that restricts itself to vertical branches. This is analogous to the well-studied problem of overfitting data in the curve-fitting problem. Analogous problems often have analogous solutions and we propose to treat network inference as a case of model selection and use the Akaike Information Criterion (AIC). Strictly tree-like networks are more parsimonious than those that postulate lateral as well as vertical branches. This leads to the conclusion that we should not always infer LGT events whenever it would improve our fit-to-data, but should do so only when the improved fit is larger than the penalty for adding extra lateral branches.     

Parallelism,parsimony, and the phytogeny of the lemuridae

In spite of the increasing popularity of cladistic methods in studies of primate systematics, few authors have investigated the effects of parallel evolution when such methods are applied to empirical data. To counter the effects of parallelism, cladistic techniques rely on the principle of evolutionary parsimony. When parsimony procedures are used to reconstruct the phylogeny of the Lemuridae, nine highly parsimonious phylogenies can be deduced. Further choice among these competing hypotheses of relationship is determined by the extent to which one embraces the parsimony principle. The phylogeny obtained by the most rigorous adherence to the parsimony principle is one which is wholly consistent with traditional evolutionary classifications of the Lemuridae. Moderate levels of parallelism can lead to the generation of several plausible, alternative phylogenetic hypotheses; less than 25% of the characters analyzed here need have evolved in parallel, yet they are largely responsible for the ambiguity of the nine different lemurid phylogenies. This suggests that phylogeny reconstructions based entirely on cladistic methods do not provide a suitable basis for the construction of classifications for groups such as the order Primates, where the degree of parallelism is likely to be quite high.     

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.     

Short quartet puzzling: a new quartet-based phylogeny reconstruction algorithm.

Quartet-based phylogeny reconstruction methods, such as Quartet Puzzling, were introduced in the hope that they might be competitive with maximum likelihood methods, without being as computationally intensive. However, despite the numerous quartet-based methods that have been developed, their performance in simulation has been disappointing. In particular, Ranwez and Gascuel, the developers of one of the best quartet methods, conjecture that quartet-based methods have inherent limitations that make them unable to produce trees as accurate as neighbor joining or maximum parsimony. In this paper, we present Short Quartet Puzzling, a new quartet-based phylogeny reconstruction algorithm, and we demonstrate the improved topological accuracy of the new method over maximum parsimony and neighbor joining, disproving the conjecture of Ranwez and Gascuel. We also show a dramatic improvement over Quartet Puzzling. Thus, while our new method is not compared to any ML method (as it is not expected to be as accurate as the best of these), this study shows that quartet methods are not as limited in performance as was previously conjectured, and opens the possibility to further improvements through new algorithmic designs.     

On the Number of Binary Characters Needed to Recover a Phylogeny Using Maximum Parsimony

We give an explicit construction to solve a conjecture of Mike Steel and David Penny that any phylogeny involving N taxa can be recovered unambiguously using on the order of log N binary characters and the method of maximum parsimony. Biologically, this means that homoplasy need not be a deterrent to parsimony methods. Some patterns of homoplasy are phylogenetically informative and can exponentially reduce the amount of data needed to resolve a phylogeny.     

Molecular analysis of the biting midges (Diptera: Ceratopogonidae), based on mitochondrial cytochrome oxidase subunit 2

Sequences from the mitochondrial cytochrome oxidase subunit 2 gene (cox2) were determined for 14 species from the family Ceratopogonidae, representing 12 genera and all five subfamilies, along with six representatives of other nematoceran families. The purpose was to develop a molecular phylogeny of the Ceratopogonidae, and interpret the phylogenetic position of the family within the infraorder Culicomorpha. These taxa have been analysed using cladistic methodology which, in combination with an excellent fossil record, provides a well established morphological phylogeny. Sequence analysis of cox2 revealed a high degree of sequence divergence among the species, reflecting in part the antiquity of the family, but also a significant acceleration of sequence evolution in the ceratopogonids compared to other nematoceran Diptera. Phylogenetic reconstruction by neighbor-joining and maximum parsimony gave strong support for an early separation of an ancient lineage that includes the two genera, Austroconops and Leptoconops, from the remainder of the family. The results support the existence of a clade that includes two subfamilies, Dasyheleinae and Forcipomyiinae, and this clade appears as sister to the remaining subfamily, Ceratopogoninae. The molecular phylogeny also supports monophyly of the Ceratopogonidae, and either a sister or paraphyletic relationship of this family with the Chironomidae.     

A priori and a posteriori methods in comparative evolutionary studies of host–parasite associations

Brooks parsimony analysis (BPA) and reconciliation methods in studies of host–parasite associations differ fundamentally, despite using the same null hypothesis. Reconciliation methods may eliminate or modify input data to maximize fit of single parasite clades to a null hypothesis of cospeciation, by invoking different a priori assumptions, including a known host phylogeny. By examining the degree of phylogenetic congruence among multiple parasite clades, using hosts as analogs of taxa but not presuming a host phylogeny or any degree of cospeciation a priori, BPA modifies the null hypothesis of cospeciation if necessary to maintain the integrity of the input data. Two exemplars illustrate critical empirical differences between reconciliation methods and BPA: (1) reconciliation methods rather than BPA may select the incorrect general host cladogram for a set of data from different clades of parasites, (2) BPA rather than reconciliation methods provides the most parsimonious interpretation of all available data, and (3) secondary BPA, proposed in 1990, when applied to data sets in which host‐switching produces hosts with reticulate histories, provides the most parsimonious and biologically realistic interpretations of general host cladograms. The extent to which these general host cladograms, based on cospeciation among different parasite clades inhabiting the same hosts, correspond to host phylogeny can be tested, a posteriori, by comparison with a host phylogeny generated from nonparasite data. These observations lead to the conclusion that BPA and reconciliation methods are designed to implement different research programs based on different epistemologies. BPA is an a posteriori method that is designed to assess the host context of parasite speciation events, whereas reconciliation methods are a priori methods that are designed to fit parasite phylogenies to a host phylogeny. Host‐switching events are essential for explaining complex histories of host–parasite associations. BPA assumes coevolutionary complexity (historical contingency), relying on parsimony as an a posteriori explanatory tool to summarize complex results, whereas reconciliation methods, which embody formalized assumptions of maximum cospeciation, are based on a priori conceptual parsimony. Modifications of basic reconciliation methods, embodied in TreeMap 1.0 and TreeMap 2.02, represent the addition of weighting schemes in which the researcher specifies allowed departures from cospeciation a priori, with the result that TreeMap results more closely agree with BPA results than do reconciled tree analysis results.     

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.     

Phylogeny and biogeography of bees of the tribe Osmiini (Hymenoptera: Megachilidae)

The Osmiini (Megachilidae) constitute a taxonomically and biologically diverse tribe of bees. To resolve their generic and suprageneric relationships, we inferred a phylogeny based on three nuclear genes (Elongation factor 1-alpha, LW-rhodopsin and CAD) applying both parsimony and Bayesian methods. Our phylogeny, which includes 95 osmiine species representing 18 of the 19 currently recognized genera, is well resolved with high support for most basal nodes. The core osmiine genera were found to form a well-supported monophyletic group, but four small genera, Noteriades, Afroheriades,Pseudoheriades and possibly Ochreriades, formerly included in the Osmiini, do not appear to belong within this tribe. Our phylogeny results in the following taxonomic changes: Stenosmia and Hoplosmia are reduced to subgeneric rank in Hoplitis and Osmia, respectively, Micreriades is recognized as a subgenus in Hoplitis and the subgenus Nasutosmia is transferred from Hoplitis to Osmia. We inferred a biogeographic scenario for the Osmiini applying maximum likelihood inference and models of character evolution. We provide evidence that the Osmiini originated in the Palearctic, and that extensive exchanges occurred between the Palearctic and the Nearctic. The latter finding may relate to the fact that many osmiine species nest in wood or in stems, facilitating dispersal by overseas transport of the nests.     

Bayesian Analysis Using a Simple Likelihood Model Outperforms Parsimony for Estimation of Phylogeny from Discrete Morphological Data

Despite the introduction of likelihood-based methods for estimating phylogenetic trees from phenotypic data, parsimony remains the most widely-used optimality criterion for building trees from discrete morphological data. However, it has been known for decades that there are regions of solution space in which parsimony is a poor estimator of tree topology. Numerous software implementations of likelihood-based models for the estimation of phylogeny from discrete morphological data exist, especially for the Mk model of discrete character evolution. Here we explore the efficacy of Bayesian estimation of phylogeny, using the Mk model, under conditions that are commonly encountered in paleontological studies. Using simulated data, we describe the relative performances of parsimony and the Mk model under a range of realistic conditions that include common scenarios of missing data and rate heterogeneity.     

基于12S rRNA基因的鹳形目系统发生关系

采用分子系统学的方法探讨鹳形目5个科之间的系统发生关系.文中测出鹳形目鸟类7种mtDNA 12SrRNA基因全序列,并结合来自Genbank的鹳形目另外7个物种及原鸡的同源区序列,经Clustal W软件对位排列后共1 009位点,包含405个变异位点,其中多态性位点381个,260个简约信息位点.基于上述序列数据,以原鸡为外群,使用距离邻接法、最大简约法、最大似然法及贝叶斯法分别重建了鹳形目5科14种的系统发生树.重建的系统发生树显示,内群中的14个种聚合为4支:鹮科构成第一支,聚在系统树的基部;锤头鹳科与鲸头鹳科聚为一支;鹭科和鹳科各自聚成一支.在比较不同建树方法的结果并进行合意树分析后认为:在鹳形目的系统发生中,鹮科可能是最早分化出的一支;锤头鹳科与鲸头鹳科之间的亲缘关系最近,它们祖先与鹭科、鹳科之间的分歧在时间上可能非常接近.鹳形目5个科之间的系统关系可以表示为:(鹮科,(鹭科,鹳科,(锤头鹳科,鲸头鹳科))).     

Molecular phylogeny of the kingdoms Animalia, Plantae, and Fungi

The branching order of the kingdoms Animalia, Plantae, and Fungi has been a controversial issue. Using the transformed distance method and the maximum parsimony method, we investigated this problem by comparing the sequences of several kinds of macromolecules in organisms spanning all three kingdoms. The analysis was based on the large-subunit and small-subunit ribosomal RNAs, 10 isoacceptor transfer RNA families, and six highly conserved proteins. All three sets of sequences support the same phylogenetic tree: plants and animals are sibling kingdoms that have diverged more recently than the fungi. The ribosomal RNA and protein data sets are large enough so that in both cases the inferred phylogeny is statistically significant. The present report appears to be the first to provide statistically conclusive molecular evidence for the phylogeny of the three kingdoms. The determination of this phylogeny will help us to understand the evolution of various molecular, cellular, and developmental characters shared by any two of the three kingdoms. Noting that the large-subunit rRNA sequences have evolved at similar rates in the three kingdoms, we estimated the ratio of the time since the animal-plant split to the time since the fungal divergence to be 0.90.     

Sampling phylogenetic tree space with the generalized Gibbs sampler

The generalized Gibbs sampler (GGS) is a recently developed Markov chain Monte Carlo (MCMC) technique that enables Gibbs-like sampling of state spaces that lack a convenient representation in terms of a fixed coordinate system. This paper describes a new sampler, called the tree sampler, which uses the GGS to sample from a state space consisting of phylogenetic trees. The tree sampler is useful for a wide range of phylogenetic applications, including Bayesian, maximum likelihood, and maximum parsimony methods. A fast new algorithm to search for a maximum parsimony phylogeny is presented, using the tree sampler in the context of simulated annealing. The mathematics underlying the algorithm is explained and its time complexity is analyzed. The method is tested on two large data sets consisting of 123 sequences and 500 sequences, respectively. The new algorithm is shown to compare very favorably in terms of speed and accuracy to the program DNAPARS from the PHYLIP package.     

Evaluating the clade size effect in alternative measures of branch support

The clade size effect refers to a bias that causes middle‐sized clades to be less supported than small or large‐sized clades. This bias is present in resampling measures of support calculated under maximum likelihood and maximum parsimony and in Bayesian posterior probabilities. Previous analyses indicated that the clade size effect is worst in maximum parsimony, followed by maximum likelihood, while Bayesian inference is the least affected. Homoplasy was interpreted as the main cause of the effect. In this study, we explored the presence of the clade size effect in alternative measures of branch support under maximum parsimony: Bremer support and symmetric resampling, expressed as absolute frequencies and frequency differences. Analyses were performed using 50 molecular and morphological matrices. Symmetric resampling showed the same tendency that bootstrap and jackknife did for maximum parsimony and maximum likelihood. Few matrices showed a significant bias using Bremer support, presenting a better performance than resampling measures of support and comparable to Bayesian posterior probabilities. Our results indicate that the problem is not maximum parsimony, but resampling measures of support. We corroborated the role of homoplasy as a possible cause of the clade size effect, increasing the number of random trees during the resampling, which together with the higher chances that medium‐sized clades have of being contradicted generates the bias during the perturbation of the original matrix, making it stronger in resampling measures of support.     

BIOGEOGRAPHY OF NEW WORLD TAIGA-DWELLING MICROTUS (MAMMALIA: ARVICOLIDAE): A HYPOTHESIS TEST THAT ACCOUNTS FOR PHYLOGENETIC UNCERTAINTY

If we adopt a statistical approach to systematics and recognize that phylogenies are estimated with error, then we can begin to explore statistically justified methods for testing a variety of comparative hypotheses, including those concerning the evolution of life-history characters and biogeography. In this paper I examine two biogeographic hypotheses concerning the rodent genus Microtus. Like many comparative hypotheses, these can be phrased so that each predicts the existence of a particular monophyletic group. Neither of the predicted groups appear on the single best phylogeny as determined by both Dollo parsimony and maximum likelihood analysis of restriction site maps of mitochondrial DNA. Simulation studies, however, suggest that often the best phylogeny from a single data set has only a low probability of being exactly correct. We must also examine those trees that, while not the single best-supported tree, are not rejected by the data. If we find the best phylogeny for which a hypothesis is satisfied, then likelihood methods can be used to test whether that phylogeny is significantly worse then the best tree overall. If that tree can be rejected, then so can the hypothesis. Computational constraints limit the use of likelihood methods for searching among topologies, so parsimony is used as a data exploratory tool. One of the predicted groups cannot be rejected, even though the most parsimonious tree which includes that group requires 11 more steps than does the most parsimonious tree.     

Inconsistency of phylogenetic estimates from concatenated data under coalescence

Although multiple gene sequences are becoming increasingly available for molecular phylogenetic inference, the analysis of such data has largely relied on inference methods designed for single genes. One of the common approaches to analyzing data from multiple genes is concatenation of the individual gene data to form a single supergene to which traditional phylogenetic inference procedures - e.g., maximum parsimony (MP) or maximum likelihood (ML) - are applied. Recent empirical studies have demonstrated that concatenation of sequences from multiple genes prior to phylogenetic analysis often results in inference of a single, well-supported phylogeny. Theoretical work, however, has shown that the coalescent can produce substantial variation in single-gene histories. Using simulation, we combine these ideas to examine the performance of the concatenation approach under conditions in which the coalescent produces a high level of discord among individual gene trees and show that it leads to statistically inconsistent estimation in this setting. Furthermore, use of the bootstrap to measure support for the inferred phylogeny can result in moderate to strong support for an incorrect tree under these conditions. These results highlight the importance of incorporating variation in gene histories into multilocus phylogenetics.     

Phylogeny and evolutionary history of diplobathrid crinoids (Echinodermata)

Order Diplobathrida is a major clade of camerate crinoids spanning the Ordovician–Mississippian, yet phylogenetic relationships have only been inferred for Ordovician taxa. This has hampered efforts to construct a comprehensive tree of life for crinoids and develop a classification scheme that adequately reflects diplobathrid evolutionary history. Here, I apply maximum parsimony and Bayesian phylogenetic approaches to the fossil record of diplobathrids to infer the largest tree of fossil crinoids to date, with over 100 genera included. Recovered trees provide a framework for evaluating the current classification of diplobathrids. Notably, previous suborder divisions are not supported, and superfamily divisions will require significant modification. Although numerous revisions are required for families, most can be retained through reassignment of genera. In addition, recovered trees were used to produce phylogeny‐based estimates of diplobathrid lineage diversity. By accounting for ghost lineages, phylogeny‐based richness estimates offer greater insight into diversification and extinction dynamics than traditional taxonomy‐based approaches alone and provide a detailed summary of the ~150 million‐year evolutionary history of Diplobathrida. This study constitutes a major step toward producing a phylogeny of the Crinoidea and documenting crinoid diversity dynamics. In addition, it will serve as a framework for subsequent phylogeny‐based investigations of macroevolutionary questions.     

Analysis of Acorus calamus chloroplast genome and its phylogenetic implications

Determining the phylogenetic relationships among the major lines of angiosperms is a long-standing problem, yet the uncertainty as to the phylogenetic affinity of these lines persists. While a number of studies have suggested that the ANITA (Amborella-Nymphaeales-Illiciales-Trimeniales-Aristolochiales) grade is basal within angiosperms, studies of complete chloroplast genome sequences also suggested an alternative tree, wherein the line leading to the grasses branches first among the angiosperms. To improve taxon sampling in the existing chloroplast genome data, we sequenced the chloroplast genome of the monocot Acorus calamus. We generated a concatenated alignment (89,436 positions for 15 taxa), encompassing almost all sequences usable for phylogeny reconstruction within spermatophytes. The data still contain support for both the ANITA-basal and grasses-basal hypotheses. Using simulations we can show that were the ANITA-basal hypothesis true, parsimony (and distance-based methods with many models) would be expected to fail to recover it. The self-evident explanation for this failure appears to be a long-branch attraction (LBA) between the clade of grasses and the out-group. However, this LBA cannot explain the discrepancies observed between tree topology recovered using the maximum likelihood (ML) method and the topologies recovered using the parsimony and distance-based methods when grasses are deleted. Furthermore, the fact that neither maximum parsimony nor distance methods consistently recover the ML tree, when according to the simulations they would be expected to, when the out-group (Pinus) is deleted, suggests that either the generating tree is not correct or the best symmetric model is misspecified (or both). We demonstrate that the tree recovered under ML is extremely sensitive to model specification and that the best symmetric model is misspecified. Hence, we remain agnostic regarding phylogenetic relationships among basal angiosperm lineages.