Parsimony-based test for identifying changes in evolutionary trends for quantitative characters: implications for the origin of the amniotic egg

The origin of the amniotic egg was a major event in vertebrate evolution and is thought to have contributed to the spectacular evolutionary radiation of amniotes. We test one of the most popular scenarios proposed by Carroll in 1970 to explain the origin of the amniotic egg using a novel method based on an asymmetric version of linear parsimony (aka Wagner parsimony) for identifying the most parsimonious split of a tree into two parts between which the evolution of the character is allowed to differ. The new method evaluates the cost of splitting a phylogenetic tree at a given node as the integral, over all pairs of asymmetry parameters, of the most parsimonious costs that can be achieved by using the first parameter on the subtree pending from this node and the second parameter elsewhere. By testing all the nodes, we then obtain the most parsimonious split of a tree with regard to the character values at its tips. Among the nine trees and two characters tested, our method yields a total of 517 parsimonious trend changes in Permo-Carboniferous stegocephalians, a single one of which occurs in a part of the tree (among stem-amniotes) where Carroll's scenario predicts that there should have been distinct changes in body size evolutionary trends. This refutes the scenario because the amniote stem does not appear to have elevated rates of evolutionary trend shifts. Our nodal body size estimates offer less discriminating power, but they likewise fail to find strong support for Carroll's scenario.     

Wagner and Dollo: a stochastic duet by composing two parsimonious solos

New contributions toward generalizing evolutionary models expand greatly our ability to analyze complex evolutionary characters and advance phylogeny reconstruction. In this article, we extend the binary stochastic Dollo model to allow for multi-state characters. In doing so, we align previously incompatible Wagner and Dollo parsimony principles under a common probabilistic framework by embedding arbitrary continuous-time Markov chains into the binary stochastic Dollo model. This approach enables us to analyze character traits that exhibit both Dollo and Wagner characteristics throughout their evolutionary histories. Utilizing Bayesian inference, we apply our novel model to analyze intron conservation patterns and the evolution of alternatively spliced exons. The generalized framework we develop demonstrates potential in distinguishing between phylogenetic hypotheses and providing robust estimates of evolutionary rates. Moreover, for the two applications analyzed here, our framework is the first to provide an adequate stochastic process for the data. We discuss possible extensions to the framework from both theoretical and applied perspectives.     

Reconstructing ancestral character states under Wagner parsimony

The problem of assigning optimal character states to the hypothetical ancestors of an evolutionary tree under the Wagner parsimony criterion is examined. A proof is provided for the correctness of Farris's well-known, but previously unproven, algorithm for solving this problem. However, the solution is not, in general, unique, and Farris's method obtains only a subset (generally only one) of the possible solutions. Algorithms that discover other solutions and that resolve ambiguities through the imposition of ancillary criteria are developed and discussed. A method for determining the optimal length of a given tree without actually assigning character states to hypothetical ancestors is described.     

EVALUATION OF THE RESTRICTED MAXIMUM-LIKELIHOOD METHOD FOR ESTIMATING PHYLOGENETIC TREES USING SIMULATED ALLELE-FREQUENCY DATA

Comparisons are made of the accuracy of the restricted maximum-likelihood, Wagner parsimony, and UPGMA (unweighted pair-group method using arithmetic averages) clustering methods to estimate phylogenetic trees. Data matrices were generated by constructing simulated stochastic evolution in a multidimensional gene-frequency space using a simple genetic-drift model (Brownian-motion, random-walk) with constant rates of divergence in all lineages. Ten differentphylogenetic tree topologies of 20 operational taxonomic units (OTU's), representing a range of tree shapes, were used. Felsenstein's restricted maximum-likelihood method, Wagner parsimony, and UPGMA clustering were used to construct trees from the resulting data matrices. The computations for the restricted maximum-likelihood method were performed on a Cray-1 supercomputer since the required calculations (especially when optimized for the vector hardware) are performed substantially faster than on more conventional computing systems. The overall level of accuracy of tree reconstruction depends on the topology of the true phylogenetic tree. The UPGMA clustering method, especially when genetic-distance coefficients are used, gives the most accurate estimates of the true phylogeny (for our model with constant evolutionary rates). For large numbers of loci, all methods give similar results, but trends in the results imply that the restricted maximum-likelihood method would produce the most accurate trees if sample sizes were large enough.     

Reconstructing ancestral character states: a critical reappraisal

Using parsimony to reconstruct ancestral character states on a phylogenetic tree has become a popular method for testing ecological and evolutionary hypotheses. Despite its popularity, the assumptions and uncertainties of reconstructing the ancestral states of a single character have received less attention than the much less challenging endeavor of reconstructing phylogenetic trees from many characters. Recent research suggests that parsimony reconstructions are often sensitive to violations of the almost universal assumption of equal probabilities of gains and losses. In addition, maximum likelihood has been developed as an alternative to parsimony reconstruction, and has also revealed a surprising amount of uncertainty in ancestral reconstructions.     

Analysis on the reconstruction accuracy of the Fitch method for inferring ancestral states

Background  

As one of the most widely used parsimony methods for ancestral reconstruction, the Fitch method minimizes the total number of hypothetical substitutions along all branches of a tree to explain the evolution of a character. Due to the extensive usage of this method, it has become a scientific endeavor in recent years to study the reconstruction accuracies of the Fitch method. However, most studies are restricted to 2-state evolutionary models and a study for higher-state models is needed since DNA sequences take the format of 4-state series and protein sequences even have 20 states.     

ACCURACY OF ESTIMATED PHYLOGENIES: EFFECTS OF TREE TOPOLOGY AND EVOLUTIONARY MODEL

A simulation study was carried out to investigate the relative importance of tree topology (both balance and stemminess), evolutionary rates (constant, varying among characters, and varying among lineages), and evolutionary models in determining the accuracy with which phylogenetic trees can be estimated. The three evolutionary context models were phyletic (characters can change at each simulated time step), speciational (changes are possible only at the time of speciation into two daughter lineages), and punctuational (changes occur at the time of speciation but only in one of the daughter lineages). UPGMA clustering and maximum parsimony (“Wagner trees”) methods for estimating phylogenies were compared. All trees were based on eight recent OTUs. The three evolutionary context models were found to have the largest influence on accuracy of estimates by both methods. The next most important effect was that of the stemminess × context interaction. Maximum parsimony and UPGMA performed worst under the punctuational models. Under the phyletic model, trees with high stemminess values could be estimated more accurately and balanced trees were slightly easier to estimate than unbalanced ones. Overall, maximum parsimony yielded more accurate trees than UPGMA—but that was expected for these simulations since many more characters than OTUs were used. Our results suggest that the great majority of estimated phylogenetic trees are likely to be quite inaccurate; they underscore the inappropriateness of characterizing current phylogenetic methods as being for reconstruction rather than for estimation.     

Parsimony in evolutionary theory: Law or methodological prescription?

Parsimony (Ockham's razor) is in widespread use in phylogenetic reconstruction (evolution takes the shortest route), however it is not quite obvious which is the rank that this principle should have in evolutionary theory. Parsimony is not of a single kind but, on the contrary, is at least of two kinds: ontological and methodological. Ontological parsimony involves an assumption about the “simplicity of nature”. Methodological parsimony is a purely logical precept, a case of the broad practical principle not to believe anything for which there is no evidence. The two kinds of parsimony are not compatible with one another. The ontological hypotheses that reality is simple has been refuted many times in the history of science, and evolution is not an exception to this. In spite of the fact, that direct evolutionary changes have higher probability than the ones that take “unnecessary” steps, evolutionary parsimony is merely a methodological precept, not a law of evolution. Probability is not enough to give evolutionary parsimony a rank of ontological axiom. Therefore, the reasons to use the principle of evolutionary parsimony are only methodological. A definition of evolutionary parsimony is: as long as no evidence is available to suggest an alternative pathway evolution may be considered to occur in the most parsimonious way.     

TESTING FOR UNEQUAL AMOUNTS OF EVOLUTION IN A CONTINUOUS CHARACTER ON DIFFERENT BRANCHES OF A PHYLOGENETIC TREE USING LINEAR AND SQUARED-CHANGE PARSIMONY: AN EXAMPLE USING LESSER ANTILLEAN ANOLIS LIZARDS

Although a large body of work investigating tests of correlated evolution of two continuous characters exists, hypotheses such as character displacement are really tests of whether substantial evolutionary change has occurred on a particular branch or branches of the phylogenetic tree. In this study, we present a methodology for testing such a hypothesis using ancestral character state reconstruction and simulation. Furthermore, we suggest how to investigate the robustness of the hypothesis test by varying the reconstruction methods or simulation parameters. As a case study, we tested a hypothesis of character displacement in body size of Caribbean Anolis lizards. We compared squared-change, weighted squared-change, and linear parsimony reconstruction methods, gradual Brownian motion and speciational models of evolution, and several resolution methods for linear parsimony. We used ancestor reconstruction methods to infer the amount of body size evolution, and tested whether evolutionary change in body size was greater on branches of the phylogenetic tree in which a transition from occupying a single-species island to a two-species island occurred. Simulations were used to generate null distributions of reconstructed body size change. The hypothesis of character displacement was tested using Wilcoxon Rank-Sums. When tested against simulated null distributions, all of the reconstruction methods resulted in more significant P-values than when standard statistical tables were used. These results confirm that P-values for tests using ancestor reconstruction methods should be assessed via simulation rather than from standard statistical tables. Linear parsimony can produce an infinite number of most parsimonious reconstructions in continuous characters. We present an example of assessing the robustness of our statistical test by exploring the sample space of possible resolutions. We compare ACCTRAN and DELTRAN resolutions of ambiguous character reconstructions in linear parsimony to the most and least conservative resolutions for our particular hypothesis.     

The asymmetry of the carpal joint and the evolution of wing folding in maniraptoran theropod dinosaurs

In extant birds, the hand is permanently abducted towards the ulna, and the wrist joint can bend extensively in this direction to fold the wing when not in use. Anatomically, this asymmetric mobility of the wrist results from the wedge-like shape of one carpal bone, the radiale, and from the well-developed convexity of the trochlea at the proximal end of the carpometacarpus. Among the theropod precursors of birds, a strongly convex trochlea is characteristic of Coelurosauria, a clade including the highly derived Maniraptora in addition to tyrannosaurs and compsognathids. The shape of the radiale can be quantified using a ‘radiale angle’ between the proximal and distal articular surfaces. Measurement of the radiale angle and reconstruction of ancestral states using squared-change parsimony shows that the angle was small (15°) in primitive coelurosaurs but considerably larger (25°) in primitive maniraptorans, indicating that the radiale was more wedge-shaped and the carpal joint more asymmetric. The radiale angle progressively increased still further within Maniraptora, with concurrent elongation of the forelimb feathers and the forelimb itself. Carpal asymmetry would have permitted avian-like folding of the forelimb in order to protect the plumage, an early advantage of the flexible, asymmetric wrist inherited by birds.     

Rapid color evolution in an aposematic species: a phylogenetic analysis of color variation in the strikingly polymorphic strawberry poison-dart frog

Aposematism is one of the great mysteries of evolutionary biology. The evolution of aposematic coloration is poorly understood, but even less understood is the evolution of polymorphism in aposematic signals. Here, we use a phylogeographic approach to investigate the evolution of color polymorphism in Dendrobates pumilio, a well-known poison-dart frog (family Dendrobatidae), which displays perhaps the most striking color variation of any aposematic species. With over a dozen color morphs, ranging from bright red to dull green, D. pumilio provides an ideal opportunity to examine the evolution of color polymorphism and evolutionary shifts to cryptic coloration in an otherwise aposematic species. We constructed a phylogenetic tree for all D. pumilio color morphs from 3051bp of mtDNA sequence data, reconstructed ancestral states using parsimony and Bayesian methods, and tested the recovered tree against constraint trees using parametric bootstrapping to determine the number of changes to each color type. We find strong evidence for nearly maximal numbers of changes in all color traits, including five independent shifts to dull dorsal coloration. Our results indicate that shifts in coloration in aposematic species may occur more regularly than predicted and that convergence in coloration may indicate that similar forces are repeatedly driving these shifts.     

Maximum Parsimony on Phylogenetic networks

Background

Phylogenetic networks are generalizations of phylogenetic trees, that are used to model evolutionary events in various contexts. Several different methods and criteria have been introduced for reconstructing phylogenetic trees. Maximum Parsimony is a character-based approach that infers a phylogenetic tree by minimizing the total number of evolutionary steps required to explain a given set of data assigned on the leaves. Exact solutions for optimizing parsimony scores on phylogenetic trees have been introduced in the past.

Results

In this paper, we define the parsimony score on networks as the sum of the substitution costs along all the edges of the network; and show that certain well-known algorithms that calculate the optimum parsimony score on trees, such as Sankoff and Fitch algorithms extend naturally for networks, barring conflicting assignments at the reticulate vertices. We provide heuristics for finding the optimum parsimony scores on networks. Our algorithms can be applied for any cost matrix that may contain unequal substitution costs of transforming between different characters along different edges of the network. We analyzed this for experimental data on 10 leaves or fewer with at most 2 reticulations and found that for almost all networks, the bounds returned by the heuristics matched with the exhaustively determined optimum parsimony scores.

Conclusion

The parsimony score we define here does not directly reflect the cost of the best tree in the network that displays the evolution of the character. However, when searching for the most parsimonious network that describes a collection of characters, it becomes necessary to add additional cost considerations to prefer simpler structures, such as trees over networks. The parsimony score on a network that we describe here takes into account the substitution costs along the additional edges incident on each reticulate vertex, in addition to the substitution costs along the other edges which are common to all the branching patterns introduced by the reticulate vertices. Thus the score contains an in-built cost for the number of reticulate vertices in the network, and would provide a criterion that is comparable among all networks. Although the problem of finding the parsimony score on the network is believed to be computationally hard to solve, heuristics such as the ones described here would be beneficial in our efforts to find a most parsimonious network.     

Searching for Most Parsimonious Trees with Simulated Evolutionary Optimization

This study describes novel algorithms for searching for most parsimonious trees. These algorithms are implemented as a parsimony computer program, PARSIGAL, which performs well even with difficult data sets. For high level search, PARSIGAL uses an evolutionary optimization algorithm, which feeds good tree candidates to a branch-swapping local search procedure. This study also describes an extremely fast method of recomputing state sets for binary characters (additive or nonadditive characters with two states), based on packing 32 characters into a single memory word and recomputing the tree simultaneously for all 32 characters using fast bitwise logical operations. The operational principles of PARSIGAL are quite different from those previously published for other parsimony computer programs. Hence it is conceivable that PARSIGAL may be able to locate islands of trees that are different from those that are easily located with existing parsimony computer programs.     

AFLP markers as a tool to reconstruct complex relationships: A case study in Rosa (Rosaceae)

The genus Rosa has a complex evolutionary history caused by several factors, often in conjunction: extensive hybridization, recent radiation, incomplete lineage sorting, and multiple events of polyploidy. We examined the applicability of AFLP markers for reconstructing (species) relationships in Rosa, using UPGMA clustering, Wagner parsimony, and Bayesian inference. All trees were well resolved, but many of the deeper branches were weakly supported. The cluster analysis showed that the rose cultivars can be separated into a European and an Oriental cluster, each being related to different wild species. The phylogenetic analyses showed that (1) two of the four subgenera (Hulthemia and Platyrhodon) do not deserve subgeneric status; (2) section Carolinae should be merged with sect. Cinnamomeae; (3) subsection Rubigineae is a monophyletic group within sect. Caninae, making sect. Caninae paraphyletic; and (4) there is little support for the distinction of the five other subsections within sect. Caninae. Comparison of the trees with morphological classifications and with previous molecular studies showed that all methods yielded reliable trees. Bayesian inference proved to be a useful alternative to parsimony analysis of AFLP data. Because of their genome-wide sampling, AFLPs are the markers of choice to reconstruct (species) relationships in evolutionary complex groups.     

Cladistic and phenetic analysis of allozyme data for nine species of sea anemones of the family Actiniidae (Cnidaria: Anthozoa)

The aim of this study was to infer from allozyme data the phylogenetic relationships of nine species of actiniid sea anemones, and also use these data to assess the various methods (phenetic and cladistic) available for phylogenetic analysis. Starch gel electrophoresis was used to obtain genetic data from 13 gene loci. The anemone Metridium senile, from the family Metridiidae, was used as an outgroup. For the phenetic analysis a matrix of pairwise unbiased genetic distances was computed and, from this, dendrograms were produced both by the Wagner distance and the UPGMA methods. For the cladistic analyses three different approaches were used: the first was to treat the allele as a binary character; this was investigated using a Wagner parsimony algorithm. Another approach used was to consider the locus as an unordered character, using the alleles as states. Finally, we used the locus as an ordered multistate character, where mutation, fixation and elimination of each allele were treated as evolutionary novelties, and the heterozygotes were used as cues for the construction of transformation series. The trees produced by the phenetic and cladistic methods were highly congruent. This result suggests that allozymes can be used to produce phylogenetic hypotheses at higher taxonomic levels than those at which they are more usually employed. The Solé difference between the various trees was the relative positions of Bunodosoma caissarum and Bunodactis verrucosa in relation to the two species of Urticina. This difference was probably due to a high rate of anagenic change in B. verrucosa, which distorted the UPGMA dendrogram. The genera Actinia and Urticina appeared monophyletic in all of the trees produced. Also, the sea anemones with specialized column structures such as verrucae and vesicles (U.felina, U. eques, B. verrucosa, B. caissarum) formed a monophyletic cluster, a result compatible with the suggestion that these structures may have appeared only once in the evolutionary history of the Actiniidae.     

Chloroplast DNA restriction site variation and phylogeny of the Berberidaceae

Comparative restriction site mapping of the chloroplast genome was performed to examine phylogenetic relationships among 27 species representing 16 genera of the Berberidaceae and two outgroups. Chloroplast genomes of the species included in this study showed no major structural rearrangements (i.e., they are collinear to tobacco cpDNA) except for the extension of the inverted repeat in species of Berberis and Mahonia. Excluding several regions that exhibited severe length variation, a total of 501 phylogenetically informative sites was mapped for ten restriction enzymes. The strict consensus tree of 14 equally parsimonious trees indicated that some berberidaceous genera (Berberis, Mahonia, Diphylleia) are not monophyletic. To explore phylogenetic utility of different parsimony methods phylogenetic trees were generated using Wagner, Dollo, and weighted parsimony for a reduced data set that included 18 species. One of the most significant results was the recognition of the four chromosomal groups, which were strongly supported regardless of the parsimony method used. The most notable difference among the trees produced by the three parsimony methods was the relationships among the four chromosomal groups. The cpDNA trees also strongly supported a close relationship of several generic pairs (e.g., Berberis-Mahonia, Epimedium-Vancouveria, etc.). Maximum likelihood values were computed for the four different tree topologies of the chromosomal groups, two Wagner, one Dollo, and one weighted topology. The results indicate that the weighted tree has the highest likelihood value. The lowest likelihood value was obtained for the Dollo tree, which had the highest bootstrap and decay values. Separate analyses using only the Inverted Repeat (IR) region resulted in a tree that is identical to the weighted tree. Poor resolution and/or support for the relationships among the four chromosomal lineages of the Berberidaceae indicate that they may have radiated from an ancestral stock in a relatively short evolutionary time.     

Computational complexity of inferring phylogenies from chromosome inversion data

In systematics, parsimony methods construct phylogenies, or evolutionary trees, in which characters evolve with the least evolutionary change. The chromosome inversion, or polymorphism, parsimony criterion is used when each character of a population may exhibit homozygous or heterozygous states, but when the heterozygous state must evolve uniquely. Variations of the criterion concern whether or not the ancestral states of characters are specified. We establish that problems of inferring phylogenies by these criteria are NP-complete and thus are so difficult computationally that efficient optimal algorithms for them are unlikely to exist.     

The information content of a character under a Markov model of evolution

The rate of evolutionary change associated with a character determines its utility for the reconstruction of phylogenetic history. For a given age of lineage splits, we examine the information content of a character to assess the magnitude and range of an optimal rate of substitution. On the one hand an optimal transition rate must provide sufficiently many character changes to distinguish subclades, whereas on the other hand changes must be sufficiently rare that reversals on a single branch (and hence homoplasy) are uncommon. In this study, we evolve binary characters over three tree topologies with fixed branch lengths, while varying transition rate as a parameter. We use the character state distribution obtained to measure the "information content" of a character given a transition rate. This is done with respect to several criteria-the probability of obtaining the correct tree using parsimony, the probability of infering the correct ancestral state, and Shannon-Weaver and Fisher information measures on the configuration of probability distributions. All of the information measures suggest the intuitive result of the existence of optimal rates for phylogeny reconstruction. This nonzero optimum is less pronounced if one conditions on there having been a change, in which case the parsimony-based results of minimum change being the most informative tends to hold.