Reconstructing Unrooted Phylogenetic Trees from Symbolic Ternary Metrics

Böcker and Dress (Adv Math 138:105–125, 1998) presented a 1-to-1 correspondence between symbolically dated rooted trees and symbolic ultrametrics. We consider the corresponding problem for unrooted trees. More precisely, given a tree T with leaf set X and a proper vertex coloring of its interior vertices, we can map every triple of three different leaves to the color of its median vertex. We characterize all ternary maps that can be obtained in this way in terms of 4- and 5-point conditions, and we show that the corresponding tree and its coloring can be reconstructed from a ternary map that satisfies those conditions. Further, we give an additional condition that characterizes whether the tree is binary, and we describe an algorithm that reconstructs general trees in a bottom-up fashion.     

On the Ancestral Compatibility of Two Phylogenetic Trees with Nested Taxa

Compatibility of phylogenetic trees is the most important concept underlying widely-used methods for assessing the agreement of different phylogenetic trees with overlapping taxa and combining them into common supertrees to reveal the tree of life. The notion of ancestral compatibility of phylogenetic trees with nested taxa was recently introduced. In this paper we analyze in detail the meaning of this compatibility from the points of view of the local structure of the trees, of the existence of embeddings into a common supertree, and of the joint properties of their cluster representations. Our analysis leads to a very simple polynomial-time algorithm for testing this compatibility, which we have implemented and is freely available for download from the BioPerl collection of Perl modules for computational biology.     

The Use (and Misuse) of Phylogenetic Trees in Comparative Behavioral Analyses

Phylogenetic comparative methods play a critical role in our understanding of the adaptive origin of primate behaviors. To incorporate evolutionary history directly into comparative behavioral research, behavioral ecologists rely on strong, well-resolved phylogenetic trees. Phylogenies provide the framework on which behaviors can be compared and homologies can be distinguished from similarities due to convergent or parallel evolution. Phylogenetic reconstructions are also of critical importance when inferring the ancestral state of behavioral patterns and when suggesting the evolutionary changes that behavior has undergone. Improvements in genome sequencing technologies have increased the amount of data available to researchers. Recently, several primate phylogenetic studies have used multiple loci to produce robust phylogenetic trees that include hundreds of primate species. These trees are now commonly used in comparative analyses and there is a perception that we have a complete picture of the primate tree. But how confident can we be in those phylogenies? And how reliable are comparative analyses based on such trees? Herein, we argue that even recent molecular phylogenies should be treated cautiously because they rely on many assumptions and have many shortcomings. Most phylogenetic studies do not model gene tree diversity and can produce misleading results, such as strong support for an incorrect species tree, especially in the case of rapid and recent radiations. We discuss implications that incorrect phylogenies can have for reconstructing the evolution of primate behaviors and we urge primatologists to be aware of the current limitations of phylogenetic reconstructions when applying phylogenetic comparative methods.     

Relating Phylogenetic Trees to Transmission Trees of Infectious Disease Outbreaks

Transmission events are the fundamental building blocks of the dynamics of any infectious disease. Much about the epidemiology of a disease can be learned when these individual transmission events are known or can be estimated. Such estimations are difficult and generally feasible only when detailed epidemiological data are available. The genealogy estimated from genetic sequences of sampled pathogens is another rich source of information on transmission history. Optimal inference of transmission events calls for the combination of genetic data and epidemiological data into one joint analysis. A key difficulty is that the transmission tree, which describes the transmission events between infected hosts, differs from the phylogenetic tree, which describes the ancestral relationships between pathogens sampled from these hosts. The trees differ both in timing of the internal nodes and in topology. These differences become more pronounced when a higher fraction of infected hosts is sampled. We show how the phylogenetic tree of sampled pathogens is related to the transmission tree of an outbreak of an infectious disease, by the within-host dynamics of pathogens. We provide a statistical framework to infer key epidemiological and mutational parameters by simultaneously estimating the phylogenetic tree and the transmission tree. We test the approach using simulations and illustrate its use on an outbreak of foot-and-mouth disease. The approach unifies existing methods in the emerging field of phylodynamics with transmission tree reconstruction methods that are used in infectious disease epidemiology.     

Dimensional Reduction for the General Markov Model on Phylogenetic Trees

We present a method of dimensional reduction for the general Markov model of sequence evolution on a phylogenetic tree. We show that taking certain linear combinations of the associated random variables (site pattern counts) reduces the dimensionality of the model from exponential in the number of extant taxa, to quadratic in the number of taxa, while retaining the ability to statistically identify phylogenetic divergence events. A key feature is the identification of an invariant subspace which depends only bilinearly on the model parameters, in contrast to the usual multi-linear dependence in the full space. We discuss potential applications including the computation of split (edge) weights on phylogenetic trees from observed sequence data.     

Phylogenetic Responses of Forest Trees to Global Change

In a rapidly changing biosphere, approaches to understanding the ecology and evolution of forest species will be critical to predict and mitigate the effects of anthropogenic global change on forest ecosystems. Utilizing 26 forest species in a factorial experiment with two levels each of atmospheric CO₂ and soil nitrogen, we examined the hypothesis that phylogeny would influence plant performance in response to elevated CO₂ and nitrogen fertilization. We found highly idiosyncratic responses at the species level. However, significant, among-genetic lineage responses were present across a molecularly determined phylogeny, indicating that past evolutionary history may have an important role in the response of whole genetic lineages to future global change. These data imply that some genetic lineages will perform well and that others will not, depending upon the environmental context.     

Mixed-up Trees: the Structure of Phylogenetic Mixtures

In this paper, we apply new geometric and combinatorial methods to the study of phylogenetic mixtures. The focus of the geometric approach is to describe the geometry of phylogenetic mixture distributions for the two state random cluster model, which is a generalization of the two state symmetric (CFN) model. In particular, we show that the set of mixture distributions forms a convex polytope and we calculate its dimension; corollaries include a simple criterion for when a mixture of branch lengths on the star tree can mimic the site pattern frequency vector of a resolved quartet tree. Furthermore, by computing volumes of polytopes we can clarify how “common” non-identifiable mixtures are under the CFN model. We also present a new combinatorial result which extends any identifiability result for a specific pair of trees of size six to arbitrary pairs of trees. Next we present a positive result showing identifiability of rates-across-sites models. Finally, we answer a question raised in a previous paper concerning “mixed branch repulsion” on trees larger than quartet trees under the CFN model. F.A. Matsen’s and M. Steel’s research was supported by the Allan Wilson Centre for Molecular Ecology and Evolution. E. Mossel’s research was supported by a Sloan fellowship in Mathematics, NSF awards DMS 0528488 and DMS 0548249 (CAREER) and by ONR grant N0014-07-1-05-06.     

Phylogenetic Framework for Trema (Celtidaceae)

We used ITS and trnL sequence data, analyzed separately and combined by MP, to explore species relationships and concepts in Trema (Celtidaceae), a pantropical genus of pioneer trees. Whether Trema is monophyletic or includes Parasponia is still unresolved. Three clades within Trema received moderate to high support, one from the New World and two from the Old World, but their relationships were not resolved. In the New World, specimens of T. micrantha formed two groups consistent with endocarp morphology. Group I, with smaller brown endocarps, is a highly supported clade sister to T. lamarckiana. Group II, with larger black endocarps, is poorly resolved with several subclades, including the highly supported T. integerrima clade. Both Old World clades contain Asian and African species, with three or more species in each region. Trema orientalis is not monophyletic: specimens from Africa formed a highly supported clade sister to T. africana, while those from Asia were sister to T. aspera from Australia.     

TreeVector: Scalable,Interactive, Phylogenetic Trees for the Web

Background

Phylogenetic trees are complex data forms that need to be graphically displayed to be human-readable. Traditional techniques of plotting phylogenetic trees focus on rendering a single static image, but increases in the production of biological data and large-scale analyses demand scalable, browsable, and interactive trees.

Methodology/Principal Findings

We introduce TreeVector, a Scalable Vector Graphics–and Java-based method that allows trees to be integrated and viewed seamlessly in standard web browsers with no extra software required, and can be modified and linked using standard web technologies. There are now many bioinformatics servers and databases with a range of dynamic processes and updates to cope with the increasing volume of data. TreeVector is designed as a framework to integrate with these processes and produce user-customized phylogenies automatically. We also address the strengths of phylogenetic trees as part of a linked-in browsing process rather than an end graphic for print.

Conclusions/Significance

TreeVector is fast and easy to use and is available to download precompiled, but is also open source. It can also be run from the web server listed below or the user''s own web server. It has already been deployed on two recognized and widely used database Web sites.     

Inferring Species Trees from Gene Trees: A Phylogenetic Analysis of the Elapidae (Serpentes) Based on the Amino Acid Sequences of Venom Proteins

Toward the goal of recovering the phylogenetic relationships among elapid snakes, we separately found the shortest trees from the amino acid sequences for the venom proteins phospholipase A₂and the short neurotoxin, collectively representing 32 species in 16 genera. We then applied a method we term gene tree parsimony for inferring species trees from gene trees that works by finding the species tree which minimizes the number of deep coalescences or gene duplications plus unsampled sequences necessary to fit each gene tree to the species tree. This procedure, which is both logical and generally applicable, avoids many of the problems of previous approaches for inferring species trees from gene trees. The results support a division of the elapids examined into sister groups of the Australian and marine (laticaudines and hydrophiines) species, and the African and Asian species. Within the former clade, the sea snakes are shown to be diphyletic, with the laticaudines and hydrophiines having separate origins. This finding is corroborated by previous studies, which provide support for the usefulness of gene tree parsimony.     

利用DNA序列构建系统树的方法介绍

利用DNA序列进行系统发生分析是分子进化研究的必要手段。构建系统树的方法有距离法、简约法、最大似然法以及贝叶斯推断法等。要解决特定的系统发生问题,首先要挑选合理的分类群及序列,尽量减少数据的偏倚,然后选择构树方法,最后还要对结果进行评价并给出进化学上的解释。本文讨论了挑选数据的原则及存在的问题,介绍了几种构树方法的基本原理及步骤,并列举了它们的优缺点。Abstract: Construction of phylogenetic trees is a key means in molecular evolutionary studies. The methods of constructing phylogenetic trees include the distance-based methods, parsimony, maximum likelihood, and Bayesian inference methods. To resolve a special problem about phylogeny, several notices are necessary: first, to select the reasonable data at less bias as possible; second, to choose the proper method to reconstruct phylogenetic tree; third, to evaluate the conclusions and explain them on the field of evolution. The present paper provides a brief introduction of the principles of data selection and tree-construction methods, and discusses about their advantage and disadvantage points.     

Identification of Horizontal Gene Transfer from Phylogenetic Gene Trees

We suggest a new procedure to search for the genes with horizontal transfer events in their evolutionary history. The search is based on analysis of topology difference between the phylogenetic trees of gene (protein) groups and the corresponding phylogenetic species trees. Numeric values are introduced to measure the discrepancy between the trees. This approach was applied to analyze 40 prokaryotic genomes classified into 132 classes of orthologs. This resulted in a list of the candidate genes for which the hypothesis of horizontal transfer in evolution looks true.     

Efficient Peak-Labeling Algorithms for Whole-Sample Mass Spectrometry Proteomics

Whole-sample mass spectrometry (MS) proteomics allows for a parallel measurement of hundreds of proteins present in a variety of biospecimens. Unfortunately, the association between MS signals and these proteins is not straightforward. The need to interpret mass spectra demands the development of methods for accurate labeling of ion species in such profiles. To aid this process, we have developed a new peak-labeling procedure for associating protein and peptide labels with peaks. This computational method builds upon characteristics of proteins expected to be in the sample, such as the amino sequence, mass weight, and expected concentration within the sample. A new probabilistic score that incorporates this information is proposed. We evaluate and demonstrate our method's ability to label peaks first on simulated MS spectra and then on MS spectra from human serum with a spiked-in calibration mixture.     

tidy tree: A New Layout for Phylogenetic Trees

Many layouts exist for visualizing phylogenetic trees, allowing to display the same information (evolutionary relationships) in different ways. For large phylogenies, the choice of the layout is a key element, because the printable area is limited, and because interactive on-screen visualizers can lead to unreadable phylogenetic relationships at high zoom levels. A visual inspection of available layouts for rooted trees reveals large empty areas that one may want to fill in order to use less drawing space and eventually gain readability. This can be achieved by using the nonlayered tidy tree layout algorithm that was proposed earlier but was never used in a phylogenetic context so far. Here, we present its implementation, and we demonstrate its advantages on simulated and biological data (the measles virus phylogeny). Our results call for the integration of this new layout in phylogenetic software. We implemented the nonlayered tidy tree layout in R language as a stand-alone function (available at https://github.com/damiendevienne/non-layered-tidy-trees), as an option in the tree plotting function of the R package ape, and in the recent tool for visualizing reconciled phylogenetic trees thirdkind (https://github.com/simonpenel/thirdkind/wiki).     

Analyzing the Fitch Method for Reconstructing Ancestral States on Ultrametric Phylogenetic Trees

The accuracy of the Fitch method for reconstructing ancestral states on ultrametric phylogenetic trees is studied. Two recurrence relations for computing the accuracy are given here. Using these relations, we analyze the convergence of the accuracy of the Fitch method for reconstructing the root state on a complete binary tree of 2 ⁿ leaves as n goes to infinity, present a closed-form formula for the accuracy on ultrametric comb trees, and provide a lower bound on the accuracy on arbitrary ultrametric phylogenetic trees.     

Genetic Distances and Reconstruction of Phylogenetic Trees from Microsatellite DNA

Recently many investigators have used microsatellite DNA loci for studying the evolutionary relationships of closely related populations or species, and some authors proposed new genetic distance measures for this purpose. However, the efficiencies of these distance measures in obtaining the correct tree topology remains unclear. We therefore investigated the probability of obtaining the correct topology (P(C)) for these new distances as well as traditional distance measures by using computer simulation. We used both the infinite-allele model (IAM) and the stepwise mutation model (SMM), which seem to be appropriate for classical markers and microsatellite loci, respectively. The results show that in both the IAM and SMM CAVALLI-SFORZA and EDWARDS'' chord distance (D(C)) and NEI et al.''s D(A) distance generally show higher P(C) values than other distance measures, whether the bottleneck effect exists or not. For estimating evolutionary times, however, NEI''s standard distance and GOLDSTEIN et al.''s (δ μ)(2) are more appropriate than other distances. Microsatellite DNA seems to be very useful for clarifying the evolutionary relationships of closely related populations.     

Rapid Evaluation of Least-Squares and Minimum-Evolution Criteria on Phylogenetic Trees

We present fast new algorithms for evaluating trees with respectto least squares and minimum evolution (ME), the most commonlyused criteria for inferring phylogenetic trees from distancedata. The new algorithms include an optimal O(N2) time algorithmfor calculating the edge (branch or internode) lengths on atree according to ordinary or unweighted least squares (OLS);an O(N3) time algorithm for edge lengths under weighted leastsquares (WLS) including the Fitch-Margoliash method; and anoptimal O(N4) time algorithm for generalized least-squares (GLS)edge lengths (where N is the number of taxa in the tree). TheME criterion is based on the sum of edge lengths. Consequently,the edge lengths algorithms presented here lead directly toO(N2), O(N3), and O(N4) time algorithms for ME under OLS, WLS,and GLS, respectively. All of these algorithms are as fast asor faster than any of those previously published, and the algorithmsfor OLS and GLS are the fastest possible (with respect to orderof computational complexity). A major advantage of our new methodsis that they are as well adapted to multifurcating trees asthey are to binary trees. An optimal algorithm for determiningpath lengths from a tree with given edge lengths is also developed.This leads to an optimal O(N2) algorithm for OLS sums of squaresevaluation and corresponding O(N3) and O(N4) time algorithmsfor WLS and GLS sums of squares, respectively. The GLS algorithmis time-optimal if the covariance matrix is already inverted.The speed of each algorithm is assessed analytically—thespeed increases we calculate are confirmed by the dramatic speedincreases resulting from their implementation in PAUP* 4.0.The new algorithms enable far more extensive tree searches andstatistical evaluations (e.g., bootstrap, parametric bootstrap,or jackknife) in the same amount of time. Hopefully, the fastalgorithms for WLS and GLS will encourage the use of these criteriafor evaluating trees and their edge lengths (e.g., for approximatedivergence time estimates), since they should be more statisticallyefficient than OLS.     

Exploring the Phylogenetic Structure of Ecological Communities: An Example for Rain Forest Trees

Because of the correlation expected between the phylogenetic relatedness of two taxa and their net ecological similarity, a measure of the overall phylogenetic relatedness of a community of interacting organisms can be used to investigate the contemporary ecological processes that structure community composition. I describe two indices that use the number of nodes that separate taxa on a phylogeny as a measure of their phylogenetic relatedness. As an example of the use of these indices in community analysis, I compared the mean observed net relatedness of trees (>/=10 cm diameter at breast height) in each of 28 plots (each 0.16 ha) in a Bornean rain forest with the net relatedness expected if species were drawn randomly from the species pool (of the 324 species in the 28 plots), using a supertree that I assembled from published sources. I found that the species in plots were more phylogenetically related than expected by chance, a result that was insensitive to various modifications to the basic methodology. I tentatively infer that variation in habitat among plots causes ecologically more similar species to co-occur within plots. Finally, I suggest a range of applications for phylogenetic relatedness measures in community analysis.     

利用分子进化树计算蛋白质的特异进化速率

本文提出了一种计算蛋白质绝对进化距离和进化速率的方法,它根据现有同源蛋白质的序列构建分子进化树,并推断进化过程中各结点处的共同祖先序列,根据某成员与某结点处共同祖先序列的氨基酸差异百分率,计算该蛋白质序列的特异进化距离和进化速率。比较我们的算法和Ｄａｙｈｏｆｆ等的模拟统计方法表明,我们的算法在一定范围内是正确的。结合计算哺乳动物红细胞生成素的进化速率,讨论了本算法在分子进化研究中的应用。