BIMLR: A method for constructing rooted phylogenetic networks from rooted phylogenetic trees

Rooted phylogenetic trees constructed from different datasets (e.g. from different genes) are often conflicting with one another, i.e. they cannot be integrated into a single phylogenetic tree. Phylogenetic networks have become an important tool in molecular evolution, and rooted phylogenetic networks are able to represent conflicting rooted phylogenetic trees. Hence, the development of appropriate methods to compute rooted phylogenetic networks from rooted phylogenetic trees has attracted considerable research interest of late. The C_ASS algorithm proposed by van Iersel et al. is able to construct much simpler networks than other available methods, but it is extremely slow, and the networks it constructs are dependent on the order of the input data. Here, we introduce an improved C_ASS algorithm, BIMLR. We show that BIMLR is faster than C_ASS and less dependent on the input data order. Moreover, BIMLR is able to construct much simpler networks than almost all other methods. BIMLR is available at http://nclab.hit.edu.cn/wangjuan/BIMLR/.     

Nodal distances for rooted phylogenetic trees

Dissimilarity measures for (possibly weighted) phylogenetic trees based on the comparison of their vectors of path lengths between pairs of taxa, have been present in the systematics literature since the early seventies. For rooted phylogenetic trees, however, these vectors can only separate non-weighted binary trees, and therefore these dissimilarity measures are metrics only on this class of rooted phylogenetic trees. In this paper we overcome this problem, by splitting in a suitable way each path length between two taxa into two lengths. We prove that the resulting splitted path lengths matrices single out arbitrary rooted phylogenetic trees with nested taxa and arcs weighted in the set of positive real numbers. This allows the definition of metrics on this general class of rooted phylogenetic trees by comparing these matrices through metrics in spaces M_n(\mathbb R){\mathcal{M}_n(\mathbb {R})} of real-valued n × n matrices. We conclude this paper by establishing some basic facts about the metrics for non-weighted phylogenetic trees defined in this way using L ^p metrics on M_n(\mathbb R){\mathcal{M}_n(\mathbb {R})}, with ${p \in \mathbb {R}_{ >0 }}${p \in \mathbb {R}_{ >0 }}.     

Ancient horizontal gene transfer can benefit phylogenetic reconstruction

Although horizontal gene transfer (HGT) is usually considered a disruptive force in recovering organismal phylogeny, it creates important phylogenetic information. In the 'net of life', the recipient of an ancient gene transfer can be the ancestor of a lineage that inherits the transferred gene; thus, the transferred gene marks the recipient and its descendants as a monophyletic group. Ancient gene transfer events can also reveal the order of emergence of donor and recipient lineages. In addition, these ancient events can significantly shape the genetic systems of the recipients and can play a part in their long-term evolution. In this article, we discuss the recent progress in phylogenetic application of ancient HGTs and describe two examples of transfer events to the ancestor of red algae and green plants that support a common origin of these two groups. We also address the potential pitfalls of this application.     

Identifying dramatic selection shifts in phylogenetic trees

Background

The rate of evolution varies spatially along genomes and temporally in time. The presence of evolutionary rate variation is an informative signal that often marks functional regions of genomes and historical selection events. There exist many tests for temporal rate variation, or heterotachy, that start by partitioning sampled sequences into two or more groups and testing rate homogeneity among the groups. I develop a Bayesian method to infer phylogenetic trees with a divergence point, or dramatic temporal shifts in selection pressure that affect many nucleotide sites simultaneously, located at an unknown position in the tree.

Results

Simulation demonstrates that the method is most able to detect divergence points when rate variation and the number of affected sites is high, but not beyond biologically relevant values. The method is applied to two viral data sets. A divergence point is identified separating the B and C subtypes, two genetically distinct variants of HIV that have spread into different human populations with the AIDS epidemic. In contrast, no strong signal of temporal rate variation is found in a sample of F and H genotypes, two genetic variants of HBV that have likely evolved with humans during their immigration and expansion into the Americas.

Conclusion

Temporal shifts in evolutionary rate of sufficient magnitude are detectable in the history of sampled sequences. The ability to detect such divergence points without the need to specify a prior hypothesis about the location or timing of the divergence point should help scientists identify historically important selection events and decipher mechanisms of evolution.

     

Computational and phylogenetic validation of nematode horizontal gene transfer

Sequencing of expressed genes has shown that nematodes, particularly the plant-parasitic nematodes, have genes purportedly acquired from other kingdoms by horizontal gene transfer. The prevailing orthodoxy is that such transfer has been a driving force in the evolution of niche specificity, and a recent paper in BMC Evolutionary Biology that presents a detailed phylogenetic analysis of cellulase genes in the free-living nematode Pristionchus pacificus at the species, genus and family levels substantiates this hypothesis.     

Methods of horizontal gene transfer determination using phylogenetic data

A new approach for comparative analysis of multiple trees reconstructed for representative protein families is proposed. This approach is based on the hypothesis of gene duplication, gene loss and horizontal gene transfer and makes use of stochastic methods and optimization. We present a species tree of 40 prokaryotic organisms obtained by our algorithm on the basis of 132 clusters of orthologous groups of proteins (COGs) from the GenBank of the National Center for Biotechnology Information (USA). We also present a computer technology intended to determine horizontally transferred genes. Some application results of the technology, based on comparative analysis of protein and species trees, are given.     

A balance index for phylogenetic trees based on rooted quartets

Journal of Mathematical Biology - We define a new balance index for rooted phylogenetic trees based on the symmetry of the evolutive history of every set of 4 leaves. This index makes sense for...     

Identifying the rooted species tree from the distribution of unrooted gene trees under the coalescent

Gene trees are evolutionary trees representing the ancestry of genes sampled from multiple populations. Species trees represent populations of individuals—each with many genes—splitting into new populations or species. The coalescent process, which models ancestry of gene copies within populations, is often used to model the probability distribution of gene trees given a fixed species tree. This multispecies coalescent model provides a framework for phylogeneticists to infer species trees from gene trees using maximum likelihood or Bayesian approaches. Because the coalescent models a branching process over time, all trees are typically assumed to be rooted in this setting. Often, however, gene trees inferred by traditional phylogenetic methods are unrooted. We investigate probabilities of unrooted gene trees under the multispecies coalescent model. We show that when there are four species with one gene sampled per species, the distribution of unrooted gene tree topologies identifies the unrooted species tree topology and some, but not all, information in the species tree edges (branch lengths). The location of the root on the species tree is not identifiable in this situation. However, for 5 or more species with one gene sampled per species, we show that the distribution of unrooted gene tree topologies identifies the rooted species tree topology and all its internal branch lengths. The length of any pendant branch leading to a leaf of the species tree is also identifiable for any species from which more than one gene is sampled.     

Identification of the horizontal gene transfer based on phylogenetic data

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.     

HGT-Gen: a tool for generating a phylogenetic tree with horizontal gene transfer

Horizontal gene transfer (HGT) is a common event in prokaryotic evolution. Therefore, it is very important to consider HGT in the study of molecular evolution of prokaryotes. This is true also for conducting computer simulations of their molecular phylogeny because HGT is known to be a serious disturbing factor for estimating their correct phylogeny. To the best of our knowledge, no existing computer program has generated a phylogenetic tree with HGT from an original phylogenetic tree. We developed a program called HGT-Gen that generates a phylogenetic tree with HGT on the basis of an original phylogenetic tree of a protein or gene. HGT-Gen converts an operational taxonomic unit or a clade from one place to another in a given phylogenetic tree. We have also devised an algorithm to compute the average length between any pair of branches in the tree. It defines and computes the relative evolutionary time to normalize evolutionary time for each lineage. The algorithm can generate an HGT between a pair of donor and acceptor lineages at the same evolutionary time. HGT-Gen is used with a sequence-generating program to evaluate the influence of HGT on the molecular phylogeny of prokaryotes in a computer simulation study.

Availability

The database is available for free at http://www.grl.shizuoka.ac.jp/˜thoriike/HGT-Gen.html     

Correlation between Shapley values of rooted phylogenetic trees under the beta-splitting model

Journal of Mathematical Biology - In recent years, several different versions of the Shapley value have been introduced in phylogenetics for the purpose of ranking biodiversity data in order to...     

Organization of butyrate synthetic genes in human colonic bacteria: phylogenetic conservation and horizontal gene transfer

Butyrate producers constitute an important bacterial group in the human large intestine. Butyryl-CoA is formed from two molecules of acetyl-CoA in a process resembling beta-oxidation in reverse. Three different arrangements of the six genes coding for this pathway have been found in low mol% G+C-content gram-positive human colonic bacteria using DNA sequencing and degenerate PCR. Gene arrangements were strongly conserved within phylogenetic groups defined by 16S rRNA gene sequence relationships. In the case of one of the genes, encoding beta-hydroxybutyryl-CoA dehydrogenase, however, sequence relationships were strongly suggestive of horizontal gene transfer between lineages. The newly identified gene for butyryl-CoA CoA-transferase, which performs the final step in butyrate formation in most known human colonic bacteria, was not closely linked to these central pathway genes.     

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.     

Genetic and phylogenetic evidence for horizontal gene transfer among ecologically disparate groups of marine Vibrio

Vibrio represents a diverse bacterial genus found in different niches of the marine environment, including numerous genera of marine sponges (phylum Porifera), inhabiting different depths and regions of benthic seas, that are potentially important in driving adaptive change among Vibrio spp. Using 16S rRNA gene sequencing, a previous study showed that sponge‐derived (SD) vibrios clustered with their mainstream counterparts present in shallow, coastal ecosystems, suggesting a genetic relatedness between these populations. Sequences from the topA, ftsZ, mreB, rpoD, rctB and toxR genes were used to investigate the degree of relatedness existing between these two separate populations by examining their phylogenetic and genetic disparity. Phylogenies were constructed from the concatenated sequences of the six housekeeping genes using maximum‐parsimony, maximum‐likelihood and neighbour‐joining algorithms. Genetic recombination was evaluated using the incongruence length difference test, Split decomposition and measuring overall compatibility of sites. This combined technical approach provided evidence that SD Vibrio strains are largely genetically homologous to their shallow‐water counterparts. Moreover, the analyses conducted support the existence of extensive horizontal gene transfer between these two groups, supporting the idea of a single panmictic population structure among vibrios from two seemingly distinct, marine environments.     

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.     

Tree reconciliation: reconstruction of species evolution by phylogenetic gene trees

It is well known that phylogenetic trees derived from different protein families are often incongruent. This is explained by mapping errors and by the essential processes of gene duplication, loss, and horizontal transfer. Therefore, the problem is to derive a "consensus" tree best fitting the given set of gene trees. This work presents a new method of deriving this tree. The method is different from the existing ones, since it considers not only the topology of the initial gene trees, but also the reliability of their branches. Thereby one can explicitly take into account the possible errors in the gene trees caused by the absence of reliable models of sequence evolution, by uneven evolution of different gene families and taxonomic groups, etc.