Inferring phylogenetic networks by the maximum parsimony criterion: a case study

Horizontal gene transfer (HGT) may result in genes whose evolutionary histories disagree with each other, as well as with the species tree. In this case, reconciling the species and gene trees results in a network of relationships, known as the "phylogenetic network" of the set of species. A phylogenetic network that incorporates HGT consists of an underlying species tree that captures vertical inheritance and a set of edges which model the "horizontal" transfer of genetic material. In a series of papers, Nakhleh and colleagues have recently formulated a maximum parsimony (MP) criterion for phylogenetic networks, provided an array of computationally efficient algorithms and heuristics for computing it, and demonstrated its plausibility on simulated data. In this article, we study the performance and robustness of this criterion on biological data. Our findings indicate that MP is very promising when its application is extended to the domain of phylogenetic network reconstruction and HGT detection. In all cases we investigated, the MP criterion detected the correct number of HGT events required to map the evolutionary history of a gene data set onto the species phylogeny. Furthermore, our results indicate that the criterion is robust with respect to both incomplete taxon sampling and the use of different site substitution matrices. Finally, our results show that the MP criterion is very promising in detecting HGT in chimeric genes, whose evolutionary histories are a mix of vertical and horizontal evolution. Besides the performance analysis of MP, our findings offer new insights into the evolution of 4 biological data sets and new possible explanations of HGT scenarios in their evolutionary history.     

Identification of horizontally transferred genes in the genus Colletotrichum reveals a steady tempo of bacterial to fungal gene transfer

Background

Horizontal gene transfer (HGT) is the stable transmission of genetic material between organisms by means other than vertical inheritance. HGT has an important role in the evolution of prokaryotes but is relatively rare in eukaryotes. HGT has been shown to contribute to virulence in eukaryotic pathogens. We studied the importance of HGT in plant pathogenic fungi by identifying horizontally transferred genes in the genomes of three members of the genus Colletotrichum.

Results

We identified eleven HGT events from bacteria into members of the genus Colletotrichum or their ancestors. The HGT events include genes involved in amino acid, lipid and sugar metabolism as well as lytic enzymes. Additionally, the putative minimal dates of transference were calculated using a time calibrated phylogenetic tree. This analysis reveals a constant flux of genes from bacteria to fungi throughout the evolution of subphylum Pezizomycotina.

Conclusions

Genes that are typically transferred by HGT are those that are constantly subject to gene duplication and gene loss. The functions of some of these genes suggest roles in niche adaptation and virulence. We found no evidence of a burst of HGT events coinciding with major geological events. In contrast, HGT appears to be a constant, albeit rare phenomenon in the Pezizomycotina, occurring at a steady rate during their evolution.

Electronic supplementary material

The online version of this article (doi:10.1186/1471-2164-16-2) contains supplementary material, which is available to authorized users.     

SpeciesRax: A Tool for Maximum Likelihood Species Tree Inference from Gene Family Trees under Duplication,Transfer, and Loss

Species tree inference from gene family trees is becoming increasingly popular because it can account for discordance between the species tree and the corresponding gene family trees. In particular, methods that can account for multiple-copy gene families exhibit potential to leverage paralogy as informative signal. At present, there does not exist any widely adopted inference method for this purpose. Here, we present SpeciesRax, the first maximum likelihood method that can infer a rooted species tree from a set of gene family trees and can account for gene duplication, loss, and transfer events. By explicitly modeling events by which gene trees can depart from the species tree, SpeciesRax leverages the phylogenetic rooting signal in gene trees. SpeciesRax infers species tree branch lengths in units of expected substitutions per site and branch support values via paralogy-aware quartets extracted from the gene family trees. Using both empirical and simulated data sets we show that SpeciesRax is at least as accurate as the best competing methods while being one order of magnitude faster on large data sets at the same time. We used SpeciesRax to infer a biologically plausible rooted phylogeny of the vertebrates comprising 188 species from 31,612 gene families in 1 h using 40 cores. SpeciesRax is available under GNU GPL at https://github.com/BenoitMorel/GeneRax and on BioConda.     

Algorithms for computing parsimonious evolutionary scenarios for genome evolution,the last universal common ancestor and dominance of horizontal gene transfer in the evolution of prokaryotes

Background

Comparative analysis of sequenced genomes reveals numerous instances of apparent horizontal gene transfer (HGT), at least in prokaryotes, and indicates that lineage-specific gene loss might have been even more common in evolution. This complicates the notion of a species tree, which needs to be re-interpreted as a prevailing evolutionary trend, rather than the full depiction of evolution, and makes reconstruction of ancestral genomes a non-trivial task.

Results

We addressed the problem of constructing parsimonious scenarios for individual sets of orthologous genes given a species tree. The orthologous sets were taken from the database of Clusters of Orthologous Groups of proteins (COGs). We show that the phyletic patterns (patterns of presence-absence in completely sequenced genomes) of almost 90% of the COGs are inconsistent with the hypothetical species tree. Algorithms were developed to reconcile the phyletic patterns with the species tree by postulating gene loss, COG emergence and HGT (the latter two classes of events were collectively treated as gene gains). We prove that each of these algorithms produces a parsimonious evolutionary scenario, which can be represented as mapping of loss and gain events on the species tree. The distribution of the evolutionary events among the tree nodes substantially depends on the underlying assumptions of the reconciliation algorithm, e.g. whether or not independent gene gains (gain after loss after gain) are permitted. Biological considerations suggest that, on average, gene loss might be a more likely event than gene gain. Therefore different gain penalties were used and the resulting series of reconstructed gene sets for the last universal common ancestor (LUCA) of the extant life forms were analysed. The number of genes in the reconstructed LUCA gene sets grows as the gain penalty increases. However, qualitative examination of the LUCA versions reconstructed with different gain penalties indicates that, even with a gain penalty of 1 (equal weights assigned to a gain and a loss), the set of 572 genes assigned to LUCA might be nearly sufficient to sustain a functioning organism. Under this gain penalty value, the numbers of horizontal gene transfer and gene loss events are nearly identical. This result holds true for two alternative topologies of the species tree and even under random shuffling of the tree. Therefore, the results seem to be compatible with approximately equal likelihoods of HGT and gene loss in the evolution of prokaryotes.

Conclusions

The notion that gene loss and HGT are major aspects of prokaryotic evolution was supported by quantitative analysis of the mapping of the phyletic patterns of COGs onto a hypothetical species tree. Algorithms were developed for constructing parsimonious evolutionary scenarios, which include gene loss and gain events, for orthologous gene sets, given a species tree. This analysis shows, contrary to expectations, that the number of predicted HGT events that occurred during the evolution of prokaryotes might be approximately the same as the number of gene losses. The approach to the reconstruction of evolutionary scenarios employed here is conservative with regard to the detection of HGT because only patterns of gene presence-absence in sequenced genomes are taken into account. In reality, horizontal transfer might have contributed to the evolution of many other genes also, which makes it a dominant force in prokaryotic evolution.

     

The cobweb of life revealed by genome-scale estimates of horizontal gene transfer

With the availability of increasing amounts of genomic sequences, it is becoming clear that genomes experience horizontal transfer and incorporation of genetic information. However, to what extent such horizontal gene transfer (HGT) affects the core genealogical history of organisms remains controversial. Based on initial analyses of complete genomic sequences, HGT has been suggested to be so widespread that it might be the “essence of phylogeny” and might leave the treelike form of genealogy in doubt. On the other hand, possible biased estimation of HGT extent and the findings of coherent phylogenetic patterns indicate that phylogeny of life is well represented by tree graphs. Here, we reexamine this question by assessing the extent of HGT among core orthologous genes using a novel statistical method based on statistical comparisons of tree topology. We apply the method to 40 microbial genomes in the Clusters of Orthologous Groups database over a curated set of 297 orthologous gene clusters, and we detect significant HGT events in 33 out of 297 clusters over a wide range of functional categories. Estimates of positions of HGT events suggest a low mean genome-specific rate of HGT (2.0%) among the orthologous genes, which is in general agreement with other quantitative of HGT. We propose that HGT events, even when relatively common, still leave the treelike history of phylogenies intact, much like cobwebs hanging from tree branches.     

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     

Confounding factors in HGT detection: statistical error, coalescent effects, and multiple solutions.

Prokaryotic organisms share genetic material across species boundaries by means of a process known as horizontal gene transfer (HGT). This process has great significance for understanding prokaryotic genome diversification and unraveling their complexities. Phylogeny-based detection of HGT is one of the most commonly used methods for this task, and is based on the fundamental fact that HGT may cause gene trees to disagree with one another, as well as with the species phylogeny. Using these methods, we can compare gene and species trees, and infer a set of HGT events to reconcile the differences among these trees. In this paper, we address three factors that confound the detection of the true HGT events, including the donors and recipients of horizontally transferred genes. First, we study experimentally the effects of error in the estimated gene trees (statistical error) on the accuracy of inferred HGT events. Our results indicate that statistical error leads to overestimation of the number of HGT events, and that HGT detection methods should be designed with unresolved gene trees in mind. Second, we demonstrate, both theoretically and empirically, that based on topological comparison alone, the number of HGT scenarios that reconcile a pair of species/gene trees may be exponential. This number may be reduced when branch lengths in both trees are estimated correctly. This set of results implies that in the absence of additional biological information, and/or a biological model of how HGT occurs, multiple HGT scenarios must be sought, and efficient strategies for how to enumerate such solutions must be developed. Third, we address the issue of lineage sorting, how it confounds HGT detection, and how to incorporate it with HGT into a single stochastic framework that distinguishes between the two events by extending population genetics theories. This result is very important, particularly when analyzing closely related organisms, where coalescent effects may not be ignored when reconciling gene trees. In addition to these three confounding factors, we consider the problem of enumerating all valid coalescent scenarios that constitute plausible species/gene tree reconciliations, and develop a polynomial-time dynamic programming algorithm for solving it. This result bears great significance on reducing the search space for heuristics that seek reconciliation scenarios. Finally, we show, empirically, that the locality of incongruence between a pair of trees has an impact on the numbers of HGT and coalescent reconciliation scenarios.     

A model of horizontal gene transfer and the bacterial phylogeny problem

How much horizontal gene transfer (HGT) between species influences bacterial phylogenomics is a controversial issue. This debate, however, lacks any quantitative assessment of the impact of HGT on phylogenies and of the ability of tree-building methods to cope with such events. I introduce a Markov model of genome evolution with HGT, accounting for the constraints on time -- an HGT event can only occur between concomitantly living species. This model is used to simulate multigene sequence data sets with or without HGT. The consequences of HGT on phylogenomic inference are analyzed and compared to other well-known phylogenetic artefacts. It is found that supertree methods are quite robust to HGT, keeping high levels of performance even when gene trees are largely incongruent with each other. Gene tree incongruence per se is not indicative of HGT. HGT, however, removes the (otherwise observed) positive relationship between sequence length and gene tree congruence to the estimated species tree. Surprisingly, when applied to a bacterial and a eukaryotic multigene data set, this criterion rejects the HGT hypothesis for the former, but not the latter data set.     

Comparing two Bayesian methods for gene tree/species tree reconstruction: simulations with incomplete lineage sorting and horizontal gene transfer

With the increasing interest in recognizing the discordance between gene genealogies, various gene tree/species tree reconciliation methods have been developed. We present here the first attempt to assess and compare two such Bayesian methods, Bayesian estimation of species trees (BEST) and BUCKy (Bayesian untangling of concordance knots), in the presence of several known processes of gene tree discordance. DNA alignments were simulated under the influence of incomplete lineage sorting (ILS) and of horizontal gene transfer (HGT). BEST and BUCKy both account for uncertainty in gene tree estimation but differ substantially in their assumptions of what caused gene tree discordance. BEST estimates a species tree using the coalescent model, assuming that all gene tree discordance is due to ILS. BUCKy does not assume any specific biological process of gene tree discordance through the use of a nonparametric clustering of concordant genes. BUCKy estimates the concordance factor (CF) of a clade, which is defined as the proportion of genes that truly have the clade in their trees. The estimated concordance tree is then built from clades with the highest estimated CFs. Because of their different assumptions, it was expected that BEST would perform better in the presence of ILS and that BUCKy would perform better in the presence of HGT. As expected, the species tree was more accurately reconstructed by BUCKy in the presence of HGT, when the HGT events were unevenly placed across the species tree. BUCKy and BEST performed similarly in most other cases, including in the presence of strong ILS and of HGT events that were evenly placed across the tree. However, BUCKy was shown to underestimate the uncertainty in CF estimation, with short credibility intervals. Despite this, the discordance pattern estimated by BUCKy could be compared with the signature of ILS. The resulting test for the adequacy of the coalescent model proved to have low Type I error. It was powerful when HGT was the major source of discordance and when HGT events were unevenly placed across the species tree.     

ENDOSYMBIOTIC AND HORIZONTAL GENE TRANSFER IN CHROMALVEOLATES1

Chromalveolates include photosynthetic and nonphotosynthetic (some plastid‐lacking) algae and protists that define a vast swath of eukaryotic diversity. These taxa are masters of gene acquisition through serial endosymbiosis (endosymbiotic gene transfer, EGT) and horizontal gene transfer (HGT). Understanding the contribution of these sources to nuclear genomes is key to elucidating chromalveolate evolution and to identifying suitable phylogenetic markers to place this lineage in the tree of life. Here we briefly review recent findings in our lab with regard to EGT and HGT in chromalveolates.     

Stochastic models for horizontal gene transfer: taking a random walk through tree space

Horizontal gene transfer (HGT) plays a critical role in evolution across all domains of life with important biological and medical implications. I propose a simple class of stochastic models to examine HGT using multiple orthologous gene alignments. The models function in a hierarchical phylogenetic framework. The top level of the hierarchy is based on a random walk process in "tree space" that allows for the development of a joint probabilistic distribution over multiple gene trees and an unknown, but estimable species tree. I consider two general forms of random walks. The first form is derived from the subtree prune and regraft (SPR) operator that mirrors the observed effects that HGT has on inferred trees. The second form is based on walks over complete graphs and offers numerically tractable solutions for an increasing number of taxa. The bottom level of the hierarchy utilizes standard phylogenetic models to reconstruct gene trees given multiple gene alignments conditional on the random walk process. I develop a well-mixing Markov chain Monte Carlo algorithm to fit the models in a Bayesian framework. I demonstrate the flexibility of these stochastic models to test competing ideas about HGT by examining the complexity hypothesis. Using 144 orthologous gene alignments from six prokaryotes previously collected and analyzed, Bayesian model selection finds support for (1) the SPR model over the alternative form, (2) the 16S rRNA reconstruction as the most likely species tree, and (3) increased HGT of operational genes compared to informational genes.     

THE INFLUENCE OF SAMPLING DESIGN ON SPECIES TREE INFERENCE: A NEW RELATIONSHIP FOR THE NEW WORLD CHICKADEES (AVES: POECILE)

In this study, we explore the long‐standing issue of how many loci are needed to infer accurate phylogenetic relationships, and whether loci with particular attributes (e.g., parsimony informativeness, variability, gene tree resolution) outperform others. To do so, we use an empirical data set consisting of the seven species of chickadees (Aves: Paridae), an analytically tractable, recently diverged group, and well‐studied ecologically but lacking a nuclear phylogeny. We estimate relationships using 40 nuclear loci and mitochondrial DNA using four coalescent‐based species tree inference methods (BEST, *BEAST, STEM, STELLS). Collectively, our analyses contrast with previous studies and support a sister relationship between the Black‐capped and Carolina Chickadee, two superficially similar species that hybridize along a long zone of contact. Gene flow is a potential source of conflict between nuclear and mitochondrial gene trees, yet we find a significant, albeit low, signal of gene flow. Our results suggest that relatively few loci with high information content may be sufficient for estimating an accurate species tree, but that substantially more loci are necessary for accurate parameter estimation. We provide an empirical reference point for researchers designing sampling protocols with the purpose of inferring phylogenies and population parameters of closely related taxa.     

INFERRING PHYLOGENIES FROM mtDNA VARIATION: MITOCHONDRIAL-GENE TREES VERSUS NUCLEAR-GENE TREES

An accurately resolved gene tree may not be congruent with the species tree because of lineage sorting of ancestral polymorphisms. DNA sequences from the mitochondrially encoded genes (mtDNA) are attractive sources of characters for estimating the phylogenies of recently evolved taxa because mtDNA evolves rapidly, but its utility is limited because the mitochondrial genes are inherited as a single linkage group (haplotype) and provide only one independent estimate of the species tree. In contrast, a set of nuclear genes can be selected from distinct chromosomes, such that each gene tree provides an independent estimate of the species tree. Another aspect of the gene-tree versus species-tree problem, however, favors the use of mtDNA for inferring species trees. For a three-species segment of a phylogeny, the branching order of a gene tree will correspond to that of the species tree if coalescence of the alleles or haplotypes occurred in the internode between the first and second bifurcation. From neutral theory, it is apparent that the probability of coalescence increases as effective population size decreases. Because the mitochondrial genome is maternally inherited and effectively haploid, its effective population size is one-fourth that of a nuclear-autosomal gene. Thus, the mitochondrial-haplotype tree has a substantially higher probability of accurately tracking a short internode than does a nuclear-autosomal-gene tree. When an internode is sufficiently long that the probability that the mitochondrial-haplotype tree will be congruent with the species tree is 0.95, the probability that a nuclear-autosomalgene tree will be congruent is only 0.62. If each of k independently sampled nuclear-gene trees has a probability of congruence with the species tree of 0.62, then a sample of 16 such trees would be required to be as confident of the inference based on the mitochondrial-haplotype tree. A survey of mtDNA-haplotype diversity in 34 species of birds indicates that coalescence is generally very recent, which suggests that coalescence times are typically much shorter than internodal branch lengths of the species tree, and that sorting of mtDNA lineages is not likely to confound the species tree. Hybridization resulting in transfer of mtDNA haplotypes among branches could also result in a haplotype tree that is incongruent with the species tree; if undetected, this could confound the species tree. However, hybridization is usually easy to detect and should be incorporated in the historical narrative of the group, because reticulation, as well as cladistic events, contributed to the evolution of the group.     

Horizontal gene transfer from extinct and extant lineages: biological innovation and the coral of life

Horizontal gene transfer (HGT) is often considered to be a source of error in phylogenetic reconstruction, causing individual gene trees within an organismal lineage to be incongruent, obfuscating the ‘true’ evolutionary history. However, when identified as such, HGTs between divergent organismal lineages are useful, phylogenetically informative characters that can provide insight into evolutionary history. Here, we discuss several distinct HGT events involving all three domains of life, illustrating the selective advantages that can be conveyed via HGT, and the utility of HGT in aiding phylogenetic reconstruction and in dating the relative sequence of speciation events. We also discuss the role of HGT from extinct lineages, and its impact on our understanding of the evolution of life on Earth. Organismal phylogeny needs to incorporate reticulations; a simple tree does not provide an accurate depiction of the processes that have shaped life''s history.     

Phylogeny vs genome reshuffling: horizontal gene transfer

The evolutionary events in organisms can be tracked to the transfer of genetic material. The inheritance of genetic material among closely related organisms is a slow evolutionary process. On the other hand, the movement of genes among distantly related species can account for rapid evolution. The later process has been quite evident in the appearance of antibiotic resistance genes among human and animal pathogens. Phylogenetic trees based on such genes and those involved in metabolic activities reflect the incongruencies in comparison to the 16S rDNA gene, generally used for taxonomic relationships. Such discrepancies in gene inheritance have been termed as horizontal gene transfer (HGT) events. In the post-genomic era, the explosion of known sequences through large-scale sequencing projects has unraveled the weakness of traditional 16S rDNA gene tree based evolutionary model. Various methods to scrutinize HGT events include atypical composition, abnormal sequence similarity, anomalous phylogenetic distribution, unusual phyletic patterns, etc. Since HGT generates greater genetic diversity, it is likely to increase resource use and ecosystem resilience.     

The Conflict Between Horizontal Gene Transfer and the Safeguard of Identity: Origin of Meiotic Sexuality

Contrary to a widespread opinion, horizontal gene transfer (HGT) between distantly related microorganisms (such as Bacteria and Archaea) has not been demonstrated to occur on a large scale. Except for transfer of mobile elements between closely related organisms, most alleged HGT events reflect phylogenetic discrepancies that can be explained by a variety of artefacts or by the differential loss of paralogous gene copies either originally present in the Last Universal Common Ancestor (LUCA) to the three Domains (a sophisticated, genetically redundant and promiscuous community of protoeukaryotes), or created by duplications having occurred at later times. Besides, (i) there is no experimental evidence for the facile acquisition of foreign DNA between distant taxa and (ii) important biological constraints operate on the phenotypic success of genetic exchange at several levels, including protein–protein interactions involved in metabolic channelling; stable integration and expression of foreign DNA is, therefore, expected to require strong selection. Explaining phylogenetic discrepancies by artefacts or loss of paralogs does not eliminate difficulties in retracing species genealogy but maintains the picture of a universal tree of life, HGT between distant organisms being reduced to a trickle. We illustrate our thesis by the phylogenetic analysis of carbamoyltransferases, a family of paralogous proteins. Among higher eukaryotes HGT appears of limited scope except in asexual organisms. We suggest that meiotic sexuality (a hallmark of eukaryotes) emerged in the genetically redundant and protoeukaryotic LUCA as a molecular identity check providing a defence mechanism against the deleterious effects of HGT.     

Systematic Detection of Large-Scale Multigene Horizontal Transfer in Prokaryotes

Horizontal gene transfer (HGT) is central to prokaryotic evolution. However, little is known about the “scale” of individual HGT events. In this work, we introduce the first computational framework to help answer the following fundamental question: How often does more than one gene get horizontally transferred in a single HGT event? Our method, called HoMer, uses phylogenetic reconciliation to infer single-gene HGT events across a given set of species/strains, employs several techniques to account for inference error and uncertainty, combines that information with gene order information from extant genomes, and uses statistical analysis to identify candidate horizontal multigene transfers (HMGTs) in both extant and ancestral species/strains. HoMer is highly scalable and can be easily used to infer HMGTs across hundreds of genomes. We apply HoMer to a genome-scale data set of over 22,000 gene families from 103 Aeromonas genomes and identify a large number of plausible HMGTs of various scales at both small and large phylogenetic distances. Analysis of these HMGTs reveals interesting relationships between gene function, phylogenetic distance, and frequency of multigene transfer. Among other insights, we find that 1) the observed relative frequency of HMGT increases as divergence between genomes increases, 2) HMGTs often have conserved gene functions, and 3) rare genes are frequently acquired through HMGT. We also analyze in detail HMGTs involving the zonula occludens toxin and type III secretion systems. By enabling the systematic inference of HMGTs on a large scale, HoMer will facilitate a more accurate and more complete understanding of HGT and microbial evolution.     

iGLASS: an improvement to the GLASS method for estimating species trees from gene trees

Several methods have been designed to infer species trees from gene trees while taking into account gene tree/species tree discordance. Although some of these methods provide consistent species tree topology estimates under a standard model, most either do not estimate branch lengths or are computationally slow. An exception, the GLASS method of Mossel and Roch, is consistent for the species tree topology, estimates branch lengths, and is computationally fast. However, GLASS systematically overestimates divergence times, leading to biased estimates of species tree branch lengths. By assuming a multispecies coalescent model in which multiple lineages are sampled from each of two taxa at L independent loci, we derive the distribution of the waiting time until the first interspecific coalescence occurs between the two taxa, considering all loci and measuring from the divergence time. We then use the mean of this distribution to derive a correction to the GLASS estimator of pairwise divergence times. We show that our improved estimator, which we call iGLASS, consistently estimates the divergence time between a pair of taxa as the number of loci approaches infinity, and that it is an unbiased estimator of divergence times when one lineage is sampled per taxon. We also show that many commonly used clustering methods can be combined with the iGLASS estimator of pairwise divergence times to produce a consistent estimator of the species tree topology. Through simulations, we show that iGLASS can greatly reduce the bias and mean squared error in obtaining estimates of divergence times in a species tree.     

Locus-aware decomposition of gene trees with respect to polytomous species trees

Background

Horizontal gene transfer (HGT), a process of acquisition and fixation of foreign genetic material, is an important biological phenomenon. Several approaches to HGT inference have been proposed. However, most of them either rely on approximate, non-phylogenetic methods or on the tree reconciliation, which is computationally intensive and sensitive to parameter values.

Results

We investigate the locus tree inference problem as a possible alternative that combines the advantages of both approaches. We present several algorithms to solve the problem in the parsimony framework. We introduce a novel tree mapping, which allows us to obtain a heuristic solution to the problems of locus tree inference and duplication classification.

Conclusions

Our approach allows for faster comparisons of gene and species trees and improves known algorithms for duplication inference in the presence of polytomies in the species trees. We have implemented our algorithms in a software tool available at https://github.com/mciach/LocusTreeInference.

     

SPRIT: Identifying horizontal gene transfer in rooted phylogenetic trees

Background  

Phylogenetic trees based on sequences from a set of taxa can be incongruent due to horizontal gene transfer (HGT). By identifying the HGT events, we can reconcile the gene trees and derive a taxon tree that adequately represents the species' evolutionary history. One HGT can be represented by a rooted Subtree Prune and Regraft (RSPR) operation and the number of RSPRs separating two trees corresponds to the minimum number of HGT events. Identifying the minimum number of RSPRs separating two trees is NP-hard, but the problem can be reduced to fixed parameter tractable. A number of heuristic and two exact approaches to identifying the minimum number of RSPRs have been proposed. This is the first implementation delivering an exact solution as well as the intermediate trees connecting the input trees.