Growth models (including terminal and segmental branching) for topological binary trees

A growth model for topological trees is formulated as a generalization of the terminal and segmental growth model. For this parameterized growth model, expressions are derived for the partition probabilities (probabilities of subtree pairs of certain degrees). The probabilities of complete trees are easily derived from these partition probabilities.     

Probability distributions of ancestries and genealogical distances on stochastically generated rooted binary trees

The stationary birth-only, or Yule-Furry, process for rooted binary trees has been analysed with a view to developing explicit expressions for two fundamental statistical distributions: the probability that a randomly selected leaf is preceded by N nodes, or “ancestors”, and the probability that two randomly selected leaves are separated by N nodes. For continuous-time Yule processes, the first of these distributions is presented in closed analytical form as a function of time, with time being measured with respect to the moment of “birth” of the common ancestor (which is essentially inaccessible to phylogenetic analysis), or with respect to the instant at which the first bifurcation occurred.The second distribution is shown to follow in an iterative manner from a hierarchy of second-order ordinary differential equations.For Yule trees of a given number n of tips, expressions have been derived for the mean and variance for each of these distributions as functions of n, as well as for the distributions themselves.In addition, it is shown how the methods developed to obtain these distributions can be employed to find, with minor effort, expressions for the expectation values of two statistics on Yule trees, the Sackin index (sum over all root-to-leaf distances), and the sum over all leaf-to-leaf distances.     

The probability of topological concordance of gene trees and species trees

The concordance of gene trees and species trees is reconsidered in detail, allowing for samples of arbitrary size to be taken from the species. A sense of concordance for gene tree and species tree topologies is clarified, such that if the "collapsed gene tree" produced by a gene tree has the same topology as the species tree, the gene tree is said to be topologically concordant with the species tree. The term speciodendric is introduced to refer to genes whose trees are topologically concordant with species trees. For a given three-species topology, probabilities of each of the three possible collapsed gene tree topologies are given, as are probabilities of monophyletic concordance and concordance in the sense of N. Takahata (1989), Genetics 122, 957-966. Increasing the sample size is found to increase the probability of topological concordance, but a limit exists on how much the topological concordance probability can be increased. Suggested sample sizes beyond which this probability can be increased only minimally are given. The results are discussed in terms of implications for molecular studies of phylogenetics and speciation.     

Coalescent time distributions in trees of arbitrary size

The relationship between speciation times and the corresponding times of gene divergence is of interest in phylogenetic inference as a means of understanding the past evolutionary dynamics of populations and of estimating the timing of speciation events. It has long been recognized that gene divergence times might substantially pre-date speciation events. Although the distribution of the difference between these has previously been studied for the case of two populations, this distribution has not been explicitly computed for larger species phylogenies. Here we derive a simple method for computing this distribution for trees of arbitrary size. A two-stage procedure is proposed which (i) considers the probability distribution of the time from the speciation event at the root of the species tree to the gene coalescent time conditionally on the number of gene lineages available at the root; and (ii) calculates the probability mass function for the number of gene lineages at the root. This two-stage approach dramatically simplifies numerical analysis, because in the first step the conditional distribution does not depend on an underlying species tree, while in the second step the pattern of gene coalescence prior to the species tree root is irrelevant. In addition, the algorithm provides intuition concerning the properties of the distribution with respect to the various features of the underlying species tree. The methodology is complemented by developing probabilistic formulae and software, written in R. The method and software are tested on five-taxon species trees with varying levels of symmetry. The examples demonstrate that more symmetric species trees tend to have larger mean coalescent times and are more likely to have a unimodal gamma-like distribution with a long right tail, while asymmetric trees tend to have smaller mean coalescent times with an exponential-like distribution. In addition, species trees with longer branches generally have shorter mean coalescent times, with branches closest to the root of the tree being most influential.     

Numbering binary trees with labeled terminal vertices

For each rooted binary tree witht labeled terminal vertices (leaves) a natural number can be assigned uniquely. Unrooted trees witht labeled terminal vertices andt-2 unlabeled internal vertices of degree 3 can also be numbered uniquely using the same convention. Rooted trees in which the hights of the internal vertices are rank ordered are also considered. Applications to problems in taxonomy are discussed.     

A congruence index for testing topological similarity between trees

MOTIVATION: Phylogenetic trees are omnipresent in evolutionary biology and the comparison of trees plays a central role there. Tree congruence statistics are based on the null hypothesis that two given trees are not more congruent (topologically similar) than expected by chance. Usually, one searches for the most parsimonious evolutionary scenario relating two trees and then one tests the null hypothesis by generating a high number of random trees and comparing these to the one between the observed trees. However, this approach requires a lot of computational work (human and machine) and the results depend on the evolutionary assumptions made. RESULTS: We propose an index, I(cong), for testing the topological congruence between trees with any number of leaves, based on maximum agreement subtrees (MAST). This index is straightforward, simple to use, does not rely on parametrizing the likelihood of evolutionary events, and provides an associated confidence level. AVAILABILITY: A web site has been created that allows rapid and easy online computation of this index and of the associated P-value at http://www.ese.u-psud.fr/bases/upresa/pages/devienne/index.html     

Algorithms for constructing phylogenetic trees of maximum topological similarity

The paper concerns the practical realization of the maximum topologic similarity principle for phylogenetic reconstruction. This novel principle is described in the accompanying paper. Two algorithms that were embodied in the computer program allow one to find out the unique tree in case when source data admit the existence of such tree. In case if numerous parallel mutations make such precise realization impossible, algorithms allow one to obtain approximations to the maximum topologic similarity trees with a high computation efficiency. Examples illustrating use of these algorithms, as well as discussion of biological consistency of the novel concept are presented.     

Species trees from gene trees: reconstructing Bayesian posterior distributions of a species phylogeny using estimated gene tree distributions

The desire to infer the evolutionary history of a group of species should be more viable now that a considerable amount of multilocus molecular data is available. However, the current molecular phylogenetic paradigm still reconstructs gene trees to represent the species tree. Further, commonly used methods of combining data, such as the concatenation method, are known to be inconsistent in some circumstances. In this paper, we propose a Bayesian hierarchical model to estimate the phylogeny of a group of species using multiple estimated gene tree distributions, such as those that arise in a Bayesian analysis of DNA sequence data. Our model employs substitution models used in traditional phylogenetics but also uses coalescent theory to explain genealogical signals from species trees to gene trees and from gene trees to sequence data, thereby forming a complete stochastic model to estimate gene trees, species trees, ancestral population sizes, and species divergence times simultaneously. Our model is founded on the assumption that gene trees, even of unlinked loci, are correlated due to being derived from a single species tree and therefore should be estimated jointly. We apply the method to two multilocus data sets of DNA sequences. The estimates of the species tree topology and divergence times appear to be robust to the prior of the population size, whereas the estimates of effective population sizes are sensitive to the prior used in the analysis. These analyses also suggest that the model is superior to the concatenation method in fitting these data sets and thus provides a more realistic assessment of the variability in the distribution of the species tree that may have produced the molecular information at hand. Future improvements of our model and algorithm should include consideration of other factors that can cause discordance of gene trees and species trees, such as horizontal transfer or gene duplication.     

Protein classification based on propagation of unrooted binary trees

We present two efficient network propagation algorithms that operate on a binary tree, i.e., a sparse-edged substitute of an entire similarity network. TreeProp-N is based on passing increments between nodes while TreeProp-E employs propagation to the edges of the tree. Both algorithms improve protein classification efficiency.     

New measures of topological stability in phylogenetic trees - Taking taxon composition into account

In phylogenetic trees the addition and removal of taxa has large effects on tree topology, hence measures of branch support and tree stability should account for taxonomic composition. Currently no comprehensive system of composition-dependent parameters exists in any cladistic or phenetic strategy. We introduce several values and indices based on a modification of the original jackknife resampling. Their advantage is a complete evaluation and optimization of taxon composition in phylogenetic data. While related to the Jackknife Monophyly Index (JMI), our system of support measures expands beyond parsimony analyses, and includes indices estimating support for the entire phylogenetic tree based on individual branch supports.     

The effects of topological inaccuracy in evolutionary trees on the phylogenetic comparative method of independent contrasts

Computer simulations were used to test the effect of increasing phylogenetic topological inaccuracy on the results obtained from correlation tests of independent contrasts. Predictably, increasing the number of disruptions in the tree increases the likelihood of significant error in the r values produced and in the statistical conclusions drawn from the analysis. However, the position of the disruption in the tree is important: Disruptions closer to the tips of the tree have a greater effect than do disruptions that are close to the root of the tree. Independent contrasts derived from inaccurate topologies are more likely to lead to erroneous conclusions when there is a true significant relationship between the variables being tested (i.e., they tend to be conservative). The results also suggest that random phylogenies perform no better than nonphylogenetic analyses and, under certain conditions, may perform even worse than analyses using raw species data. Therefore, the use of random phylogenies is not beneficial in the absence of knowledge of the true phylogeny.     

Analysis of binary trees when occasional multifurcations can be considered as aggregates of bifurcations

The geometrical properties of neurons are important for the way they function within neural circuits. The arborescent processes of neurons that are necessary for the transmission of the information are formed by branching and elongation of segments. In studies that model the outgrowth the tree structures have generally been considered as binary. However, multifurcations do occur. It will be shown that if the multifurcations can be considered as aggregates of bifurcations they may be included in the topological analysis of neuronal branching patterns.     

Algorithms for MDC-based multi-locus phylogeny inference: beyond rooted binary gene trees on single alleles

One of the criteria for inferring a species tree from a collection of gene trees, when gene tree incongruence is assumed to be due to incomplete lineage sorting (ILS), is Minimize Deep Coalescence (MDC). Exact algorithms for inferring the species tree from rooted, binary trees under MDC were recently introduced. Nevertheless, in phylogenetic analyses of biological data sets, estimated gene trees may differ from true gene trees, be incompletely resolved, and not necessarily rooted. In this article, we propose new MDC formulations for the cases where the gene trees are unrooted/binary, rooted/non-binary, and unrooted/non-binary. Further, we prove structural theorems that allow us to extend the algorithms for the rooted/binary gene tree case to these cases in a straightforward manner. In addition, we devise MDC-based algorithms for cases when multiple alleles per species may be sampled. We study the performance of these methods in coalescent-based computer simulations.     

Radial distributions of Cd in stems of oak trees (Quercus robur L.) re-analyzed after 10 years

Radial distribution patterns of Cd were determined in stems of the same oak trees (Quercus robur L.) in 1983 and again in 1994. On both sampling dates the same distribution patterns were generally observed. Highest concentrations of Cd were found at the sapwood-heart-wood transition. A sharp drop over this boundary towards inner parts of the stems occurred in all trees. In the decade between the two investigations the sapwood-heartwood boundaries had shifted outwards by 9–11 annual rings. The Cd peaks at the boundaries were shifted by approximately the same interval. The results suggest that the described Cd peaks are mobile in a radial direction. The present location of such peaks cannot be used to infer the pollution history of the tree's environment. The Cd accumulation at the sapwood-heartwood boundary is probably affected by physiological processes in the wood. Thus it is concluded that radial distributions of Cd in stems of oak trees are no reliable source of information for retrospective monitoring of past time pollution levels.     

Monte Carlo sampling and principal component analysis of flux distributions yield topological and modular information on metabolic networks

The work presented here uses Monte Carlo random sampling combined with flux balance analysis and linear programming to analyse the steady-state flux distributions on the surface of the glucose-ammonia phenotypic phase plane of an Escherichia coli system grown on glucose-minimal medium. The distribution of allowable glucose and ammonia uptake rates showed a triangular shape, the apex corresponding to maximum growth rate. The exact shape, e.g. the diagonal boundary is determined by the relative amounts of nutrients required for growth. The logarithm of flux values has a normal distribution, e.g. there is a log normal distribution, and most of the reactions have an order of magnitude between 10(-1) and 1. The increase in the number of blocked reactions as growth switched from aerobic to micro-aerobic phase and the presence of alternate networks for a single optimal solution were both reflections of the variability of pathway utilization for survival and growth. Principal component analysis (PCA) provided us with significant clues on the correlations between individual reactions and correlations between sets of reactions. Furthermore, PCA identified the most influential reactions of the system. The PCA score plots clearly distinguish two different growth phases, micro-aerobic and aerobic. The loading plots for each growth phase showed both the impact of the reactions on the model and the clustering of reactions that are highly correlated. These results have proved that PCA is a promising way to analyse correlations in high-dimensional solution spaces and to detect modular patterns among reactions in a network.     

Fig trees at the northern limit of their range: the distributions of cryptic pollinators indicate multiple glacial refugia

Climatic oscillations during the last few million years had well‐documented effects on the distributions and genomes of temperate plants and animals, but much less is known of their impacts on tropical and subtropical species. In contrast to Europe and North America, ice‐sheets did not cover most of China during glacial periods, and the effects of glacial cycles were less dramatic. Fig trees are a predominantly tropical group pollinated by host‐specific fig wasps. We employed partial mitochondrial COI (918 bp) and nuclear ITS2 (462 bp) gene sequences to investigate the genetic structure and demographic histories of the wasps that pollinate the subtropical Ficus pumila var. pumila in Southeastern China. Deep genetic divergence in both mitochondrial (7.2–11.6%) and nuclear genes (1.6–2.9%) indicates that three pollinator species are present and that they diverged about 4.72 and 6.00 Myr bp . This predates the Quaternary ice ages, but corresponds with the formation of the Taiwan Strait and uplifting of the Wuyi–Xianxia Mountains. The three pollinators have largely allopatric distribution patterns in China and display different postglacial demographic histories. Wiebesia spp. 1 and 2 occupy, respectively, the northern and southern regions of the mainland host range. Their populations both underwent significant postglacial spatial expansions, but at different times and at different rates. Wiebesia sp. 3 is largely restricted to northern islands and shows less evidence of recent population expansion. Their mainly allopatric distributions and different demographic histories are consistent with host plant postglacial expansion from three distinct refugia and suggest one mechanism whereby fig trees gain multiple pollinators.