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.     

Maximum parsimony on subsets of taxa

In this paper we investigate mathematical questions concerning the reliability (reconstruction accuracy) of Fitch's maximum parsimony algorithm for reconstructing the ancestral state given a phylogenetic tree and a character. In particular, we consider the question whether the maximum parsimony method applied to a subset of taxa can reconstruct the ancestral state of the root more accurately than when applied to all taxa, and we give an example showing that this indeed is possible. A surprising feature of our example is that ignoring a taxon closer to the root improves the reliability of the method. On the other hand, in the case of the two-state symmetric substitution model, we answer affirmatively a conjecture of Li, Steel and Zhang which states that under a molecular clock the probability that the state at a single taxon is a correct guess of the ancestral state is a lower bound on the reconstruction accuracy of Fitch's method applied to all taxa.     

Inconsistency of the maximum parsimony method when the rate of nucleotide substitution is constant

The inconsistency of the maximum parsimony method is known to occur even when the rate of nucleotide substitution is constant. To understand why this inconsistency occurs, a mathematical study was conducted for the cases of five, six, and seven sequences. The results obtained indicate that this inconsistency occurs because the probability of occurrence of nucleotide configurations generated by one substitution on a short interior branch is often lower than that of configurations generated by more substitutions on other longer branches. The chance of occurrence of this event—or, the inconsistency of the maximum parsimony method—apparently increases as the number of sequences increases. The inconsistency may occur even when the extent of sequence divergence is relatively small. Correspondence to: M. Nei     

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.     

Proopiomelanocortin (POMC) and testing the phylogenetic position of turtles (Testudines)

Morphological and molecular studies have inferred multiple hypotheses for the phylogenetic relationships of Testudines. The hypothesis that Testudines are the only extant anapsid amniotes and the sister taxon of diapsid amniotes is corroborated by morphological studies, while the hypothesis that Testudines are diapsid amniotes is corroborated by more recent molecular and morphological studies. In this study, the placement of Testudines is tested using the full length cDNA sequence of the polypeptide hormone precursor proopiomelanocortin (POMC). Because only extant taxa have been used, the hypotheses being tested are limited to the following (1) Testudines as the sister taxon of Archosauria, (2) Testudines included in Archosauria and the sister taxon of Crocodilia, (3) Testudines as the sister taxon of Lepidosauria, (4) Testudines as the sister taxon of Sauria, and (5) Testudines as the sister taxon of a monophyletic Mammalia–Sauria clade. Neither Maximum likelihood, Bayesian, or maximum parsimony analyses are able to falsify the hypothesis of (Archosauria (Lepidosauria, Testudines)) and as such is the preferred inference from the POMC data.     

Maximum likelihood outperforms maximum parsimony even when evolutionary rates are heterotachous

Heterotachy occurs when the relative evolutionary rates among sites are not the same across lineages. Sequence alignments are likely to exhibit heterotachy with varying severity because the intensity of purifying selection and adaptive forces at a given amino acid or DNA sequence position is unlikely to be the same in different species. In a recent study, the influence of heterotachy on the performance of different phylogenetic methods was examined using computer simulation for a four-species phylogeny. Maximum parsimony (MP) was reported to generally outperform maximum likelihood (ML). However, our comparisons of MP and ML methods using the methods and evaluation criteria employed in that study, but considering the possible range of proportions of sites involved in heterotachy, contradict their findings and indicate that, in fact, ML is significantly superior to MP even under heterotachy.     

Phylogenetic analysis using parsimony and likelihood methods

The assumptions underlying the maximum-parsimony (MP) method of phylogenetic tree reconstruction were intuitively examined by studying the way the method works. Computer simulations were performed to corroborate the intuitive examination. Parsimony appears to involve very stringent assumptions concerning the process of sequence evolution, such as constancy of substitution rates between nucleotides, constancy of rates across nucleotide sites, and equal branch lengths in the tree. For practical data analysis, the requirement of equal branch lengths means similar substitution rates among lineages (the existence of an approximate molecular clock), relatively long interior branches, and also few species in the data. However, a small amount of evolution is neither a necessary nor a sufficient requirement of the method. The difficulties involved in the application of current statistical estimation theory to tree reconstruction were discussed, and it was suggested that the approach proposed by Felsenstein (1981,J. Mol. Evol. 17: 368–376) for topology estimation, as well as its many variations and extensions, differs fundamentally from the maximum likelihood estimation of a conventional statistical parameter. Evidence was presented showing that the Felsenstein approach does not share the asymptotic efficiency of the maximum likelihood estimator of a statistical parameter. Computer simulations were performed to study the probability that MP recovers the true tree under a hierarchy of models of nucleotide substitution; its performance relative to the likelihood method was especially noted. The results appeared to support the intuitive examination of the assumptions underlying MP. When a simple model of nucleotide substitution was assumed to generate data, the probability that MP recovers the true topology could be as high as, or even higher than, that for the likelihood method. When the assumed model became more complex and realistic, e.g., when substitution rates were allowed to differ between nucleotides or across sites, the probability that MP recovers the true topology, and especially its performance relative to that of the likelihood method, generally deteriorates. As the complexity of the process of nucleotide substitution in real sequences is well recognized, the likelihood method appears preferable to parsimony. However, the development of a statistical methodology for the efficient estimation of the tree topology remains a difficult open problem.     

Phylogenetic analysis of the aquatic Oligochaeta under the principle of parsimony

Phylogenetic relationships between five subfamilies of Tubificidae and ten other families of microdrile oligochaetes were estimated by a Wanger parsimony analysis using PAUP (Phylogenetic Analysis Using Parsimony, by D. L. Swofford). As the apomorph character state is ambiguous for some characters, different assumptions of directionality as well as deletions of some characters are tested in a number of analyses. A general pattern is evident from the study; (1) the majority of the aquatic families are members of a large monophyletic group (the order Tubificida in a somewhat restricted sense) defined by the shared possession of atria (generally with well developed external prostate glands), but the family Tubificidae is paraphyletic within this group; (2) the Enchytraeidae appear to form a second group (the Enchytraeida) together with the exclusively marine Capilloventridae and Randiellidae, all three families characterized by the anterior location of the spermathecae; (3) the Haplotaxidae are a plesiomorph family, which stands out as a branch of its own and constitutes the ancestral part of a group comprising also all the megadriles (the Haplotaxida). However, monophyly of the Haplotaxida is likely only if the haplotaxid octogonadial condition is assumed to be derived from the tetragonadial condition characterizing most microdriles, a situation not envisaged by previous authors. The implications of the parsimony method are briefly discussed.     

Mathematical properties and bounds on haplotyping populations by pure parsimony

Although the haplotype data can be used to analyze the function of DNA, due to the significant efforts required in collecting the haplotype data, usually the genotype data is collected and then the population haplotype inference (PHI) problem is solved to infer haplotype data from genotype data for a population. This paper investigates the PHI problem based on the pure parsimony criterion (HIPP), which seeks the minimum number of distinct haplotypes to infer a given genotype data. We analyze the mathematical structure and properties for the HIPP problem, propose techniques to reduce the given genotype data into an equivalent one of much smaller size, and analyze the relations of genotype data using a compatible graph. Based on the mathematical properties in the compatible graph, we propose a maximal clique heuristic to obtain an upper bound, and a new polynomial-sized integer linear programming formulation to obtain a lower bound for the HIPP problem.     

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.     

The performance of phylogenetic algorithms in estimating haplotype genealogies with migration

Genealogies estimated from haplotypic genetic data play a prominent role in various biological disciplines in general and in phylogenetics, population genetics and phylogeography in particular. Several software packages have specifically been developed for the purpose of reconstructing genealogies from closely related, and hence, highly similar haplotype sequence data. Here, we use simulated data sets to test the performance of traditional phylogenetic algorithms, neighbour-joining, maximum parsimony and maximum likelihood in estimating genealogies from nonrecombining haplotypic genetic data. We demonstrate that these methods are suitable for constructing genealogies from sets of closely related DNA sequences with or without migration. As genealogies based on phylogenetic reconstructions are fully resolved, but not necessarily bifurcating, and without reticulations, these approaches outperform widespread 'network' constructing methods. In our simulations of coalescent scenarios involving panmictic, symmetric and asymmetric migration, we found that phylogenetic reconstruction methods performed well, while the statistical parsimony approach as implemented in TCS performed poorly. Overall, parsimony as implemented in the PHYLIP package performed slightly better than other methods. We further point out that we are not making the case that widespread 'network' constructing methods are bad, but that traditional phylogenetic tree finding methods are applicable to haplotypic data and exhibit reasonable performance with respect to accuracy and robustness. We also discuss some of the problems of converting a tree to a haplotype genealogy, in particular that it is nonunique.     

The diversity and evolution of recruitment behaviour in ants,with a discussion of the usefulness of parsimony criteria in the reconstruction of evolutionary histories

Summary Three alternative hypotheses about the evolution of recruitment behaviour in ants, based on accounts in the literature, are compared by means of a cladistic analysis. The three hypotheses are the following:Hypothesis 1. Increasingly efficient recruitment behaviours exhibited by different ant species have been shaped by or are correlated with ant phylogeny.Hypothesis 2. Increasingly efficient recruitment behaviours represent necessary evolutionary steps independently followed during the evolution of different ant clades.Hypothesis 3. Differently efficient recruitment behaviours have been selected in a convergent way among different species by similar population/environmental constraints.In a first stage of the analysis, these hypotheses have been compared in terms of parsimony (i.e. in terms of tree length = TL) of alternative cladograms based on recruitment behaviour only. The analysis gave the following results: Hypothesis 1, TL = 4; Hypothesis 2, TL = 18; Hypothesis 3, TL = 11. At least in terms of parsimony, hence, Hypothesis 1 appears to be the best. This hypothesis, however, cannot be retained for its total lack of congruence with current views on ant phylogeny. Among the remaining two hypotheses, Hypothesis 3 is again much (ca. 40%) more parsimonious than Hypothesis 2, but the retention index for recruitment behaviour on the relative cladogram is 0.2 as compared with 0.7 for Hypothesis 2. Practically, this implies biologically very implausible behavioural evolution indicated by very improbable ancestors for the species included in the analysis. In the case of recruitment evolution the biological credibility of each hypothesis is inversely proportional to its parsimony.The three hypotheses on the evolution of recruitment behaviour are compared again taking into account the morphological and behavioural correlates of recruitment. The results confirm those obtained by simple cladistic analysis of behaviour alone, namely that an obligatory (i. e. neither reversible nor random) increase in recruitment efficiency has been repeatedly selected within different ant clades. Inclusion of the recruitment correlates allows, in addition, a more precise formulation of the implications of each hypothesis and a tentative test of two other alternatives deduced from the literature. Most papers dealing with recruitment assume this behaviour to be controlled by a single gland, while at least two experimental analyses show that more than one gland is likely to be involved as behavioural releaser. A cladistic approach allowed testing of the following two adaptational hypotheses: A) Synergic behavioural control by several glands, allowing shift of the dominant role from one gland to another. B) Single gland control, making improbable the replacement of one gland by another that performs the same function. The results of the analysis appear to favour alternative A slightly, though neither alternative results in implausible evolutionary paths.It is stressed that parsimony remains the sole decisional criterion when no other criteria are available but it can by no way be preferred to the slightest trace of biological common sense.     

Dangers in testing statistical hypotheses

Most experiments are intended for the estimation of the size of effects rather than for the testing of a hypothesis of whether or not an effect occurs. Hypothesis testing is often inapplicable, is over-used and is likely to lead to misinterpretations of results. The two types of error possible in hypothesis testing are discussed. Whereas Type I error is usually examined as a matter of course, Type II error is almost always ignored. Investigations in which zero differences are important should recognise the possibility of Type II error in their interpretation. A nonsignificant result should not be interpreted as evidence of a lack of effect. Statistical significance is not synonymous with economic or scientific importance. The importance of choosing the most appropriate design is emphasised and some suggestions are made as to how important sources of error can be avoided.     

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.     

The role of parsimony,outgroup analysis,and theory of evolution in phylogenetic systematics

It is argued that both the principle of parsimony and the theory of evolution, especially that of natural selection, are essential analytical tools in phylogenetic systematics, whereas the widely used outgroup analysis is completely useless and may even be misleading. In any systematic analysis, two types of patterns of characters and character states must be discriminated which are referred to as completely and incompletely resolved. In the former, all known species are presented in which the characters and their states studied occur, whereas in the latter this is not the case. Dependent on its structure, a pattern of characters and their states may be explained by either a unique or by various conflicting, equally most parsimonious hypotheses of relationships. The so-called permutation method is introduced which facilitates finding the conflicting, equally most parsimonious hypotheses of relationships. The utility of the principle of parsimony is limited by the uncertainty as to whether its application in systematics must refer to the minimum number of steps needed to explain a pattern of characterts and their states most parsimoniously or to the minimum number of evolutionary events assumed to have caused these steps. Although these numbers may differ, the former is usually preferred for simplicity. The types of outgroup analysis are shown to exist which are termed parsimony analysis based on test samples and cladistic type of outgroup analysis. Essentially, the former is used for analysing incompletely resolved patterns of characters and their states, the latter for analysing completely resolved ones. Both types are shown to be completely useless for rejecting even one of various conflicting, equally most parsimonious hypotheses of relationships. According to contemporary knowledge, this task can be accomplished only by employing the theory of evolution (including the theory of natural selection). But even then, many phylogenetic-systematic problems will remain unsolved. In such cases, arbitrary algorithms like those offered by phenetics can at best offer pseudosolutions to open problems. Despite its limitations, phylogenetic systematics is superior to any kind of aphylogenetic systematics (transformed cladistics included) in approaching a (not: the) “general reference system” of organisms.     

A likelihood approach to character weighting and what it tells us about parsimony and compatibility

The statistical framework of maximum likelihood estimation is used to examine character weighting in inferring phylogenies. A simple probabilistic model of evolution is used, in which each character evolves independently among two states, and different lineages evolve independently. When different characters have different known probabilities of change, all sufficiently small, the proper maximum likelihood method of estimating phylogenies is a weighted parsimony method in which the weights are logarithmically related to the rates of change. When rates of change are taken extremely small, the weights become more equal and unweighted parsimony methods are obtained.
When it is known that a few characters have very high rates of change and the rest very low rates, but it is not known which characters are the ones having the high rates, the maximum likelihood criterion supports use of compatibility methods. By varying the fraction of characters believed to have high rates of change one obtains a 'threshold method' whose behavior depends on the value of a parameter. By altering this parameter the method changes smoothly from being a parsimony method to being a compatibility method. This provides us with a spectrum of intermediates between these methods. These intermediate methods may be of use in analysing real data.