Search

This paper discusses methods to take into account interactions between characters, in the context of parsimony analysis. These interactions can be in the form of some characters becoming inapplicable given certain states of other, primary characters; in the form of only certain states being allowed in some characters when a given state or set of states occurs for other characters; or in the form of transformation costs in some character being higher or lower when other characters have certain states or transformations between states. Character–state reconstructions and evaluation of trees under the assumption of independence may easily lead to ancestral assignments that violate elementary rules of biomechanics, well‐established theories relating form and function or ideas about character co‐variation. An obvious example is reconstructing an ancestral bird as wingless and flying at the same time; another is reconstructing a protein‐coding gene as having a stop codon in some ancestors. If the characters are optimized independently, such chimeric ancestral reconstructions can occur even when no terminal displays the impossible combination of states. A set of conventions (implemented via new TNT commands and options) allows the definition of complex rules of interaction. By recoding groups of characters with proper step–matrix costs (and excluding impossible combinations from the set of permissible states), it is possible to find the ancestral reconstructions that maximize homology (and thus the degree to which similarities can be explained by common ancestry), within the constraints imposed by the rules specified by the user. We expect that considerations of biomechanics, functional morphology and natural history will be a source of many theories on possible character dependences, and that the present implementation will encourage users to take the possibility of character dependences into account in their phylogenetic analyses. [ABSTRACT FROM AUTHOR]

This paper examines the implementation of parsimony methods in the programs PAUP*, MEGA and MPBoot, and compares them with TNT. PAUP* implements standard, well‐tested algorithms, and flexible search strategies and options for handling trees; its main drawback is the lack of advanced search algorithms, which makes it difficult to find most parsimonious trees for large and complex datasets. In addition, branch‐swapping can be much slower than in TNT for datasets with large numbers of taxa, although this is only occasionally a problem for phylogenomic datasets given that they typically have small numbers of taxa. The parsimony implementation of MEGA has major drawbacks. MEGA often fails to find parsimonious trees because it does not perform all possible branch swapping subtree pruning regrafting (SPR)/tree bisection‐reconnection (TBR) rearrangements. It furthermore fails to properly handle ambiguity or multiple equally parsimonious trees, and it uses the same addition sequence for all bootstrap replicates. The latter yields values of group support that depend on the order in which taxa are listed in the dataset. In addition, tree searches are very slow and do not facilitate the exploration of different starting points (as random seed is fixed). MPBoot searches for optimal trees using the ratchet, but it is based on SPR instead of TBR (and only evaluates by default a subset of the SPR rearrangements). MPBoot approximates bootstrap frequencies by first finding a sample of trees and then selecting from those trees for every replicate, without performing a tree‐search. The approximation is too rough in many cases, producing serious under‐ or overestimations of the correct support values and, for most kinds of datasets, slower estimations than can be obtained with TNT. In addition, bootstrapping with PAUP*, MEGA or MPBoot can attribute strong supports to groups that have no support at all under any meaningful concept of support, such as likelihood ratios or Bremer supports. In TNT, this problem is decreased by using the strict consensus tree to represent each replicate, or eliminated entirely by using different approximations of the Bremer support. [ABSTRACT FROM AUTHOR]

We discuss here the use of TNT (Tree Analysis using New Technology) for phylogenomic analysis. For such data, parsimony is a useful alternative to model‐based analyses, which frequently utilize models that make unrealistic assumptions (e.g. low heterotachy), struggle with high levels of missing data, etc. Parsimony and model‐based methods often yield trees with few topological differences, which can then be analyzed further in order to investigate whether these few topological differences are due to undesirable analysis artefacts. This is facilitated by the greater speed and computational efficiency of parsimony, which allow for a more in‐depth analysis of datasets. We here briefly describe the computationally most efficient and versatile parsimony software, TNT, which can be used for phylogenetic and phylogenomic analyses. In particular, we describe and provide a series of scripts that are specifically designed for the analysis of phylogenomic datasets. This includes scripts for concatenation of gene data files in different formats, generation of plots and datasets with different levels of gene/taxon occupancy, calculation of different support measures and phylogenetic reconstruction based on concatenated matrices and single genes. The execution of the scripts is also demonstrated with video clips (https://www.youtube.com/channel/UCpIgK8sVH‐yK0Bo3fK62IxA). Lastly, we describe the main commands and functions that enable efficient phylogenomic analyses in TNT. [ABSTRACT FROM AUTHOR]

Evidence for phylogenetic analysis comes in the form of observed similarities, and trees are selected to minimize the number of similarities that cannot be accounted for by homology (homoplasies). Thus, the classical argument for parsimony directly links homoplasy with explanatory power. When characters are hierarchically related, a first character may represent a primary structure such as tail absence/presence and a secondary (subordinate) character may describe tail colour; this makes tail colour inapplicable when tail is absent. It has been proposed that such character hierarchies should be evaluated on the same logical basis as standard characters, maximizing the number of similarities accounted for by secondary homology, i.e. common ancestry. Previous evaluations of the homology of a given ancestral reconstruction contain the unintuitive quantity "subcharacters" (number of regions of applicability). Rather than counting subcharacters, this paper proposes an equivalent but more intuitive formulation, based on counting the number of changes into each separate state. In this formulation, x‐transformations, the homoplasy for the reconstruction is simply the number of changes into the state beyond the first, summed over all states. There is thus no direct connection between homoplasy and number of steps, only between homoplasy and extra steps. The link between the two formulations is that, for any region of applicability of any character, a subcharacter can be interpreted as the change into the state that is plesiomorphic in that region. Although some authors have claimed that the equivalence between maximizing explanatory power and minimizing independent originations of similar features (i.e. the standard justification of parsimony) does not hold for inapplicable characters, evaluating homoplasy with x‐transformations clearly connects the two sides of that equation. Furthermore, as the evaluation with x‐transformations provides a direct count and a straightforward interpretation of homoplasy, it extends naturally into implied weighting, and sheds light on problems with additive, step‐matrix or continuous characters. It also allows deriving transformation costs for recoding hierarchies as step‐matrix characters (where recoded states correspond to permissible combinations of states in primary and secondary characters), so that homology of the original observations is properly measured. Those transformation costs set the cost of gaining the primary structure to the maximum difference between "present" states plus cost of loss, and difference between "present" states to the sum of user‐defined transformation costs between secondary features. With such recoding, invoking multiple independent derivations of the structure and similar features will cost as many extra "steps" as the instances of similarities (in both original characters) that are not being homologized. The step‐matrix recoding also can take into account nested dependences. We present a simple convention for naming characters, which TNT can use to automatically convert the original data into a step‐matrix form and set the proper transformation costs. Finally, the basic elements for handling inapplicable characters in the context of maximum‐likelihood inference are outlined, and some quantitative comparisons between different approaches to inapplicables are provided. [ABSTRACT FROM AUTHOR]

A likelihood method that approximates the behaviour of implied weighting is described. This approach provides a likelihood perspective on several aspects of implied weighting, such as guidance for the choice of concavity values, a justification to use different concavities for different numbers of taxa, and a natural basis for extended implied weighting. In this approach, the number of free parameters in the estimation depends on C, the number of characters (in contrast to the standard Mk model, which estimates 2T–3 parameters for T taxa). Depending on the characteristics of the dataset, the likelihood obtained with this approach may in some cases be similar or superior to that of the Mk model, but with fewer parameters being adjusted. Because of that tradeoff, testing against the Mk model by means of the Akaike information criterion on a set of 182 morphological datasets indicated many cases (36) in which the likelihood approximation to implied weighting is the best method, from an information‐theoretic point of view. Given that it is expected to produce (almost) the same results as this maximum‐likelihood approximation, implied weighting can therefore be seen as a valid alternative to the Mk model often used for morphological datasets, on the basis of a criterion for model fit widely advocated by likelihoodists. [ABSTRACT FROM AUTHOR]

The Mkv evolutionary model, based on minor modifications to models of molecular evolution, is being increasingly used to infer phylogenies from discrete morphological data, often producing different results from parsimony. The critical difference between Mkv and parsimony is the assumption of a "common mechanism" in the Mkv model, with branch lengths determining that probability of change for all characters increases or decreases at the same tree branches by the same exponential factor. We evaluate whether the assumption of a common mechanism applies to morphology, by testing the implicit prediction that branch lengths calculated from different subsets of characters will be significantly correlated. Our analysis shows that DNA (38 data sets tested) is often compatible with a common mechanism, but morphology (86 data sets tested) generally is not, showing very disparate branch lengths for different character partitions. The low levels of branch length correlation demonstrated for morphology (fitting models without a common mechanism) suggest that the Mkv model is too unrealistic and inadequate for the analysis of most morphological data sets. [Bayesian analysis; Mkv model; morphological data; phylogenetics.] [ABSTRACT FROM AUTHOR]

Abstract: One of the lasting controversies in phylogenetic inference is the degree to which specific evolutionary models should influence the choice of methods. Model‐based approaches to phylogenetic inference (likelihood, Bayesian) are defended on the premise that without explicit statistical models there is no science, and parsimony is defended on the grounds that it provides the best rationalization of the data, while refraining from assigning specific probabilities to trees or character‐state reconstructions. Authors who favour model‐based approaches often focus on the statistical properties of the methods and models themselves, but this is of only limited use in deciding the best method for phylogenetic inference—such decision also requires considering the conditions of evolution that prevail in nature. Another approach is to compare the performance of parsimony and model‐based methods in simulations, which traditionally have been used to defend the use of models of evolution for DNA sequences. Some recent papers, however, have promoted the use of model‐based approaches to phylogenetic inference for discrete morphological data as well. These papers simulated data under models already known to be unfavourable to parsimony, and modelled morphological evolution as if it evolved just like DNA, with probabilities of change for all characters changing in concert along tree branches. The present paper discusses these issues, showing that under reasonable and less restrictive models of evolution for discrete characters, equally weighted parsimony performs as well or better than model‐based methods, and that parsimony under implied weights clearly outperforms all other methods. [ABSTRACT FROM AUTHOR]

This paper discusses the problem of whether creating a matrix with all the character state combinations that have a fixed number of steps (or extra steps) on a given tree T , produces the same tree T when analyzed with maximum parsimony or maximum likelihood. Exhaustive enumeration of cases up to 20 taxa for binary characters, and up to 12 taxa for 4-state characters, shows that the same tree is recovered (as unique most likely or most parsimonious tree) as long as the number of extra steps is within 1/4 of the number of taxa. This dependence, 1/4 of the number of taxa, is discussed with a general argumentation, in terms of the spread of the character changes on the tree used to select character state distributions. The present finding allows creating matrices which have as much homoplasy as possible for the most parsimonious or likely tree to be predictable, and examination of these matrices with hill-climbing search algorithms provides additional evidence on the (lack of a) necessary relationship between homoplasy and the ability of search methods to find optimal trees. [ABSTRACT FROM AUTHOR]

This paper examines a recent proposal to calculate supertrees by minimizing the sum of subtree prune-and-regraft distances to the input trees. The supertrees thus calculated may display groups present in a minority of the input trees but contradicted by the majority, or groups that are not supported by any input tree or combination of input trees. The proponents of the method themselves stated that these are serious problems of 'matrix representation with parsimony', but they can in fact occur in their own method. The majority rule supertrees, being explicitly clade-based, cannot have these problems, and seem much more suited to retrieving common clades from a set of trees with different taxon sets. However, it is dubious that so-called majority rule supertrees can always be interpreted as displaying those clades present (or compatible with) with a majority of the trees. The majority rule consensus is always a median tree, in terms of the Robinson-Foulds distances (i.e. it minimizes the sum of Robinson-Foulds distances to the input trees). In contrast, majority rule supertrees may not be median-different, contradictory trees may minimize Robinson-Foulds distances, while their strict consensus does not. If being 'majority' results from being median in Robinson-Foulds distances, this means that in the supertree setting a 'majority' is ambiguously defined, sometimes achievable only by mutually contradictory trees. [ABSTRACT FROM AUTHOR]

In recent years, several publications in computer science journals have proposed new heuristic methods for parsimony analysis. This contribution discusses those papers, including methods highly praised by their authors, such as Hydra, Sampars and GA + PR + LS. Trees of comparable or better scores can be obtained using the program TNT, but from one to three orders of magnitude faster. In some cases, the search methods are very similar to others long in use in phylogenetics, but the enormous speed differences seem to correspond more to poor implementations than to actual differences in the methods themselves. [ABSTRACT FROM AUTHOR]

When doing a bootstrap analysis with a single tree saved per pseudoreplicate, biased search algorithms may influence support values more than actual properties of the data set. Two methods commonly used for finding phylogenetic trees consist of randomizing the input order of species in multiple addition sequences followed by branch swapping, or using random trees as the starting point for branch swapping. The randomness inherent to such methods is assumed to eliminate any consistent preferences for some trees or unsupported groups of taxa, but both methods can be significantly biased. In the case of trees created by sequentially adding taxa, a bias may occur even if every addition sequence is equiprobable, and if one of the equally optimal positions for each terminal to add to the tree is selected equiprobably. In the case of branch swapping, the bias can happen even when branch swapping equiprobably selects any of the trees of better score in the subtree-pruning-regrafting-neighborhood or tree-bisection-reconnection-neighborhood. Consequently, when the data set is ambiguous, both random-addition sequences and branch swapping from random trees may (i) find some of the optimal trees much more frequently than others and (ii) find some groups with a frequency that differs from their frequency among all optimal trees. When the data set defines a single optimal tree, the groups present in that tree may have a different probability of being found by a search, even if supported by equal amounts of evidence. This may happen in both parsimony and maximum-likelihood analyses, and even in small data sets without incongruence. [ABSTRACT FROM AUTHOR]

Three different types of data sets, for which the uniquely most parsimonious tree can be known exactly but is hard to find with heuristic tree search methods, are studied. Tree searches are complicated more by the shape of the tree landscape (i.e. the distribution of homoplasy on different trees) than by the sheer abundance of homoplasy or character conflict. Data sets of Type 1 are those constructed by Radel et al. (2013). Data sets of Type 2 present a very rugged landscape, with narrow peaks and valleys, but relatively low amounts of homoplasy. For such a tree landscape, subjecting the trees to TBR and saving suboptimal trees produces much better results when the sequence of clipping for the tree branches is randomized instead of fixed. An unexpected finding for data sets of Types 1 and 2 is that starting a search from a random tree instead of a random addition sequence Wagner tree may increase the probability that the search finds the most parsimonious tree; a small artificial example where these probabilities can be calculated exactly is presented. Data sets of Type 3, the most difficult data sets studied here, comprise only congruent characters, and a single island with only one most parsimonious tree. Even if there is a single island, missing entries create a very flat landscape which is difficult to traverse with tree search algorithms because the number of equally parsimonious trees that need to be saved and swapped to effectively move around the plateaus is too large. Minor modifications of the parameters of tree drifting, ratchet, and sectorial searches allow travelling around these plateaus much more efficiently than saving and swapping large numbers of equally parsimonious trees with TBR. For these data sets, two new related criteria for selecting taxon addition sequences in Wagner trees (the “selected” and “informative” addition sequences) produce much better results than the standard random or closest addition sequences. These new methods for Wagner trees and for moving around plateaus can be useful when analyzing phylogenomic data sets formed by concatenation of genes with uneven taxon representation (“sparse” supermatrices), which are likely to present a tree landscape with extensive plateaus. [ABSTRACT FROM AUTHOR]

Oblong, a program with very low memory requirements, is presented. It is designed for parsimony analysis of data sets comprising many characters for moderate numbers of taxa (the order of up to a few hundred). The program can avoid using vast amounts of RAM by temporarily saving data to disk buffers, only parts of which are periodically read back in by the program. In this way, the entire data set is never held in RAM by the program-only small parts of it. While using disk files to store the data slows down searches, it does so only by a relatively small factor (4× to 5×), because the program minimizes the number of times the data must be accessed (i.e. read back in) during tree searches. Thus, even if the program is not designed primarily for speed, runtimes are within an order of magnitude of those of the fastest existing parsimony programs. [ABSTRACT FROM AUTHOR]

A method for the direct use of aligned landmark data (2D or 3D coordinates of comparable points) in phylogenetic analysis is described. The approach is based on finding, for each of the landmark points, the ancestral positions that minimize the distance between the ancestor/descendant points along the tree. Doing so amounts to maximizing the degree to which similar positions of the landmarks in different taxa can be accounted for by common ancestry, i.e. parsimony. This method requires no transformation of the aligned data or the results: the data themselves are the x, y, z coordinates of the landmarks, and the output of mapping a character onto a given tree is the x, y, z coordinates for the hypothetical ancestors. In the special case of collinear points, the results are identical to those of optimization of (continuous) additive characters. [ABSTRACT FROM AUTHOR]

Obtaining a well supported schema of phylogenetic relationships among the major groups of living organisms requires considering as much taxonomic diversity as possible, but the computational cost of calculating large phylogenies has so far been a major obstacle. We show here that the parsimony algorithms implemented in TNT can successfully process the largest phylogenetic data set ever analysed, consisting of molecular sequences and morphology for 73 060 eukaryotic taxa. The trees resulting from molecules alone display a high degree of congruence with the major taxonomic groups, with a small proportion of misplaced species; the combined data set retrieves these groups with even higher congruence. This shows that tree-calculation algorithms effectively retrieve phylogenetic history for very large data sets, and at the same time provides strong corroboration for the major eukaryotic lineages long recognized by taxonomists. [ABSTRACT FROM AUTHOR]

[Display omitted] • Differences between concatenated phylogenomic methods are quantified for the first time in more than 150 empirical datasets. • Differences between the trees derived from the three evaluated methods were minimal. • The degree of support of nodes is a good predictor of groups that differ between methods. • The number of incongruent nodes was higher for relationships at level of phylum or higher. • Most of discordance in the systematic conclusions from studies involved nodes considered as recalcitrant problems in systematics. Assessing the effect of methodological decisions on the resulting hypotheses is critical in phylogenetics. Recent studies have focused on evaluating how model selection, orthology definition and confounding factors affect phylogenomic results. Here, we compare the results of three concatenated phylogenetic methods (Maximum Likelihood, ML; Bayesian Inference, BI; Maximum Parsimony, MP) in 157 empirical phylogenomic datasets. The resulting trees were very similar, with 96.7% of all nodes shared between BI and ML (90.6% for ML-MP and 89.1% for BI-MP). Differing nodes were predominantly those of lower support. The main conclusions of most of the studies agreed for the three phylogenetic methods and the discordance involved nodes considered as recalcitrant problems in systematics. The differences between methods were proportionally larger in datasets that analyze the relationships at higher taxonomic levels (particularly phyla and kingdoms), and independent of the number of characters included in the datasets. Note: a spanish version of this article is available in the Supplementary material (Supplementary material online). [ABSTRACT FROM AUTHOR]