On investigating the statistical properties of the populous path algorithm by computer simulation

Summary Goodman et al.'s (1974) populous path algorithm for estimating hidden mutational change in protein evolution is designed to be used as an adjunct to the maximum parsimony method. When the algorithm is so used, the augmented maximum parsimony distances, far from being overestimates, are underestimates of the actual number of nucleotide substitutions which occur in Tateno and Nei's (1978) computer simulation by the Poisson process model, even when the simulation is carried out at two and a half times the sequence density. Although underestimates, our evidence shows that they are nevertheless more accurate than estimates obtained by a Poisson correction. In the maximum parsimony reconstruction, there is a bias towards overrepresenting the number of shared nucleotide identities between adjacent ancestral and descendant nodal sequences with the bias being stronger in those portions of the evolutionary tree sparser in sequence data. Because of this particular property of maximum parsimony reconstructed sequences, the conclusions of Tateno and Nei concerning the statistical properties of the populous path algorithm are invalid. We conclude that estimates of protein evolutionary rates by the maximum parsimony - populous path approach will become more accurate rather than less as larger numbers of closely related species are included in the analysis.     

A rate-independent technique for analysis of nucleic acid sequences: evolutionary parsimony

The method of evolutionary parsimony--or operator invariants--is a technique of nucleic acid sequence analysis related to parsimony analysis and explicitly designed for determining evolutionary relationships among four distantly related taxa. The method is independent of substitution rates because it is derived from consideration of the group properties of substitution operators rather than from an analysis of the probabilities of substitution in branches of a tree. In both parsimony and evolutionary parsimony, three patterns of nucleotide substitution are associated one-to-one with the three topologically linked trees for four taxa. In evolutionary parsimony, the three quantities are operator invariants. These invariants are the remnants of substitutions that have occurred in the interior branch of the tree and are analogous to the substitutions assigned to the central branch by parsimony. The two invariants associated with the incorrect trees must equal zero (statistically), whereas only the correct tree can have a nonzero invariant. The chi 2-test is used to ascertain the nonzero invariant and the statistically favored tree. Examples, obtained using data calculated with evolutionary rates and branchings designed to camouflage the true tree, show that the method accurately predicts the tree, even when substitution rates differ greatly in neighboring peripheral branches (conditions under which parsimony will consistently fail). As the number of substitutions in peripheral branches becomes fewer, the parsimony and the evolutionary-parsimony solutions converge. The method is robust and easy to use.      

A method for constructing maximum parsimony ancestral amino acid sequences on a given network

A solution is presented for the problem of how to find ancestral codons which minimize the number of mutations over a given network of species for which character-states of aligned amino acid sequences among the contemporary species are known. Three theorems which allow this “maximum parsimony” problem to be solved are proved; then the use of these theorems in finding maximum parsimony ancestral codons is illustrated on a network of chicken and mammalian alpha globin amino acid sequences at two alignment positions.     

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.     

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.     

The relative performance of Bayesian and parsimony approaches when sampling characters evolving under homogeneous and heterogeneous sets of parameters

We tested whether it is beneficial for the accuracy of phylogenetic inference to sample characters that are evolving under different sets of parameters, using both Bayesian MCMC (Markov chain Monte Carlo) and parsimony approaches. We examined differential rates of evolution among characters, differential character-state frequencies and character-state space, and differential relative branch lengths among characters. We also compared the relative performance of parsimony and Bayesian analyses by progressively incorporating more of these heterogeneous parameters and progressively increasing the severity of this heterogeneity. Bayesian analyses performed better than parsimony when heterogeneous simulation parameters were incorporated into the substitution model. However, parsimony outperformed Bayesian MCMC when heterogeneous simulation parameters were not incorporated into the Bayesian substitution model. The higher the rate of evolution simulated, the better parsimony performed relative to Bayesian analyses. Bayesian and parsimony analyses converged in their performance as the number of simulated heterogeneous model parameters increased. Up to a point, rate heterogeneity among sites was generally advantageous for phylogenetic inference using both approaches. In contrast, branch-length heterogeneity was generally disadvantageous for phylogenetic inference using both parsimony and Bayesian approaches. Parsimony was found to be more conservative than Bayesian analyses, in that it resolved fewer incorrect clades.
© The Willi Hennig Society 2006.     

Inconsistency of maximum parsimony revisited

Felsenstein (1978, Syst. Zool. 27:401-410) showed that the method of maximum parsimony can be inconsistent, i.e., lead to an incorrect result with an infinite amount of data. The situation in which this inconsistency occurs is often called the "Felsenstein zone," the phenomenon also known as "long-branch attraction." Felsenstein derived a sufficient inconsistency condition from a model for four taxa with only two different parameters for the probability of change on the five branches connecting the four taxa. In the present paper, his approach is used to derive the inconsistency condition of maximum parsimony from the most general model for four taxa, i.e., with five different parameters for the probabilities of change on the five branches and, for the first time, for characters with k states (k = 2, 3, 4, 5, 6, ...) This is used to determine the factors that can cause the inconsistency of maximum parsimony. It is shown that the probability of change on all five branches and the number of character states play a role in causing inconsistency.     

Proteomic parsimony through bipartite graph analysis improves accuracy and transparency

Assembling peptides identified from LC-MS/MS spectra into a list of proteins is a critical step in analyzing shotgun proteomics data. As one peptide sequence can be mapped to multiple proteins in a database, na?ve protein assembly can substantially overstate the number of proteins found in samples. We model the peptide-protein relationships in a bipartite graph and use efficient graph algorithms to identify protein clusters with shared peptides and to derive the minimal list of proteins. We test the effects of this parsimony analysis approach using MS/MS data sets generated from a defined human protein mixture, a yeast whole cell extract, and a human serum proteome after MARS column depletion. The results demonstrate that the bipartite parsimony technique not only simplifies protein lists but also improves the accuracy of protein identification. We use bipartite graphs for the visualization of the protein assembly results to render the parsimony analysis process transparent to users. Our approach also groups functionally related proteins together and improves the comprehensibility of the results. We have implemented the tool in the IDPicker package. The source code and binaries for this protein assembly pipeline are available under Mozilla Public License at the following URL: http://www.mc.vanderbilt.edu/msrc/bioinformatics/.     

Using Allele Frequencies and Geographic Subdivision to Reconstruct Gene Trees within a Species: Molecular Variance Parsimony

We formalize the use of allele frequency and geographic information for the construction of gene trees at the intraspecific level and extend the concept of evolutionary parsimony to molecular variance parsimony. The central principle is to consider a particular gene tree as a variable to be optimized in the estimation of a given population statistic. We propose three population statistics that are related to variance components and that are explicit functions of phylogenetic information. The methodology is applied in the context of minimum spanning trees (MSTs) and human mitochondrial DNA restriction data, but could be extended to accommodate other tree-making procedures, as well as other data types. We pursue optimal trees by heuristic optimization over a search space of more than 1.29 billion MSTs. This very large number of equally parsimonious trees underlines the lack of resolution of conventional parsimony procedures. This lack of resolution is highlighted by the observation that equally parsimonious trees yield very different estimates of population genetic diversity and genetic structure, as shown by null distributions of the population statistics, obtained by evaluation of 10,000 random MSTs. We propose a non-parametric test for the similarity between any two trees, based on the distribution of a weighted coevolutionary correlation. The ability to test for tree relatedness leads to the definition of a class of solutions instead of a single solution. Members of the class share virtually all of the critical internal structure of the tree but differ in the placement of singleton branch tips.     

Phylogeny of Melaleuca, Callistemon, and Related Genera of the Beaufortia Suballiance (Myrtaceae) Based on 5S and ITS-1 Spacer Regions of nrDNA

A phylogenetic analysis of genera within the informal suballiance Beaufortia (family Myrtaceae), largely endemic to Australia and New Caledonia, is presented based on separate and combined data sets for 5S and ITS-1 spacer regions of nuclear ribosomal DNA. The two sets were not in conflict but the 5S data set was more informative. Data were analysed using conventional parsimony, jackknife parsimony, and three-item parsimony analyses. Three-item analysis gave more resolved trees than conventional parsimony analysis. The Beaufortia suballiance includes two major clades, with all Australian representatives of Callistemon (shown to be monophyletic) and most Australian representatives of Melaleuca forming one of these. The sister clade comprises a well-defined group of endemic New Caledonian taxa (classified as Callistemon and Melaleuca ), some Australian species of Melaleuca , a clade including the Western Australia/Northern Territory genera Beaufortia, Lamarchea , and Regelia , and a clade including the south-west Western Australian genera Calothamnus, Eremaea, Conothamnus , and Phymatocarpus . All molecular analyses sup port the monophyly of Conothamnus and of Regelia , genera for which a number of species were included. Three-item analysis of the combined data set supports the monophyly of Beaufortia . The findings have implications for both taxonomy and biogeography.     

Identification of 18 mouse ABC genes and characterization of the ABC superfamily in Mus musculus

ATP-binding cassette (ABC) genes encode a family of transport proteins known to be involved in a number of human genetic diseases. In this study, we characterized the ABC superfamily in Mus musculus through in silico gene identification and mapping and phylogenetic analysis of mouse and human ABC genes. By querying dbEST with amino acid sequences from the conserved ATP-binding domains, we identified and partially sequenced 18 new mouse ABC genes, bringing the total number of mouse ABC genes to 34. Twelve of the new ABC genes were mapped in the mouse genome to the X chromosome and to 10 of the 19 autosomes. Phylogenetic relationships of mouse and human ABC genes were examined with maximum parsimony and neighbor-joining analyses that demonstrated that mouse and human ABC orthologs are more closely related than are mouse paralogs. The mouse ABC genes could be grouped into the seven previously described human ABC subfamilies. Three mouse ABC genes mapped to regions implicated in cholesterol gallstone susceptibility.     

Molecular phylogenetics of myliobatiform fishes (Chondrichthyes: Myliobatiformes), with comments on the effects of missing data on parsimony and likelihood

Mitochondrial DNA sequences from the 12S rRNA gene, four tRNA genes, and a portion of two protein coding genes were used to investigate the relationship of myliobatoid genera. In addition, we conducted an investigation of the sister group to the freshwater stingrays by sampling additional DNA sequences from GenBank. Consequently, two datasets were used to examine myliobatoid relationships. The first consisted of the genes sequenced in this study. The second dataset was compiled by combining the first dataset with cytochrome b sequences from GenBank. The second dataset, however, included a number of missing characters due to differences in sampling. The effect of the missing characters on both maximum parsimony and maximum likelihood analysis was investigated by conducting a simulation study. Results of the simulation study indicated that maximum likelihood was not sensitive to the missing data, whereas the accuracy of maximum parsimony analysis was expected to decrease. Phylogenetic analysis of this group had several areas concordant with morphological studies, however, the analysis also revealed two novel relationships. In addition, placement of two taxa (Gymnura and Himantura) were dependent both on the dataset and analytical method used.     

Does minimizing homoplasy really maximize homology? MaHo: A method for evaluating homology among most parsimonious trees

Parsimony analysis aims at finding the tree that best fits hypotheses of homology. However, parsimony does not directly maximize homology, but minimizes homoplasy. When a parsimony analysis results in more than a single most-parsimonious tree (MPT), it is shown that the number of homologous characters may vary significantly. We propose a method called MaHo to identify, among the MPTs, the tree(s) that has (have) the highest number of characters that are homologies. We apply this approach to the phylogenetic relationships of the Dombeyoideae (Malvaceae) of the Mascarene Islands. A parsimony analysis was performed, including 31 representatives of the Dombeyoideae. The search resulted in 29,336 MPTs. MaHo was used in order to improve the resolution of the consensus and to increase the number of unambiguous homologies. The consensus of the 7592 MPTs presenting the highest number of homologies was chosen. This resulted in unravelling five additional synapomorphies and in reducing the number of MPTs.     

Stability of characters and construction of phylogenetic trees.

Parsimony methods infer phylogenetic trees by minimizing number of character changes required to explain observed character states. From the perspective of applicability of parsimony methods, it is important to assess whether the characters used to infer phylogeny are likely to provide a correct tree. We introduce a graph theoretical characterization that helps to assess whether given set of characters is appropriate to use with parsimony methods. Given a set of characters and a set of taxa, we construct a network called character overlap graph. We show that the character overlap graph for characters that are appropriate to use in parsimony methods is characterized by significant under-representation of subnetworks known as holes, and provide a validation for this observation. This characterization explains success in constructing evolutionary trees using parsimony method for some characters (e.g., protein domains) and lack of such success for other characters (e.g., introns). In the latter case, the understanding of obstacles to applying parsimony methods in a direct way has lead us to a new approach for detecting inconsistent and/or noisy data. Namely, we introduce the concept of stable characters which is similar but less restrictive than the well known concept of pairwise compatible characters. Application of this approach to introns produces the evolutionary tree consistent with the Coelomata hypothesis.     

Parsimony and the Fisher–Wright debate

In the past five years, there have been a series of papers in the journal Evolution debating the relative significance of two theories of evolution, a neo-Fisherian and a neo-Wrightian theory, where the neo-Fisherians make explicit appeal to parsimony. My aim in this paper is to determine how we can make sense of such an appeal. One interpretation of parsimony takes it that a theory that contains fewer entities or processes, (however we demarcate these) is more parsimonious. On the account that I defend here, parsimony is a ‘local’ virtue. Scientists’ appeals to parsimony are not necessarily an appeal to a theory’s simplicity in the sense of it’s positing fewer mechanisms. Rather, parsimony may be proxy for greater probability or likelihood. I argue that the neo-Fisherians appeal is best understood on this interpretation. And indeed, if we interpret parsimony as either prior probability or likelihood, then we can make better sense of Coyne et al. argument that Wright’s three phase process operates relatively infrequently.     

RANDOM AMPLIFIED POLYMORPHIC DNA (RAPD) AND PARSIMONY METHODS

Abstract — Random amplified polymorphic DNA (RAPD) data possess a number of undesirable features for parsimony analysis. These features include their non-codominant inheritance, their anonymous nature, their different (a)symmetrical transformation probabilities, and their possible GC priming bias. As a consequence, no single parsimony method seems appropriate for RAPD data. Moreover, the presence/absence coding of RAPDs is equivalent to the invalid independent allele model for allozymes. These issues are discussed and the way in which parsimony analysis of RAPDs can be misleading is illustrated.     

Compatibility analysis and its applications

A two-state character is defined as uniquely derived if it has only evolved once in the history of a group, without subsequent reversal. Two independent characters cannot both be uniquely derived if all four possible combinations (or all three excluding that of the two ancestral forms) occur.
A number of ways of choosing compatible sets of uniquely derived characters are discussed and used to derive possible unrooted and rooted trees. Results of these are related to those chosen on parsimony criteria, using data for orthopteroid groups, and the assumptions of both methods are compared. Application of compatibility analysis to the moth genera Teldenia and Argodrepana is also discussed. Compatibility and parsimony methods are complementary rather than exclusive of each other.     

Frequent inconsistency of parsimony under a simple model of cladogenesis

Although the conditions under which the parsimony method becomes inconsistent have been studied for almost two decades, the probability that the parsimony method would encounter conditions causing inconsistency under simple models of cladogenesis is unknown. Here, we examine the statistical behavior of the parsimony method under a birth-death model of cladogenesis, when the molecular clock holds. The parsimony method can become inconsistent a high proportion of the time even under this simple model of cladogenesis. When taxon sampling is poor or rates of evolution are high, the probability that parsimony will become inconsistent increases.     

GROUNDPLANS AND EXEMPLARS: PATHS TO THE TREE OF LIFE

Abstract — During cladistic analysis of a diverse higher taxon it is impractical to code every species as a separate terminal. In such cases, workers proceed in one of two distinct ways: (1) examine a number of member species in order to deduce groundplan character states of the higher group before the analysis is begun, here called the intuitive method, or (2), code a number of real species belonging to the group as terminals in the analysis, called the exemplar method. Both methods have the same aim, to estimate the groundplan of the higher taxon concerned.
Both groundplan estimation methods will lead to identical results when the character in question has the same state in all members of the terminal group, however when the character has two or more states, the two methods may give different results. The precise methods employed in the intuitive approach have not been articulated in the literature, but possible techniques may result in non-parsimonious ancestral state assignments, even in simple cases.
Groundplan estimation in the exemplar method is an extension of parsimony. The exemplar method allows groundplan state/s at internal nodes to be calculated during tree search. In many cases the exemplar method assigns a number of possible states to the groundplan, and the state assignment is therefore equivocal. This is not a deficiency of the method but reflects the notion that the parsimony criterion alone cannot always distinguish a single state present in a hypothetical ancestor. The optimal choice of exemplars required to estimate the groundplan most efficiently is discussed under a simple and common hypothesis of character transformation. For complex character distributions up to three exemplars may be required, each from a separate lineage of the group close to its hypothetical common ancestral node.