Phylogenetic estimation with partial likelihood tensors.

We present an alternative method for calculating likelihoods in molecular phylogenetics. Our method is based on partial likelihood tensors, which are generalizations of partial likelihood vectors, as used in Felsenstein's approach. Exploiting a lexicographic sorting and partial likelihood tensors, it is possible to obtain significant computational savings. We show this on a range of simulated data by enumerating all numerical calculations that are required by our method and the standard approach.

Markov invariants, plethysms, and phylogenetics.

We explore model-based techniques of phylogenetic tree inference exercising Markov invariants. Markov invariants are group invariant polynomials and are distinct from what is known in the literature as phylogenetic invariants, although we establish a commonality in some special cases. We show that the simplest Markov invariant forms the foundation of the Log-Det distance measure. We take as our primary tool group representation theory, and show that it provides a general framework for analyzing Markov processes on trees. From this algebraic perspective, the inherent symmetries of these processes become apparent, and focusing on plethysms, we are able to define Markov invariants and give existence proofs. We give an explicit technique for constructing the invariants, valid for any number of character states and taxa. For phylogenetic trees with three and four leaves, we demonstrate that the corresponding Markov invariants can be fruitfully exploited in applied phylogenetic studies.

Preferential host switching by primate lentiviruses can account for phylogenetic similarity with the primate phylogeny.

Primate lentiviruses (PLV) from closely related primate species have been observed to be more closely related to each other than to PLV from more distantly related primate species. The current explanation for this observation is the codivergence hypothesis; that is, the divergence of a virus lineage results from the divergence of the host lineage. We show that, alternatively, frequent cross-species transmission of PLV, coupled with a tendency for more closely related primate species to exchange viruses "successfully," can result in apparent codivergence. This host-switching hypothesis reconciles several puzzling observations related to the evolution of PLV.

Mathematical elegance with biochemical realism: the covarion model of molecular evolution.

There is an apparent paradox in our understanding of molecular evolution. Current biochemically based models predict that evolutionary trees should not be recoverable for divergences beyond a few hundred million years. In practice, however, trees often appear to be recovered from much older times. Mathematical models, such as those assuming that sites evolve at different rates [including a Gamma distribution of rates across sites (RAS)] may in theory allow the recovery of some ancient divergences. However, such models require that each site maintain its characteristic rate over the whole evolutionary period. This assumption, however, contradicts the knowledge that tertiary structures diverge with time, invalidating the rate-constancy assumption of purely mathematical models. We report here that a hidden Markov version of the covarion model can meet both biochemical and statistical requirements for the analysis of sequence data. The model was proposed on biochemical grounds and can be implemented with only two additional parameters. The two hidden parts of this model are the proportion of sites free to vary (covarions) and the rate of interchange between fixed sites and these variable sites. Simulation results are consistent with this approach, providing a better framework for understanding anciently diverged sequences than the standard RAS models. However, a Gamma distribution of rates may approximate a covarion model and may possibly be justified on these grounds. The accurate reconstruction of older divergences from sequence data is still a major problem, and molecular evolution still requires mathematical models that also have a sound biochemical basis.

The epidemic behavior of the hepatitis C virus.

Hepatitis C virus (HCV) is a leading worldwide cause of liver disease. Here, we use a new model of HCV spread to investigate the epidemic behavior of the virus and to estimate its basic reproductive number from gene sequence data. We find significant differences in epidemic behavior among HCV subtypes and suggest that these differences are largely the result of subtype-specific transmission patterns. Our model builds a bridge between the disciplines of population genetics and mathematical epidemiology by using pathogen gene sequences to infer the population dynamic history of an infectious disease.

Hitch-hiking: a parallel heuristic search strategy, applied to the phylogeny problem.

The article introduces a parallel heuristic search strategy ("Hitch-hiking") which can be used in conjunction with other random-walk heuristic search strategies. It is applied to an artificial phylogeny problem, in which character sequences are evolved using pseudo-random numbers from a hypothetical ancestral sequence. The objective function to be minimized is the minimum number of character-state changes required on a binary tree that could account for the sequences observed at the tips (leaves) of the tree -- the Maximum Parsimony criterion. The Hitch-hiking strategy is shown to be useful in that it is robust and that on average the solutions found using the strategy are better than those found without. Also the strategy can dynamically provide information on the characteristics of the landscape of the problem. I argue that Hitch-hiking as a scheme for parallelization of existing heuristic search strategies is of potentially very general use, in many areas of combinatorial optimization.

Lack of evidence for cospeciation between retroelements and their hosts.

Some literature is available on cospeciation and on reconstructing the phylogenetic relationships of retroelements, but relatively little consideration has been given to whether there is cospeciation between retroelements and their hosts. Here we address this problem in detail. We conclude that there is no significant evidence for cospeciation between retroelements and their hosts. This conclusion was reached by noting that the branching order of the two phylogenies was no more similar than would be expected by chance.

A covariotide model explains apparent phylogenetic structure of oxygenic photosynthetic lineages.

The aims of the work were (1) to develop statistical tests to identify whether substitution takes place under a covariotide model in sequences used for phylogenetic inference and (2) to determine the influence of covariotide substitution on phylogenetic trees inferred for photosynthetic and other organisms. (Covariotide and covarion models are ones in which sites that are variable in some parts of the underlying tree are invariable in others and vice versa.) Two tests were developed. The first was a contingency test, and the second was an inequality test comparing the expected number of variable sites in two groups with the observed number. Application of these tests to 16S rDNA and tufA sequences from a range of nonphotosynthetic prokaryotes and oxygenic photosynthetic prokaryotes and eukaryotes suggests the occurrence of a covariotide mechanism. The degree of support for partitioning of taxa in reconstructed trees involving these organisms was determined in the presence or absence of sites showing particular substitution patterns. This analysis showed that the support for splits between (1) photosynthetic eukaryotes and prokaryotes and (2) photosynthetic and nonphotosynthetic organisms could be accounted for by patterns arising from covariotide substitution. We show that the additional problem of compositional bias in sequence data needs to be considered in the context of patterns of covariotide/covarion substitution. We argue that while covariotide or covarion substitution may give rise to phylogenetically informative patterns in sequence data, this may not always be so.

Jungles: a new solution to the host/parasite phylogeny reconciliation problem.

The problem of finding least-cost reconstructions of past host/parasite associations, given the phylogenetic histories of a set of host taxa and of their associated parasites, is known to be complex. I provide in this article a new method of implicitly listing all the potentially optimal solutions to the problem, by considering each hypothesised past association individually, in a structure I have termed a Jungle. These structures are demonstrated to enable fast acquisition of globally optimal solutions under general weighting schemes, including minimisation of total number of postulated events and maximization of postulated cospeciation events. A simple example is given, and the pocket gopher/chewing louse system investigated by Hafner and Nadler [Hafner and Nadler, Nature 332 (1988) 258] is re-examined.

Spectrum: spectral analysis of phylogenetic data.

MOTIVATION: Spectrum is a new Macintosh and Microsoft Windows program designed to read in phylogenetic four-state or binary data in NEXUS format, and output the corresponding bipartition spectra. It can be used to find the tree whose expected spectrum is closest to the observed spectrum (the closest tree, Hendy, Discr, Math., 96, 51-58,. 1991).

Trees within trees: phylogeny and historical associations.

The association between two or more lineages over evolutionary time is a recurrent theme spanning several different fields within biology, from molecular evolution to coevolution and biogeography. In each `historical association', one lineage is associated with another, and can be thought of as tracking the other over evolutionary time with a greater or lesser degree of fidelity. Examples include genes tracking organisms, parasites tracking hosts and organisms tracking geological and geographical changes. Parallels among these problems raise the tantalizing prospect that each is a special case of a more general problem, and that a single analytical tool can be applied to all three kinds of association.

From gene to organismal phylogeny: reconciled trees and the gene tree/species tree problem.

The processes of gene duplication, loss, and lineage sorting can result in incongruence between the phylogenies of genes and those of species. This incongruence complicates the task of inferring the latter from the former. We describe the use of reconciled trees to reconstruct the history of a gene tree with respect to a species tree. Reconciled trees allow the history of the gene tree to be visualized and also quantify the relationship between the two trees. The cost of a reconciled tree is the total number of duplications and gene losses required to reconcile a gene tree with its species tree. We describe the use of heuristic searches to find the species tree which yields the reconciled tree with the lowest cost. This method can be used to infer species trees from one or more gene trees.

Toward a characterization of landscapes of combinatorial optimization problems, with special attention to the phylogeny problem.

This article introduces a coherent language base for describing and working with characteristics of combinatorial optimization problems, which is at once general enough to be used in all such problems and precise enough to allow subtle concepts in this field to be discussed unambiguously. An example is provided of how this nomenclature is applied to an instance of the phylogeny problem. Also noted is the beneficial effect, on the landscape of the solution space, of transforming the observed data to account for multiple changes of character state.

The effects of sequence length, tree topology, and number of taxa on the performance of phylogenetic methods.

Simulations were used to study the performance of several character-based and distance-based phylogenetic methods in obtaining the correct tree from pseudo-randomly generated input data. The study included all the topologies of unrooted binary trees with from 4 to 10 pendant vertices (taxa) inclusive. The length of the character sequences used ranged from 10 to 10(5) characters exponentially. The methods studied include Closest Tree, Compatibility, Li's method, Maximum Parsimony, Neighbor-joining, Neighborliness, and UPGMA. We also provide a modification to Li's method (SimpLi) which is consistent with additive data. We give estimations of the sequence lengths required for given confidence in the output of these methods under the assumptions of molecular evolution used in this study. A notation for characterizing all tree topologies is described. We show that when the number of taxa, the maximum path length, and the minimum edge length are held constant, there it little but significant dependence of the performance of the methods on the tree topology. We show that those methods that are consistent with the model used perform similarly, whereas the inconsistent methods, UPGMA and Li's method, perform very poorly.

Neighbor-joining uses the optimal weight for net divergence.

A class of phylogenetic clustering methods which calculate net divergences from distance data, but assign differing weights to the net divergences, is defined. The class includes the Neighbor-Joining Method and the Unweighted Pair-Group Method with Arithmetic Mean. The accuracy of some of these methods is studied by computer simulation for the case of four taxa under the additive tree hypothesis. Of these methods and under this hypothesis, it is proved that Neighbor-Joining uses the only weighting for net divergence which is consistent, so that it is the only method in the class which is expected to converge to the correct tree as more data are added. Neighbor-Joining is then compared with Closest Tree on Distances for five taxa by simulation. It is proved that Closest Tree on Distances is equivalent to Neighbor-Joining for four taxa, though it is not when more than four taxa are considered.