New Gromov-Inspired Metrics on Phylogenetic Tree Space

We present a new class of metrics for unrooted phylogenetic X-trees inspired by the Gromov–Hausdorff distance for (compact) metric spaces. These metrics can be efficiently computed by linear or quadratic programming. They are robust under NNI operations, too. The local behaviour of the metrics shows that they are different from any previously introduced metrics. The performance of the metrics is briefly analysed on random weighted and unweighted trees as well as random caterpillars.     

Yule-generated trees constrained by node imbalance

The Yule   process generates a class of binary trees which is fundamental to population genetic models and other applications in evolutionary biology. In this paper, we introduce a family of sub-classes of ranked trees, called Ω-trees, which are characterized by imbalance of internal nodes. The degree of imbalance is defined by an integer 0≤ω$0\le \omega$. For caterpillars  , the extreme case of unbalanced trees, ω=0$\omega =0$. Under models of neutral evolution, for instance the Yule model, trees with small ω are unlikely to occur by chance. Indeed, imbalance can be a signature of permanent selection pressure, such as observable in the genealogies of certain pathogens. From a mathematical point of view it is interesting to observe that the space of Ω-trees maintains several statistical invariants although it is drastically reduced in size compared to the space of unconstrained Yule trees. Using generating functions, we study here some basic combinatorial properties of Ω-trees. We focus on the distribution of the number of subtrees with two leaves. We show that expectation and variance of this distribution match those for unconstrained trees already for very small values of ω.     

THE EFFECT OF ORDERED CHARACTERS ON PHYLOGENETIC RECONSTRUCTION

Abstract Morphological structures are likely to undergo more than a single change during the course of evolution. As a result, multistate characters are common in systematic studies and must be dealt with. Particularly interesting is the question of whether or not multistate characters should be treated as ordered (additive) or unordered (non-additive). In accepting a particular hypothesis of order, numerous others are necessarily rejected. We review some of the criteria often used to order character states and the underlying assumptions inherent in these criteria.
The effects that ordered multistate characters can have on phylogenetic reconstruction are examined using 27 data sets. It has been suggested that hypotheses of character state order are more informative then hypotheses of unorder and may restrict the number of equally parsimonious trees as well as increase tree resolution. Our results indicate that ordered characters can produce more, equal or less equally parsimonious trees and can increase, decrease or have no effect on tree resolution. The effect on tree resolution can be a simple gain in resolution or a dramatic change in sister-taxa relationships. In cases where several outgroups are included in the data matrix, hypotheses of order can change character polarities by altering outgroup topology. Ordered characters result in a different topology from unordered characters only when the hierarchy of the cladogram disagrees with the investigator's a priori hypothesis of order. If the best criterion for assessing character evolution is congruence with other characters, the practice of ordering multistate characters is inappropriate.     

Fifty years of character compatibility concepts at work

In the mid 19th century,systematic biologists realized that observable similarities and differences among a group of related species could be the basis for hypotheses about the evolutionary relationships among the species and their ancestors.Such hypotheses Can be expressed as characters.A character is comprised of two or more character states of species considered to be similar with respect to a basis for comparison.The states of a character may also be arranged into a character state tree to hypothesize speciation events associated with changes from one character state to another.In the mid 20th century.some systematists realized that sometimes paxrs of characters(or character state trees)could be incompatible as hypotheses,i.e.,they could not both be true.Through the 1950s,'60s and'70s,tests for,and ways to resolve,incompatibilities were used to estimate an ancestor relation based on mutually compatible characters.An estimate was often shown as a diagram connecting ancestors to their immediate descendants(not quite correctly)called a phylogenetic tree.More recently,other applications of compatibility concepts have been developed,including:identify characters that appear to be random in the context of their data set;combine estimates of ancestor relations for subsets of taxa in a larger collection into a single estimate(a so-called supertree)for the whole collection;and interpret geographic patterns in an evolutionary context.     

Necessary and sufficient conditions for the existence of certain quadratic invariants under a phylogenetic tree.

Invariants are functions of the probabilities of state configurations among lineages, with expected values equal to zero under certain phylogenies. For two-state sequences, the existence of certain quadratic invariants requires a symmetric substitution model. For sequences with more than two states, the necessary condition for the existence of certain quadratic invariants in terms of independent events is much stronger than symmetry. For DNA sequences, only three parameters are allowed in the substitution model, which includes Kimura's two-parameter model as a special case.     

Relations phylogénétiques chez les marchantiales (Hepaticae). Incongruence apparente entre données morphologiques et moléculaires

A cladistic analysis of the order Marchantiales based on morphological characters (43 characters) did not agree with the classification in current use. Molecular sequences of nuclear-encoded 26S rRNA genes of seven species of the order and two out-groups (1254–1299 bp) were analysed to solve this contradiction. Results between morphologial and sequence data are conflicting. The combination of the two data sets shows that a weighting of the morphological data corresponding to equal contributions of the two sets resolves contradiction. We demonstrate that the structure of two data sets can be compatible even if the resultant trees are incongruent. Addition of a few compatible data (for instance, via character weighting) can result in congruent trees. The taxonomic incongruence we observed could illustrate a case of too limited molecular sampling.     

Corroboration versus "Strongest Evidence"

Background knowledge comprises accepted (well-corroborated) theories and results. Such theories are taken to be true for the purpose of interpreting evidence when assessing the corroboration of a hypothesis currently in question. Accordingly, background knowledge does not properly include rejected theories, false assumptions, or null models. In particular, regarding a model of random character distribution as "background knowledge" would rule out corroboration of phylogenetic hypotheses, since it would make character data irrelevant to inferring phylogeny. The presence of homoplasy is not grounds for treating characters as if they were randomly distributed, since characters can show strong phylogenetic structure even when they show homoplasy. This means that clique (compatibility) analysis is unjustified, since that method depends crucially on the assumption that characters showing any homoplasy at all are unrelated to phylogeny. Although likelihood does not measure corroboration, corroboration is closely connected to likelihood: for given evidence and background, the most likely trees are also best corroborated. Most parsimonious trees are best corroborated; the apparent clash between parsimony and likelihood is an artifact of the use of unrealistic models in most "maximum likelihood" methods.     

Algorithms for efficient near-perfect phylogenetic tree reconstruction in theory and practice

We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at most once in the evolutionary tree, yielding an algorithm for binary character states that is computationally efficient but not robust to imperfections in real data. A near-perfect phylogeny relaxes the perfect phylogeny assumption by allowing at most a constant number of additional mutations. We develop two algorithms for constructing optimal near-perfect phylogenies and provide empirical evidence of their performance. The first simple algorithm is fixed parameter tractable when the number of additional mutations and the number of characters that share four gametes with some other character are constants. The second, more involved algorithm for the problem is fixed parameter tractable when only the number of additional mutations is fixed. We have implemented both algorithms and shown them to be extremely efficient in practice on biologically significant data sets. This work proves the BNPP problem fixed parameter tractable and provides the first practical phylogenetic tree reconstruction algorithms that find guaranteed optimal solutions while being easily implemented and computationally feasible for data sets of biologically meaningful size and complexity.     

SKEWNESS AND PERMUTATION

Abstract— The skewness criterion of phylogenetic structure in data is too sensitive to character state frequencies, is not sensitive enough to number of characters (degree of corroboration) and relies on counts of arbitrarily-resolved bifurcating trees. For these reasons it can give misleading results. Permutation tests lack those drawbacks and can be performed quickly by using approximate parsimony calculations, but the test based on minimal tree length can imply strong structure in ambiguous data. A more satisfactory test is obtained by using a support measure which takes multiple trees into account.     

Data Decisiveness, Missing Entries, and the DD Index

The decisiveness of a data set has been defined as the degree to which all possible dichotomous trees for that data set differ in length, and the DD statistic (the data decisiveness index) has been proposed to measure this degree. In this paper, we first discuss an exact nonre cursive formula for the length of indecisive datasets (DD = 0) that consist of informative binary characters in which no missing entries are allowed. Next, the concept of indecisive data sets is extended to data sets in which missing entries may be present. Last, indecisive data sets with missing entries are used as an aid to construct hypothetical data sets that single out some of the factors that influence the DD statistic. On the basis of these examples, it is concluded that the concept of data decisiveness is too elusive to be captured into a single and simple index such as DD.     

Weighting against homoplasy improves phylogenetic analysis of morphological data sets

The problem of character weighting in cladistic analysis is revisited. The finding that, in large molecular data sets, removal of third positions (with more homoplasy) decreases the number of well supported groups has been interpreted by some authors as indicating that weighting methods are unjustified. Two arguments against that interpretation are advanced. Characters that collectively determine few well‐supported groups may be highly reliable when taken individually (as shown by specific examples), so that inferring greater reliability for sets of characters that lead to an increase in jackknife frequencies may not always be warranted. But even if changes in jackknife frequencies can be used to infer reliability, we demonstrate that jackknife frequencies in large molecular data sets are actually improved when downweighting characters according to their homoplasy but using properly rescaled functions (instead of the very strong standard functions, or the extreme of inclusion/exclusion); this further weakens the argument that downweighting homoplastic characters is undesirable. Last, we show that downweighting characters according to their homoplasy (using standard homoplasy‐weighting methods) on 70 morphological data sets (with 50–170 taxa), produces clear increases in jackknife frequencies. The results obtained under homoplasy weighting also appear more stable than results under equal weights: adding either taxa or characters, when weighting against homoplasy, produced results more similar to original analyses (i.e., with larger numbers of groups that continue being supported after addition of taxa or characters), with similar or lower error rates (i.e., proportion of groups recovered that subsequently turn out to be incorrect). Therefore, the same argument that had been advanced against homoplasy weighting in the case of large molecular data sets is an argument in favor of such weighting in the case of morphological data sets. © The Willi Hennig Society 2008.     

Congruence and indifference between two molecular markers for understanding oral evolution in the Marynidae sensu lato (Ciliophora, Colpodea)

Our understanding of the evolution of oral structures within the Colpodida is confounded by the low number of morphological characters that can be used in constructing hypotheses, and by the low taxon and character sampling in molecular phylogenetic analyses designed to assess these hypotheses. Here we increase character sampling by sequencing the mitochondrial SSU-rDNA locus for three isolates of the Marynidae sensu lato. We show that the inferred mitochondrial and nuclear SSU-rDNA trees, as well as concatenated and constrained analyses, are congruent in not recovering a monophyletic Marynidae. However, due to low node support, the trees are indifferent to whether the morphological characters used to unite the Marynidae are the result of retention of ancestral states or convergence. In light of this indifference and an increased amount of nuclear and mitochondrial SSU-rDNA data, alternative hypotheses of oral evolution in the Colpodida are presented.     

When two trees go to war

Rooted phylogenetic networks are used to model non-treelike evolutionary histories. Such networks are often constructed by combining trees, clusters, triplets or characters into a single network that in some well-defined sense simultaneously represents them all. We review these four models and investigate how they are related. Motivated by the parsimony principle, one often aims to construct a network that contains as few reticulations (non-treelike evolutionary events) as possible. In general, the model chosen influences the minimum number of reticulation events required. However, when one obtains the input data from two binary (i.e. fully resolved) trees, we show that the minimum number of reticulations is independent of the model. The number of reticulations necessary to represent the trees, triplets, clusters (in the softwired sense) and characters (with unrestricted multiple crossover recombination) are all equal. Furthermore, we show that these results also hold when not the number of reticulations but the level of the constructed network is minimised. We use these unification results to settle several computational complexity questions that have been open in the field for some time. We also give explicit examples to show that already for data obtained from three binary trees the models begin to diverge.     

Phylogeny reconstruction in the neogene bryozoan metrarabdotos: A paleontologic evaluation of methodology

An adequate stratigraphic record can not only aid in both cladistic and stratophenetic reconstruction of phytogenies, but can also serve in estimating the temporal consistency of the resulting phylogenetic trees. For hypothetical data sets, cladistically constructed trees can be as consistent with the temporal distribution of sampled populations or species as those constructed stratophenetically. Empirical testing in taxonomic groups with sufficiently dense fossil records is needed to show whether, and under what conditions, this potential can be realized. A stratophenetic tree and cladistic trees based on several approaches to character weighting were constructed for Caribbean Neogene species of the bryozoan Metrarabdotos with multiple‐character data from closely spaced sequential populations. The modular morphology and highly punctuated evolutionary pattern of these species blur the distinction between continuous and discrete characters, so that all available characters are potentially of equal significance in establishing phytogenies, rather than just those with discrete states conventionally used in cladistic analysis. However, only the cladistic trees generated with all characters weighted to emphasize contribution to species discrimination have temporal consistencies that are clearly significant statistically and approach that of the stratophenetic tree in magnitude. These results provide a start toward establishing general guidelines for cladistic analysis of taxa with stratigraphie records too sparse for stratophenetic reconstruction.     

ESTIMATING CHARACTER WEIGHTS DURING TREE SEARCH

Abstract— A new method for weighting characters according to their homoplasy is proposed; the method is non-iterative and does not require independent estimations of weights. It is based on searching trees with maximum total fit, with character fits defined as a concave function of homoplasy. Then, when comparing trees, differences in steps occurring in characters which show more homoplasy on the trees are less influential. The reliability of the characters is estimated, during the analysis, as a logical implication of the trees being compared. The "fittest" trees imply that the characters are maximally reliable and, given character conflict, have fewer steps for the characters which fit the tree better. If other trees save steps in some characters, it will be at the expense of gaining them in characters with less homoplasy.     

Partition-free congruence analysis: implications for sensitivity analysis

A criterion is proposed to compare systematic hypotheses based on multiple sources of information under a diverse set of interpretive assumptions (i.e., sensitivity analysis of Wheeler, 1995 ). This metric, the Meta‐Retention Index (MRI), is the retention index (RI) of Farris calculated over the set of conventional homologous qualitative characters (ordered, unordered, Sankoff, etc.) and molecular fragment characters sensu Wheeler (1996, 1999 ). The superiority of this measure to other similar measures (e.g., incongruence length difference test) comes from its independence from partition information. The only values that participate in its calculation are the minimum, maximum and observed cost (= cladogram cost) of each character. The partition (morphology, gene locus) from which the variant may have come is irrelevant. In the special cases where there is only a single data partition, this measure is equivalent to the conventional RI; and in the case where there are single fragment characters per partition (contiguous molecular loci as data sets) the measure is identical to the complement of the Rescaled Incongruence Length Difference (RILD) of Wheeler and Hayashi (1998 ). The MRI can serve as an optimality criterion for deciding among systematic hypotheses based on the same data, but different sets of analysis assumptions (e.g., character weights, indel costs). The MRI may lose discriminatory power in situations where a minority of highly congruent characters is given high weight. This situation can be detected and seems unlikely to occur frequently in real data sets. © The Willi Hennig Society 2006.     

Multiple molecular data sets suggest independent origins of highly eusocial behavior in bees (Hymenoptera:Apinae)

Different views of the pattern of social evolution among the highly eusocial bees have arisen as a result of discordance between past molecular and morphology-based phylogenies. Here we present new data and taxa for four molecular data sets and reassess the morphological characters available to date. We show there is no significant character incongruence between four molecular data sets (two nuclear and two mitochondrial), but highly significant character incongruence leads to topological incongruence between the molecular and morphological data. We investigate the effects of using different outgroup combinations to root the estimated tree. We also consider various ways in which biases in the sequence data could be misleading, using several maximum likelihood models, LogDet corrections, and spectral analyses. Ultimately, we concede there is strong discordance between the molecular and morphological data partitions and appropriately apply the conditional combination approach in this case. We also find two equally well supported placements of the root for the molecular trees, one supported by 16S and 28S sequences, the other supported by cytochrome b and opsin. The strength of the evidence leads us to accept two equally well supported hypotheses based on analyses of the molecular data sets. These are the most rigorously supported hypotheses of corbiculate bee relationships at this time, and frame our argument that highly eusocial behavior within the corbiculate bees evolved twice independently.     

PHYLOGENETIC INTERRELATIONSHIPS AND REDUCTIVE EVOLUTION IN NEOTROPICAL CHARACIDIIN FISHES (CHARACIFORMES, OSTARIOPHYSI)

Abstract— Miniaturization, which results in the presence of numerous apparently paedomorphic characters associated with reduced size, is a common phenomenon among neotropical fishes, with over 85 miniature species distributed among the five major ordinal groups. Eleven species are recognized as miniatures within the Characidiinae, a monophyletic subunit of Characiformes. A reconstruction of characidiin phylogeny is used to analyze the history of miniaturization events. Former hypotheses of origin of miniaturization among characidiins are rejected, underscoring the need for phylogenetic frameworks in the study of ontogenetic changes associated with the phenomenon of miniaturization. The 11 instances of miniature species can be most parsimoniously attributed to three independent miniaturization events within the Characidiinae.
Reductive characters comprise a large proportion of phylogenetically informative characters within the Characidiinae. In the largest group of miniatures, reductive characters represent more than half of the character state transformations affecting supraspecific relationships among Elachocharax, Klausewitzia, Odontocharacidium and Microcharacidium . An analysis of patterns of character state distributions fails to reject the null hypothesis of character independence. A distinction is made between the concepts of character independence, defined as the origination of character states from different (non-simultaneous) evolutionary events, and character correlation, defined as the association of character states in terminal taxa. Character correlation is not a sufficient criterion to reject Hennig's auxiliary principle, according to which the "presence of apomorphous characters in different species is always reason for suspecting kinship, and their origin by convergence should not be assumed a priori". High values of character correlation are the expected result of congruent patterns of character distribution.     

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.     

EVOLUTIONARY CHARACTER ANALYSIS: TRACING CHARACTER CHANGE ON A CLADOGRAM

Abstract— There has been little formal discussion concerning character analysis in cladistics, even though characters and their character state trees are central to phylogenetic analyses. We refer to this field as Evolutionary Character Analysis. This paper defines the components of evolutionary character analysis: character state trees, transmodal characters, cladogram characters, attribute and character phylogenies; and the use of these components in phylogenetic inference and evolutionary studies. Character state trees and their effect on cladogram construction are discussed. A new method for numerically coding complex character state trees is described that further reduces the number of variables required to describe them. This method, ordinal coding, reduces the size of data matrices, and facilitates retrieval of state codes. This paper advocates the use of both biological evidence and evidence internal to the cladogram itself to construct character state trees (CSTs). We discuss general models of character evolution (morphocline analysis, Fitch minimum mutation model, etc.) and their role in forming CSTs. Character state trees formed with theories of character evolution are referred to as transmodal characters. These transmodal characters are contrasted with cladogram characters (Mickevich, 1982), and the place of each in a phylogenetic analysis is discussed. The method for determining cladogram characters is detailed with more complicated examples than found in previous publications. We advocate testing transmodal characters by comparing them with the resultant cladogram characters. This comparison involves transformation series analysis (TSA; Mickevich, 1982) which is viewed as an extension of reciprocal illumination. The TSA procedure and its place in hypothesis testing are reviewed. Tracing the evolution of characters interests both systematists and non-systematists alike. When character state trees (transmodal characters) are optimized on pre-existing phylogenies, character phylogenies and attribute phylogenies result. Attributes are defined as a feature that may or may not be homologous (i.e., ecological categories, plant hosts, etc.). We provide two illustrations of this approach, one involving the evolution of the anuran ear and another involving the coevolution of the butterfly Heliconius and its hostplants. Finally, the components of phylogenetic character analysis can be used to test more general evolutionary theories such as the biogenetic law and vicariance biogeography.