New approaches for reconstructing phylogenies from gene order data

We report on new techniques we have developed for reconstructing phylogenies on whole genomes. Our mathematical techniques include new polynomial-time methods for bounding the inversion length of a candidate tree and new polynomial-time methods for estimating genomic distances which greatly improve the accuracy of neighbor-joining analyses. We demonstrate the power of these techniques through an extensive performance study based on simulating genome evolution under a wide range of model conditions. Combining these new tools with standard approaches (fast reconstruction with neighbor-joining, exploration of all possible refinements of strict consensus trees, etc.) has allowed us to analyze datasets that were previously considered computationally impractical. In particular, we have conducted a complete phylogenetic analysis of a subset of the Campanulaceae family, confirming various conjectures about the relationships among members of the subset and about the principal mechanism of evolution for their chloroplast genome. We give representative results of the extensive experimentation we conducted on both real and simulated datasets in order to validate and characterize our approaches. We find that our techniques provide very accurate reconstructions of the true tree topology even when the data are generated by processes that include a significant fraction of transpositions and when the data are close to saturation.     

Automatic genome-wide reconstruction of phylogenetic gene trees

Gene duplication and divergence is a major evolutionary force. Despite the growing number of fully sequenced genomes, methods for investigating these events on a genome-wide scale are still in their infancy. Here, we present SYNERGY, a novel and scalable algorithm that uses sequence similarity and a given species phylogeny to reconstruct the underlying evolutionary history of all genes in a large group of species. In doing so, SYNERGY resolves homology relations and accurately distinguishes orthologs from paralogs. We applied our approach to a set of nine fully sequenced fungal genomes spanning 150 million years, generating a genome-wide catalog of orthologous groups and corresponding gene trees. Our results are highly accurate when compared to a manually curated gold standard, and are robust to the quality of input according to a novel jackknife confidence scoring. The reconstructed gene trees provide a comprehensive view of gene evolution on a genomic scale. Our approach can be applied to any set of sequenced eukaryotic species with a known phylogeny, and opens the way to systematic studies of the evolution of individual genes, molecular systems and whole genomes. Supplementary information: Supplementary data are available at Bioinformatics online.     

Robustness of Phylogenetic Inference Based on Minimum Evolution

Minimum evolution is the guiding principle of an important class of distance-based phylogeny reconstruction methods, including neighbor-joining (NJ), which is the most cited tree inference algorithm to date. The minimum evolution principle involves searching for the tree with minimum length, where the length is estimated using various least-squares criteria. Since evolutionary distances cannot be known precisely but only estimated, it is important to investigate the robustness of phylogenetic reconstruction to imprecise estimates for these distances. The safety radius is a measure of this robustness: it consists of the maximum relative deviation that the input distances can have from the correct distances, without compromising the reconstruction of the correct tree structure. Answering some open questions, we here derive the safety radius of two popular minimum evolution criteria: balanced minimum evolution (BME) and minimum evolution based on ordinary least squares (OLS + ME). Whereas BME has a radius of \frac12\frac{1}{2}, which is the best achievable, OLS + ME has a radius tending to 0 as the number of taxa increases. This difference may explain the gap in reconstruction accuracy observed in practice between OLS + ME and BME (which forms the basis of popular programs such as NJ and FastME).     

Assessment of phylogenomic and orthology approaches for phylogenetic inference

MOTIVATION: Phylogenomics integrates the vast amount of phylogenetic information contained in complete genome sequences, and is rapidly becoming the standard for reliably inferring species phylogenies. There are, however, fundamental differences between the ways in which phylogenomic approaches like gene content, superalignment, superdistance and supertree integrate the phylogenetic information from separate orthologous groups. Furthermore, they all depend on the method by which the orthologous groups are initially determined. Here, we systematically compare these four phylogenomic approaches, in parallel with three approaches for large-scale orthology determination: pairwise orthology, cluster orthology and tree-based orthology. RESULTS: Including various phylogenetic methods, we apply a total of 54 fully automated phylogenomic procedures to the fungi, the eukaryotic clade with the largest number of sequenced genomes, for which we retrieved a golden standard phylogeny from the literature. Phylogenomic trees based on gene content show, relative to the other methods, a bias in the tree topology that parallels convergence in lifestyle among the species compared, indicating convergence in gene content. CONCLUSIONS: Complete genomes are no guarantee for good or even consistent phylogenies. However, the large amounts of data in genomes enable us to carefully select the data most suitable for phylogenomic inference. In terms of performance, the superalignment approach, combined with restrictive orthology, is the most successful in recovering a fungal phylogeny that agrees with current taxonomic views, and allows us to obtain a high-resolution phylogeny. We provide solid support for what has grown to be a common practice in phylogenomics during its advance in recent years. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.     

Use of whole genome sequence data to infer baculovirus phylogeny

Several phylogenetic methods based on whole genome sequence data were evaluated using data from nine complete baculovirus genomes. The utility of three independent character sets was assessed. The first data set comprised the sequences of the 63 genes common to these viruses. The second set of characters was based on gene order, and phylogenies were inferred using both breakpoint distance analysis and a novel method developed here, termed neighbor pair analysis. The third set recorded gene content by scoring gene presence or absence in each genome. All three data sets yielded phylogenies supporting the separation of the Nucleopolyhedrovirus (NPV) and Granulovirus (GV) genera, the division of the NPVs into groups I and II, and species relationships within group I NPVs. Generation of phylogenies based on the combined sequences of all 63 shared genes proved to be the most effective approach to resolving the relationships among the group II NPVs and the GVs. The history of gene acquisitions and losses that have accompanied baculovirus diversification was visualized by mapping the gene content data onto the phylogenetic tree. This analysis highlighted the fluid nature of baculovirus genomes, with evidence of frequent genome rearrangements and multiple gene content changes during their evolution. Of more than 416 genes identified in the genomes analyzed, only 63 are present in all nine genomes, and 200 genes are found only in a single genome. Despite this fluidity, the whole genome-based methods we describe are sufficiently powerful to recover the underlying phylogeny of the viruses.     

The Consistent Phylogenetic Signal in Genome Trees Revealed by Reducing the Impact of Noise

Phylogenetic trees based on gene repertoires are remarkably similar to the current consensus of life history. Yet it has been argued that shared gene content is unreliable for phylogenetic reconstruction because of convergence in gene content due to horizontal gene transfer and parallel gene loss. Here we test this argument, by filtering out as noise those orthologous groups that have an inconsistent phylogenetic distribution, using two independent methods. The resulting phylogenies do indeed contain small but significant improvements. More importantly, we find that the majority of orthologous groups contain some phylogenetic signal and that the resulting phylogeny is the only detectable signal present in the gene distribution across genomes. Horizontal gene transfer or parallel gene loss does not cause systematic biases in the gene content tree.     

On the <Emphasis Type="SmallCaps">PATHGROUPS</Emphasis> approach to rapid small phylogeny

We present a data structure enabling rapid heuristic solution to the ancestral genome reconstruction problem for given phylogenies under genomic rearrangement metrics. The efficiency of the greedy algorithm is due to fast updating of the structure during run time and a simple priority scheme for choosing the next step. Since accuracy deteriorates for sets of highly divergent genomes, we investigate strategies for improving accuracy and expanding the range of data sets where accurate reconstructions can be expected. This includes a more refined priority system, and a two-step look-ahead, as well as iterative local improvements based on a the median version of the problem, incorporating simulated annealing. We apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny.     

Deriving the genomic tree of life in the presence of horizontal gene transfer: conditioned reconstruction

The horizontal gene transfer (HGT) being inferred within prokaryotic genomes appears to be sufficiently massive that many scientists think it may have effectively obscured much of the history of life recorded in DNA. Here, we demonstrate that the tree of life can be reconstructed even in the presence of extensive HGT, provided the processes of genome evolution are properly modeled. We show that the dynamic deletions and insertions of genes that occur during genome evolution, including those introduced by HGT, may be modeled using techniques similar to those used to model nucleotide substitutions that occur during sequence evolution. In particular, we show that appropriately designed general Markov models are reasonable tools for reconstructing genome evolution. These studies indicate that, provided genomes contain sufficiently many genes and that the Markov assumptions are met, it is possible to reconstruct the tree of life. We also consider the fusion of genomes, a process not encountered in gene sequence evolution, and derive a method for the identification and reconstruction of genome fusion events. Genomic reconstructions of a well-defined classical four-genome problem, the root of the multicellular animals, show that the method, when used in conjunction with paralinear/logdet distances, performs remarkably well and is relatively unaffected by the recently discovered big genome artifact.     

DNA hybridization in animal taxonomy: a critique from first principles

DNA hybridization is a "distance method" for phylogenetic reconstruction and, as such, shares a set of assumptions, advantages, and problems with other techniques that do not directly employ character data. The technique purports to measure the average percent mismatch of homologous nucleotide sequences between the single-copy genomes of species. This measurement, as any other, is subject to considerations of accuracy and precision. While replicate measurements and technical modifications can improve precision, the accuracy of such measurements is limited by the equivalence of genomes under comparison. Such routine events in genome evolution as gene duplication and deletion may complicate the interpretation of DNA hybridization distances. Beyond measurement limitations, the most serious potential distortions of distances are due to biased sequence sampling and homoplasy. These problems, however, do not necessarily preclude phylogenetic reconstruction, and their effects may be mitigated by numerical corrections. Homoplasy, in particular, is a difficulty faced by all methods of phylogenetic inference. If such distortions can be eliminated, mitigated by correction, or shown to be trivial, pairwise tree-construction strategies should provide reliable estimates of phylogeny.     

On the accuracy of language trees

Historical linguistics aims at inferring the most likely language phylogenetic tree starting from information concerning the evolutionary relatedness of languages. The available information are typically lists of homologous (lexical, phonological, syntactic) features or characters for many different languages: a set of parallel corpora whose compilation represents a paramount achievement in linguistics. From this perspective the reconstruction of language trees is an example of inverse problems: starting from present, incomplete and often noisy, information, one aims at inferring the most likely past evolutionary history. A fundamental issue in inverse problems is the evaluation of the inference made. A standard way of dealing with this question is to generate data with artificial models in order to have full access to the evolutionary process one is going to infer. This procedure presents an intrinsic limitation: when dealing with real data sets, one typically does not know which model of evolution is the most suitable for them. A possible way out is to compare algorithmic inference with expert classifications. This is the point of view we take here by conducting a thorough survey of the accuracy of reconstruction methods as compared with the Ethnologue expert classifications. We focus in particular on state-of-the-art distance-based methods for phylogeny reconstruction using worldwide linguistic databases. In order to assess the accuracy of the inferred trees we introduce and characterize two generalizations of standard definitions of distances between trees. Based on these scores we quantify the relative performances of the distance-based algorithms considered. Further we quantify how the completeness and the coverage of the available databases affect the accuracy of the reconstruction. Finally we draw some conclusions about where the accuracy of the reconstructions in historical linguistics stands and about the leading directions to improve it.     

Conditioned genome reconstruction: how to avoid choosing the conditioning genome

Genome phylogenies can be inferred from data on the presence and absence of genes across taxa. Logdet distances may be a good method, because they allow expected genome size to vary across the tree. Recently, Lake and Rivera proposed conditioned genome reconstruction (calculation of logdet distances using only those genes present in a conditioning genome) to deal with unobservable genes that are absent from every taxon of interest. We prove that their method can consistently estimate the topology for almost any choice of conditioning genome. Nevertheless, the choice of conditioning genome is important for small samples. For real bacterial genome data, different choices of conditioning genome can result in strong bootstrap support for different tree topologies. To overcome this problem, we developed supertree methods that combine information from all choices of conditioning genome. One of these methods, based on the BIONJ algorithm, performs well on simulated data and may have applications to other supertree problems. However, an analysis of 40 bacterial genomes using this method supports an incorrect clade of parasites. This is a common feature of model-based gene content methods and is due to parallel gene loss.     

What tangled web: barriers to rampant horizontal gene transfer

Dawkins in his The Selfish Gene(1) quite aptly applies the term "selfish" to parasitic repetitive DNA sequences endemic to eukaryotic genomes, especially vertebrates. Doolittle and Sapienza(2) as well as Orgel and Crick(3) enlivened this notion of selfish DNA with the identification of such repetitive sequences as remnants of mobile elements such as transposons. In addition, Orgel and Crick(3) associated parasitic DNA with a potential to outgrow their host genomes by propagating both vertically via conventional genome replication as well as infectiously by horizontal gene transfer (HGT) to other genomes. Still later, Doolittle(4) speculated that unchecked HGT between unrelated genomes so complicates phylogeny that the conventional representation of a tree of life would have to be replaced by a thicket or a web of life.(4) In contrast, considerable data now show that reconstructions based on whole genome sequences are consistent with the conventional "tree of life".(5-10) Here, we identify natural barriers that protect modern genome populations from the inroads of rampant HGT.     

FACTORS DETERMINING THE ACCURACY OF CLADOGRAM ESTIMATION: EVALUATION USING COMPUTER SIMULATION

We developed a simulation model of phylogenesis with which we generated a large number of phylogenies and associated data matrices. We examined the characteristics of these and evaluated the success of three taxonomic methods (Wagner parsimony, character compatibility, and UPGMA clustering) as estimators of phylogeny, paying particular attention to the consequences of changes in certain evolutionary assumptions: relative rate of evolution in three different evolutionary contexts (phyletic, parent lineage, and daughter lineage); relative rate of evolution in different directions (novel forward, convergent forward, or reverse); variation of evolutionary rates; and topology of the phylogenetic tree. Except for variation of evolutionary rates, all the evolutionary parameters that we controlled had significant effects on accuracy of phylogenetic reconstructions. Unexpectedly, the topology of the phylogeny was the most important single factor affecting accuracy; some phylogenies are more readily estimated than others for simply historical reasons. We conclude that none of the three estimation methods is very accurate, that the differences in accuracy among them are rather small, and that historical effects (the branching pattern of a phylogeny) may outweigh biological effects in determining the accuracy with which a phylogeny can be reconstructed.     

Towards optimal distance functions for stochastic substitution models

Distance based reconstruction methods of phylogenetic trees consist of two independent parts: first, inter-species distances are inferred assuming some stochastic model of sequence evolution; then the inferred distances are used to construct a tree. In this paper we concentrate on the task of inter-species distance estimation. Specifically, we characterize the family of valid distance functions for the assumed substitution model and show that deliberate selection of distance function significantly improves the accuracy of distance estimates and, consequently, also improves the accuracy of the reconstructed tree.Our contribution consists of three parts: first, we present a general framework for constructing families of additive distance functions for stochastic evolutionary models. Then, we present a method for selecting (near) optimal distance functions, and we conclude by presenting simulation results which support our theoretical analysis.     

Is multiple-sequence alignment required for accurate inference of phylogeny?

The process of inferring phylogenetic trees from molecular sequences almost always starts with a multiple alignment of these sequences but can also be based on methods that do not involve multiple sequence alignment. Very little is known about the accuracy with which such alignment-free methods recover the correct phylogeny or about the potential for increasing their accuracy. We conducted a large-scale comparison of ten alignment-free methods, among them one new approach that does not calculate distances and a faster variant of our pattern-based approach; all distance-based alignment-free methods are freely available from http://www.bioinformatics.org.au (as Python package decaf+py). We show that most methods exhibit a higher overall reconstruction accuracy in the presence of high among-site rate variation. Under all conditions that we considered, variants of the pattern-based approach were significantly better than the other alignment-free methods. The new pattern-based variant achieved a speed-up of an order of magnitude in the distance calculation step, accompanied by a small loss of tree reconstruction accuracy. A method of Bayesian inference from k-mers did not improve on classical alignment-free (and distance-based) methods but may still offer other advantages due to its Bayesian nature. We found the optimal word length k of word-based methods to be stable across various data sets, and we provide parameter ranges for two different alphabets. The influence of these alphabets was analyzed to reveal a trade-off in reconstruction accuracy between long and short branches. We have mapped the phylogenetic accuracy for many alignment-free methods, among them several recently introduced ones, and increased our understanding of their behavior in response to biologically important parameters. In all experiments, the pattern-based approach emerged as superior, at the expense of higher resource consumption. Nonetheless, no alignment-free method that we examined recovers the correct phylogeny as accurately as does an approach based on maximum-likelihood distance estimates of multiply aligned sequences.     

Correlation between strand asymmetry and phylogeny in mitochondrial DNA

An evolutionary distance is introduced in order to propose an efficient and feasible procedure for phylogeny studies. Our analysis are based on the strand asymmetry property of mitochondrial DNA, but can be applied to other genomes. Comparison of our results with those reported in conventional phylogenetic trees, gives confidence about our approximation. Our findings support the hypotheses about the origin of the skew and its dependence upon evolutionary pressures, and improves previous efforts on using the strand asymmetry property of genomes for phylogeny inference. For the evolutionary distance introduced here, we observe that the more adequate technique for tree reconstructions correspond to an average link method which employs a sequential clustering algorithm.     

Genome phylogenetic analysis based on extended gene contents

With the rapid growth of entire genome data, whole-genome approaches such as gene content become popular for genome phylogeny inference, including the tree of life. However, the underlying model for genome evolution is unclear, and the proposed (ad hoc) genome distance measure may violate the additivity. In this article, we formulate a stochastic framework for genome evolution, which provides a basis for defining an additive genome distance. However, we show that it is difficult to utilize the typical gene content data-i.e., the presence or absence of gene families across genomes-to estimate the genome distance. We solve this problem by introducing the concept of extended gene content; that is, the status of a gene family in a given genome could be absence, presence as single copy, or presence as duplicates, any of which can be used to estimate the genome distance and phylogenetic inference. Computer simulation shows that the new tree-making method is efficient, consistent, and fairly robust. The example of 35 microbial complete genomes demonstrates that it is useful not only to study the universal tree of life but also to explore the evolutionary pattern of genomes.     

Using PQ structures for genomic rearrangement phylogeny.

Various international efforts are underway to catalog the genomic similarities and variations in the human population. Some key discoveries such as inversions and transpositions within the members of the species have also been made over the years. The task of constructing a phylogeny tree of the members of the same species, given this knowledge and data, is an important problem. In this context, a key observation is that the "distance" between two members, or member and ancestor, within the species is small. In this paper, we pose the tree reconstruction problem exploiting some of these peculiarities. The central idea of the paper is based on the notion of minimal consensus PQ tree T of sequences. We use a modified PQ structure (termed oPQ) and show that both the number and size of each T is O(1). We further show that the tree reconstruction problem is statistically well-defined (Theorem 7) and give a simple scheme to construct the phylogeny tree and the common ancestors. Our preliminary experiments with simulated data look very promising.     

Algorithmic approaches to clonal reconstruction in heterogeneous cell populations

Background: The reconstruction of clonal haplotypes and their evolutionary history in evolving populations is a common problem in both microbial evolutionary biology and cancer biology. The clonal theory of evolution provides a theoretical framework for modeling the evolution of clones.Results: In this paper, we review the theoretical framework and assumptions over which the clonal reconstruction problem is formulated. We formally define the problem and then discuss the complexity and solution space of the problem. Various methods have been proposed to find the phylogeny that best explains the observed data. We categorize these methods based on the type of input data that they use (space-resolved or time-resolved), and also based on their computational formulation as either combinatorial or probabilistic. It is crucial to understand the different types of input data because each provides essential but distinct information for drastically reducing the solution space of the clonal reconstruction problem. Complementary information provided by single cell sequencing or from whole genome sequencing of randomly isolated clones can also improve the accuracy of clonal reconstruction. We briefly review the existing algorithms and their relationships. Finally we summarize the tools that are developed for either directly solving the clonal reconstruction problem or a related computational problem.Conclusions: In this review, we discuss the various formulations of the problem of inferring the clonal evolutionary history from allele frequeny data, review existing algorithms and catergorize them according to their problem formulation and solution approaches. We note that most of the available clonal inference algorithms were developed for elucidating tumor evolution whereas clonal reconstruction for unicellular genomes are less addressed. We conclude the review by discussing more open problems such as the lack of benchmark datasets and comparison of performance between available tools.     

Mitochondrial Genome of <Emphasis Type="Italic">Savalia savaglia</Emphasis> (Cnidaria,Hexacorallia) and Early Metazoan Phylogeny

Mitochondrial genomes have recently become widely used in animal phylogeny, mainly to infer the relationships between vertebrates and other bilaterians. However, only 11 of 723 complete mitochondrial genomes available in the public databases are of early metazoans, including cnidarians (Anthozoa, mainly Scleractinia) and sponges. Although some cnidarians (Medusozoa) are known to possess atypical linear mitochondrial DNA, the anthozoan mitochondrial genome is circular and its organization is similar to that of other metazoans. Because the phylogenetic relationships among Anthozoa as well as their relation to other early metazoans still need to be clarified, we tested whether sequencing the complete mitochondrial genome of Savalia savaglia, an anthozoan belonging to the order Zoantharia (=Zoanthidea), could be useful to infer such relationships. Compared to other anthozoans, S. savaglia’s genome is unusually long (20,766 bp) due to the presence of several noncoding intergenic regions (3691 bp). The genome contains all 13 protein coding genes commonly found in metazoans, but like other Anthozoa it lacks most of the tRNAs. Phylogenetic analyses of S. savaglia mitochondrial sequences show Zoantharia branching closely to other Hexacorallia, either as a sister group to Actiniaria or as a sister group to Actiniaria and Scleractinia. The close relationships suggested between Zoantharia and Actiniaria are reinforced by strong similarities in their gene order and the presence of similar introns in the COI and ND5 genes. Our study suggests that mitochondrial genomes can be a source of potentially valuable information on the phylogeny of Hexacorallia and may provide new insights into the evolution of early metazoans. Electronic Supplementary Material Electronic Supplementary material is available for this article at and accessible for authorised users. [Reviewing Editor: Dr. Axel Meyer]