Hadamard conjugations and modeling sequence evolution with unequal rates across sites

Rooting gene trees without outgroups: EP rooting

Gene sequences are routinely used to determine the topologies of unrooted phylogenetic trees, but many of the most important questions in evolution require knowing both the topologies and the roots of trees. However, general algorithms for calculating rooted trees from gene and genomic sequences in the absence of gene paralogs are few. Using the principles of evolutionary parsimony (EP) (Lake JA. 1987a. A rate-independent technique for analysis of nucleic acid sequences: evolutionary parsimony. Mol Biol Evol. 4:167–181) and its extensions (Cavender, J. 1989. Mechanized derivation of linear invariants. Mol Biol Evol. 6:301–316; Nguyen T, Speed TP. 1992. A derivation of all linear invariants for a nonbalanced transversion model. J Mol Evol. 35:60–76), we explicitly enumerate all linear invariants that solely contain rooting information and derive algorithms for rooting gene trees directly from gene and genomic sequences. These new EP linear rooting invariants allow one to determine rooted trees, even in the complete absence of outgroups and gene paralogs. EP rooting invariants are explicitly derived for three taxon trees, and rules for their extension to four or more taxa are provided. The method is demonstrated using 18S ribosomal DNA to illustrate how the new animal phylogeny (Aguinaldo AMA et al. 1997. Evidence for a clade of nematodes, arthropods, and other moulting animals. Nature 387:489–493; Lake JA. 1990. Origin of the metazoa. Proc Natl Acad Sci USA 87:763–766) may be rooted directly from sequences, even when they are short and paralogs are unavailable. These results are consistent with the current root (Philippe H et al. 2011. Acoelomorph flatworms are deuterostomes related to Xenoturbella. Nature 470:255–260).

ANCESTRAL MAXIMUM LIKELIHOOD OF EVOLUTIONARY TREES IS HARD

Maximum likelihood (ML) (Neyman, 1971) is an increasingly popular optimality criterion for selecting evolutionary trees. Finding optimal ML trees appears to be a very hard computational task — in particular, algorithms and heuristics for ML take longer to run than algorithms and heuristics for maximum parsimony (MP). However, while MP has been known to be NP-complete for over 20 years, no such hardness result has been obtained so far for ML.

In this work we make a first step in this direction by proving that ancestral maximum likelihood (AML) is NP-complete. The input to this problem is a set of aligned sequences of equal length and the goal is to find a tree and an assignment of ancestral sequences for all of that tree's internal vertices such that the likelihood of generating both the ancestral and contemporary sequences is maximized. Our NP-hardness proof follows that for MP given in (Day, Johnson and Sankoff, 1986) in that we use the same reduction from VERTEX COVER; however, the proof of correctness for this reduction relative to AML is different and substantially more involved.

Measuring fit of sequence data to phylogenetic model: gain of power using marginal tests

Testing fit of data to model is fundamentally important to any science, but publications in the field of phylogenetics rarely do this. Such analyses discard fundamental aspects of science as prescribed by Karl Popper. Indeed, not without cause, Popper (Unended quest: an intellectual autobiography. Fontana, London, 1976) once argued that evolutionary biology was unscientific as its hypotheses were untestable. Here we trace developments in assessing fit from Penny et al. (Nature 297:197-200, 1982) to the present. We compare the general log-likelihood ratio (the G or G (2) statistic) statistic between the evolutionary tree model and the multinomial model with that of marginalized tests applied to an alignment (using placental mammal coding sequence data). It is seen that the most general test does not reject the fit of data to model (P approximately 0.5), but the marginalized tests do. Tests on pairwise frequency (F) matrices, strongly (P < 0.001) reject the most general phylogenetic (GTR) models commonly in use. It is also clear (P < 0.01) that the sequences are not stationary in their nucleotide composition. Deviations from stationarity and homogeneity seem to be unevenly distributed amongst taxa; not necessarily those expected from examining other regions of the genome. By marginalizing the 4( t ) patterns of the i.i.d. model to observed and expected parsimony counts, that is, from constant sites, to singletons, to parsimony informative characters of a minimum possible length, then the likelihood ratio test regains power, and it too rejects the evolutionary model with P << 0.001. Given such behavior over relatively recent evolutionary time, readers in general should maintain a healthy skepticism of results, as the scale of the systematic errors in published trees may really be far larger than the analytical methods (e.g., bootstrap) report.

Can comprehensive background knowledge be incorporated into substitution models to improve phylogenetic analyses? A case study on major arthropod relationships

BACKGROUND

Whenever different data sets arrive at conflicting phylogenetic hypotheses, only testable causal explanations of sources of errors in at least one of the data sets allow us to critically choose among the conflicting hypotheses of relationships. The large (28S) and small (18S) subunit rRNAs are among the most popular markers for studies of deep phylogenies. However, some nodes supported by this data are suspected of being artifacts caused by peculiarities of the evolution of these molecules. Arthropod phylogeny is an especially controversial subject dotted with conflicting hypotheses which are dependent on data set and method of reconstruction. We assume that phylogenetic analyses based on these genes can be improved further i) by enlarging the taxon sample and ii) employing more realistic models of sequence evolution incorporating non-stationary substitution processes and iii) considering covariation and pairing of sites in rRNA-genes.

RESULTS

We analyzed a large set of arthropod sequences, applied new tools for quality control of data prior to tree reconstruction, and increased the biological realism of substitution models. Although the split-decomposition network indicated a high noise content in the data set, our measures were able to both improve the analyses and give causal explanations for some incongruities mentioned from analyses of rRNA sequences. However, misleading effects did not completely disappear.

CONCLUSION

Analyses of data sets that result in ambiguous phylogenetic hypotheses demand for methods, which do not only filter stochastic noise, but likewise allow to differentiate phylogenetic signal from systematic biases. Such methods can only rely on our findings regarding the evolution of the analyzed data. Analyses on independent data sets then are crucial to test the plausibility of the results. Our approach can easily be extended to genomic data, as well, whereby layers of quality assessment are set up applicable to phylogenetic reconstructions in general.

Difficulties in testing for covarion-like properties of sequences under the confounding influence of changing proportions of variable sites

The covarion (COV)-like properties of sequences are poorly described and their impact on phylogenetic analyses poorly understood. We demonstrate using simulations that, under an evolutionary model where the proportion of variable sites changes in nonadjacent lineages, log likelihood values for rates across site (RAS) and COV models become similar, making models difficult to distinguish. Further, although COV and RAS models provide a great improvement in likelihood scores over a homogeneous model with these simulated data, reconstruction accuracy of tree building is low, suggesting caution when it is suspected that proportions of variable sites differ in different evolutionary lineages. We study the performance of a recently developed contingency test that detects the presence of COV-type evolution modified for protein data. We report that if proportions of variable sites (p(var)) change in a lineage-specific manner such that their distributions in different lineages become sufficiently nonoverlapping, then the contingency test can incorrectly suggest a homogeneous model. Also of concern is the possibility of different proportions of variable sites between the groups being studied. In a study of chloroplast proteins, interpretation of the test is found to be susceptible to different partitioning of taxon groups, making the test very subjective in its implementation. Extreme intergroup differences in the extent of divergence and difference in proportions of variable sites could be contributing to this effect.

Model use in phylogenetics: nine key questions

Models of character evolution underpin all phylogeny estimations, thus model adequacy remains a crucial issue for phylogenetics and its many applications. Although progress has been made in selecting appropriate models for phylogeny estimation, there is still concern about their purpose and proper use. How do we interpret models in a phylogenetic context? What are their effects on phylogeny estimation? How can we improve confidence in the models that we choose? That the phylogenetics community is asking such questions denotes an important stage in the use of explicit models. Here, we examine these and other common questions and draw conclusions about how the community is using and choosing models, and where this process will take us next.

Measuring the fit of sequence data to phylogenetic model: allowing for missing data

It is fundamentally important to assess the fit of data to model in phylogenetic and evolutionary studies. Phylogenetic methods using molecular sequences typically start with a multiple alignment. It is possible to measure the fit of data to model expectations of data, for example, via the likelihood-ratio (G) test or the X(2) test, if all sites in all sequences have an unambiguous residue. However, nearly all alignments of interest contain sites (columns of the alignment) with missing data, that is, ambiguous nucleotides, gaps, or unsequenced regions, which must presently be removed before using the above tests. Unfortunately, this is often either undesirable or impractical, as it will discard much of the data. Here, we show how iterative ML estimators may directly estimate the site-pattern probabilities for columns with missing data, given only standard i.i.d. assumptions. The optimization may use an EM or Newton algorithm, or any other hill-climbing approach. The resulting optimal likelihood under the unconstrained or multinomial model may be compared directly with the likelihood of the data coming from the model (a G statistic). Alternatively the modified observed and the expected frequencies of site patterns may be compared using a X(2) test. The distribution of such statistics is best assessed using appropriate simulations. The new method is applicable to models using codons or paired sites. The methods are also useful with Hadamard conjugations (spectral analysis) and are illustrated with these and with ML evolutionary models that allow site-rate variability.

LUCA, or just a conserved Archaeon?: Comments on Xue et al. (2003)

In their recent paper, Xue et al. used an unusual technique of rooting the universal phylogenetic tree, which resulted in positioning of the last universal common ancestor within Archaea. The present paper brings some criticisms on the methods and results achieved.

Searching factors causing implausible non-monophyly: ssu rDNA phylogeny of Isopoda Asellota (Crustacea: Peracarida) and faster evolution in marine than in freshwater habitats

This contribution addresses two questions: which alignment patterns are causing non-monophyly of the Asellota and what is the phylogenetic history of this group? The Asellota are small benthic crustaceans occurring in most aquatic habitats. In view of the complex morphological apomorphies known for this group, monophyly of the Asellota has never been questioned. Using ssu rDNA sequences of outgroups and of 16 asellote species from fresh water, littoral marine habitats and from deep-sea localities, the early divergence between the lineages in fresh water and in the ocean, and the monophyly of the deep-sea taxon Munnopsidae are confirmed. Relative substitution rates of freshwater species are much lower than in other isopod species, rates being highest in some littoral marine genera (Carpias and Jaera). Furthermore, more sequence sites are variable in marine than in freshwater species, the latter conserve outgroup character states. Monophyly is recovered with parsimony methods, but not with distance and maximum likelihood analyses, which tear apart the marine from the freshwater species. The information content of alignments was studied with spectra of supporting positions. The scarcity of signal (=apomorphic nucleotides) supporting monophyly of the Asellota is attributed to a short stem-line of this group or to erosion of signal in fast evolving marine species. Parametric boostrapping in combination with spectra indicates that a tree model cannot explain the data and that monophyly of the Asellota should not be rejected even though many topologies do not recover this taxon.

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

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

Rapidly evolving lineages impede the resolution of phylogenetic relationships among Clitellata (Annelida)

The phylogenetic relationships of the Clitellata were investigated using a data set with published and new complete or partial 18S rRNA and mtCOI gene sequences of 13 and 49 taxa representing 8 and 14 families, respectively. Three different alignments were considered for 18S, and the possible influence of departures from rate constancy among sites was evaluated by analyses using a Gamma model of rate heterogeneity. Maximum-likelihood estimates of the shape parameter alpha of the Gamma distribution were very low, whatever the alignment or the gene considered, suggesting that phylogenetic reconstructions taking into account the rate heterogeneity among sites are likely to be the most reliable. Analyzed separately, the two genes did not resolve the relationships among the Clitellata, but the consensus tree was congruent with the morphology-based relationships. Our data suggest the inclusion of the Euhirudinea, Acanthobdellida, and Branchiobdellida in the Oligochaeta and suggest the Lumbriculidae as the link between both assemblages. Although separate analyses of both genes, as well as different alignments for the 18S rRNA sequences, yielded conflicting results concerning the phylogenetic position of leeches and leech-like worms vis-à-vis the Oligochaeta, subsequent analyses using the Gamma model greatly reduced the observed inconsistencies. Our analyses show that among the Clitellata, the leeches and the leech-like and gutless worms represent significantly faster evolving lineages. It is suggested that the observed higher mutation rates may be explained by the fact that these lineages contain almost exclusively commensal and/or parasitic taxa.

Appropriate likelihood ratio tests and marginal distributions for evolutionary tree models with constraints on parameters

We show how to make appropriate likelihood ratio tests for evolutionary tree models when parameters such as edge (internodes or branches) lengths have nonnegativity constraints. In such cases, under the null model of an edge length being zero, the marginal distribution of this parameter is proven to be a "half-normal", that is, 50% zero values and 50% the positive half of a normal distribution. Other constrained parameters, such as the proportion of invariant sites, give similar results. To make likelihood ratio tests between nested models, e.g., H(0): homogeneous site rates, and H(1): site rates follow a gamma distribution with variance 1/k, then asymptotically as sequence length increases, the distribution under H(0) becomes a mixture of chi distributions, in this case 50% chi(0), and 50% chi(1) (where the subscript denotes degrees of freedom, i.e. , not the usually assumed 100% chi(1); which leads to a conservative test). Such mixtures are sometimes called distributions. Simulations show that even with sequences as short as 125 sites, some parameters, including the proportion of invariant sites, fit asymptotic distributions closely.

How good are deep phylogenetic trees?

Great interest is given to species emerging early in phylogenetic reconstruction because they are often assumed to represent an ancestor. Recent studies indicate, however, that species branching deep in molecular trees are often fast-evolving ones, misplaced because of the long-branch artefact. The detection of genuinely deep-branching organisms remains an elusive task.

Estimation of evolutionary distances under stationary and nonstationary models of nucleotide substitution

Estimation of evolutionary distances has always been a major issue in the study of molecular evolution because evolutionary distances are required for estimating the rate of evolution in a gene, the divergence dates between genes or organisms, and the relationships among genes or organisms. Other closely related issues are the estimation of the pattern of nucleotide substitution, the estimation of the degree of rate variation among sites in a DNA sequence, and statistical testing of the molecular clock hypothesis. Mathematical treatments of these problems are considerably simplified by the assumption of a stationary process in which the nucleotide compositions of the sequences under study have remained approximately constant over time, and there now exist fairly extensive studies of stationary models of nucleotide substitution, although some problems remain to be solved. Nonstationary models are much more complex, but significant progress has been recently made by the development of the paralinear and LogDet distances. This paper reviews recent studies on the above issues and reports results on correcting the estimation bias of evolutionary distances, the estimation of the pattern of nucleotide substitution, and the estimation of rate variation among the sites in a sequence.

General time-reversible distances with unequal rates across sites: mixing gamma and inverse Gaussian distributions with invariant sites

A series of new results useful to the study of DNA sequences using Markov models of substitution are presented with proofs. General time-reversible distances can be extended to accommodate any fixed distribution of rates across sites by replacing the logarithmic function of a matrix with the inverse of a moment generating function. Estimators are presented assuming a gamma distribution, the inverse Gaussian distribution, or a mixture of either of these with invariant sites. Also considered are the different ways invariant sites may be removed and how these differences may affect estimated distances. Through collaboration, we implemented these distances into PAUP in 1994. The variance of these new distances is approximated via the delta method. It is also shown how to predict the divergence expected for a pair of sequences given a rate matrix and a distribution of rates across sites, allowing iterated ML estimates of distances under any reversible model. A simple test of whether a rate matrix is time reversible is also presented. These new methods are used to estimate the divergence time of humans and chimps from mtDNA sequence data. These analyses support suggestions that the human lineage has an enhanced transition rate relative to other hominoids. These studies also show that transversion distances differ substantially from the overall distances which are dominated by transitions. Transversions alone apparently suggest a very recent divergence time for humans versus chimps and/or a very old (> 16 myr) divergence time for humans versus orangutans. This work illustrates graphically ways to interpret the reliability of distance-based transformations, using the corrected transition to transversion ratio returned for pairs of sequences which are successively more diverged.