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.     

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.     

Testing for treeness: lateral gene transfer,phylogenetic inference,and model selection

A phylogeny that allows for lateral gene transfer (LGT) can be thought of as a strictly branching tree (all of whose branches are vertical) to which lateral branches have been added. Given that the goal of phylogenetics is to depict evolutionary history, we should look for the best supported phylogenetic network and not restrict ourselves to considering trees. However, the obvious extensions of popular tree-based methods such as maximum parsimony and maximum likelihood face a serious problem—if we judge networks by fit to data alone, networks that have lateral branches will always fit the data at least as well as any network that restricts itself to vertical branches. This is analogous to the well-studied problem of overfitting data in the curve-fitting problem. Analogous problems often have analogous solutions and we propose to treat network inference as a case of model selection and use the Akaike Information Criterion (AIC). Strictly tree-like networks are more parsimonious than those that postulate lateral as well as vertical branches. This leads to the conclusion that we should not always infer LGT events whenever it would improve our fit-to-data, but should do so only when the improved fit is larger than the penalty for adding extra lateral branches.     

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.     

Detecting lateral gene transfers by statistical reconciliation of phylogenetic forests

Background  

To understand the evolutionary role of Lateral Gene Transfer (LGT), accurate methods are needed to identify transferred genes and infer their timing of acquisition. Phylogenetic methods are particularly promising for this purpose, but the reconciliation of a gene tree with a reference (species) tree is computationally hard. In addition, the application of these methods to real data raises the problem of sorting out real and artifactual phylogenetic conflict.     

Phylogenetic identification of lateral genetic transfer events

Background  

Lateral genetic transfer can lead to disagreements among phylogenetic trees comprising sequences from the same set of taxa. Where topological discordance is thought to have arisen through genetic transfer events, tree comparisons can be used to identify the lineages that may have shared genetic information. An 'edit path' of one or more transfer events can be represented with a series of subtree prune and regraft (SPR) operations, but finding the optimal such set of operations is NP-hard for comparisons between rooted trees, and may be so for unrooted trees as well.     

CTree: comparison of clusters between phylogenetic trees made easy

SUMMARY: CTree has been designed for the quantification of clusters within viral phylogenetic tree topologies. Clusters are stored as individual data structures from which statistical data, such as the Subtype Diversity Ratio (SDR), Subtype Diversity Variance (SDV) and pairwise distances can be extracted. This simplifies the quantification of tree topologies in relation to inter- and intra-cluster diversity. Here the novel features incorporated within CTree, including the implementation of a heuristic algorithm for identifying clusters, are outlined along with the more usual features found within general tree viewing software. AVAILABILITY: CTree is available as an executable jar file from: http://www.manchester.ac.uk/bioinformatics/ctree     

Comparison of phylogenetic trees through alignment of embedded evolutionary distances

Background  

The understanding of evolutionary relationships is a fundamental aspect of modern biology, with the phylogenetic tree being a primary tool for describing these associations. However, comparison of trees for the purpose of assessing similarity and the quantification of various biological processes remains a significant challenge.     

A singular bacteriophytochrome acquired by lateral gene transfer

Bacteriophytochromes are phytochrome-like proteins that mediate photosensory responses in various bacteria according to their light environment. The genome of the photosynthetic and plant-symbiotic Bradyrhizobium sp. strain ORS278 revealed the presence of a genomic island acquired by lateral transfer harboring a bacteriophytochrome gene, BrBphP3.ORS278, and genes involved in the synthesis of phycocyanobilin and gas vesicles. The corresponding protein BrBphP3.ORS278 is phylogenetically distant from the other (bacterio)phytochromes described thus far and displays a series of unusual properties. It binds phycocyanobilin as a chromophore, a unique feature for a bacteriophytochrome. Moreover, its C-terminal region is short and displays no homology with any known functional domain. Its dark-adapted state absorbs maximally around 610 nm, an unusually short wavelength for (bacterio)phytochromes. This form is designated as Po for orange-absorbing form. Upon illumination, a photo-reversible switch occurs between the Po form and a red (670 nm)-absorbing form (Pr), which rapidly backreacts in the dark. Because of this instability, illumination results in a mixture of the Po and Pr states in proportions that depend on the intensity. These uncommon features suggest that BrBphP3.ORS278 could be fitted to measure light intensity rather than color.     

Phylogenetic reconstruction and lateral gene transfer

Lateral gene transfer (LGT) is often seen as a form of noise, obscuring the phylogenetic signal with which we might hope to reconstruct the evolution of a group of organisms, or indeed the history of all life (the Tree of Life). Such reconstruction might still be possible if the subset of genes conserved among all genomes in a group (or common to all genomes) comprise a core that is relatively refractory to LGT. Several papers designed to test this notion have recently appeared, and here we re-analyze one, which claims that the core of single-copy orthologs shared by all sequenced genomes of the gammaproteobacteria is essentially free of LGT. This conclusion is unfortunately premature, and it is very hard to determine what fraction of this core has been affected by LGT. We discuss other difficulties with the core concept and suggest that, although the core idea must remain part of our understanding of phylogenetic relationships, it should not be the sole basis for defining such relationships, because these are not exclusively tree-like. We suggest instead a more complex but more natural framework for classification, which we call the Synthesis of Life.     

Networks of gene sharing among 329 proteobacterial genomes reveal differences in lateral gene transfer frequency at different phylogenetic depths

Lateral gene transfer (LGT) is an important mechanism of natural variation among prokaryotes. Over the full course of evolution, most or all of the genes resident in a given prokaryotic genome have been affected by LGT, yet the frequency of LGT can vary greatly across genes and across prokaryotic groups. The proteobacteria are among the most diverse of prokaryotic taxa. The prevalence of LGT in their genome evolution calls for the application of network-based methods instead of tree-based methods to investigate the relationships among these species. Here, we report networks that capture both vertical and horizontal components of evolutionary history among 1,207,272 proteins distributed across 329 sequenced proteobacterial genomes. The network of shared proteins reveals modularity structure that does not correspond to current classification schemes. On the basis of shared protein-coding genes, the five classes of proteobacteria fall into two main modules, one including the alpha-, delta-, and epsilonproteobacteria and the other including beta- and gammaproteobacteria. The first module is stable over different protein identity thresholds. The second shows more plasticity with regard to the sequence conservation of proteins sampled, with the gammaproteobacteria showing the most chameleon-like evolutionary characteristics within the present sample. Using a minimal lateral network approach, we compared LGT rates at different phylogenetic depths. In general, gene evolution by LGT within proteobacteria is very common. At least one LGT event was inferred to have occurred in at least 75% of the protein families. The average LGT rate at the species and class depth is about one LGT event per protein family, the rate doubling at the phylum level to an average of two LGT events per protein family. Hence, our results indicate that the rate of gene acquisition per protein family is similar at the level of species (by recombination) and at the level of classes (by LGT). The frequency of LGT per genome strongly depends on the species lifestyle, with endosymbionts showing far lower LGT frequencies than free-living species. Moreover, the nature of the transferred genes suggests that gene transfer in proteobacteria is frequently mediated by conjugation.     

TreeKO: a duplication-aware algorithm for the comparison of phylogenetic trees

Comparisons of tree topologies provide relevant information in evolutionary studies. Most existing methods share the drawback of requiring a complete and exact mapping of terminal nodes between the compared trees. This severely limits the scope of genome-wide analyses, since trees containing duplications are pruned arbitrarily or discarded. To overcome this, we have developed treeKO, an algorithm that enables the comparison of tree topologies, even in the presence of duplication and loss events. To do so treeKO recursively splits gene trees into pruned trees containing only orthologs to subsequently compute a distance based on the combined analyses of all pruned tree comparisons. In addition treeKO, implements the possibility of computing phylome support values, and reconciliation-based measures such as the number of inferred duplication and loss events.     

Old genes in new places: A taxon-rich analysis of interdomain lateral gene transfer events

Vertical inheritance is foundational to Darwinian evolution, but fails to explain major innovations such as the rapid spread of antibiotic resistance among bacteria and the origin of photosynthesis in eukaryotes. While lateral gene transfer (LGT) is recognized as an evolutionary force in prokaryotes, the role of LGT in eukaryotic evolution is less clear. With the exception of the transfer of genes from organelles to the nucleus, a process termed endosymbiotic gene transfer (EGT), the extent of interdomain transfer from prokaryotes to eukaryotes is highly debated. A common critique of studies of interdomain LGT is the reliance on the topology of single-gene trees that attempt to estimate more than one billion years of evolution. We take a more conservative approach by identifying cases in which a single clade of eukaryotes is found in an otherwise prokaryotic gene tree (i.e. exclusive presence). Starting with a taxon-rich dataset of over 13,600 gene families and passing data through several rounds of curation, we identify and categorize the function of 306 interdomain LGT events into diverse eukaryotes, including 189 putative EGTs, 52 LGTs into Opisthokonta (i.e. animals, fungi and their microbial relatives), and 42 LGTs nearly exclusive to anaerobic eukaryotes. To assess differential gene loss as an explanation for exclusive presence, we compare branch lengths within each LGT tree to a set of vertically-inherited genes subsampled to mimic gene loss (i.e. with the same taxonomic sampling) and consistently find shorter relative distance between eukaryotes and prokaryotes in LGT trees, a pattern inconsistent with gene loss. Our methods provide a framework for future studies of interdomain LGT and move the field closer to an understanding of how best to model the evolutionary history of eukaryotes.     

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.     

From gene trees to species trees II: species tree inference by minimizing deep coalescence events

When gene copies are sampled from various species, the resulting gene tree might disagree with the containing species tree. The primary causes of gene tree and species tree discord include incomplete lineage sorting, horizontal gene transfer, and gene duplication and loss. Each of these events yields a different parsimony criterion for inferring the (containing) species tree from gene trees. With incomplete lineage sorting, species tree inference is to find the tree minimizing extra gene lineages that had to coexist along species lineages; with gene duplication, it becomes to find the tree minimizing gene duplications and/or losses. In this paper, we present the following results: 1) The deep coalescence cost is equal to the number of gene losses minus two times the gene duplication cost in the reconciliation of a uniquely leaf labeled gene tree and a species tree. The deep coalescence cost can be computed in linear time for any arbitrary gene tree and species tree. 2) The deep coalescence cost is always not less than the gene duplication cost in the reconciliation of an arbitrary gene tree and a species tree. 3) Species tree inference by minimizing deep coalescence events is NP-hard.     

Recent events dominate interdomain lateral gene transfers between prokaryotes and eukaryotes and,with the exception of endosymbiotic gene transfers,few ancient transfer events persist

While there is compelling evidence for the impact of endosymbiotic gene transfer (EGT; transfer from either mitochondrion or chloroplast to the nucleus) on genome evolution in eukaryotes, the role of interdomain transfer from bacteria and/or archaea (i.e. prokaryotes) is less clear. Lateral gene transfers (LGTs) have been argued to be potential sources of phylogenetic information, particularly for reconstructing deep nodes that are difficult to recover with traditional phylogenetic methods. We sought to identify interdomain LGTs by using a phylogenomic pipeline that generated 13 465 single gene trees and included up to 487 eukaryotes, 303 bacteria and 118 archaea. Our goals include searching for LGTs that unite major eukaryotic clades, and describing the relative contributions of LGT and EGT across the eukaryotic tree of life. Given the difficulties in interpreting single gene trees that aim to capture the approximately 1.8 billion years of eukaryotic evolution, we focus on presence–absence data to identify interdomain transfer events. Specifically, we identify 1138 genes found only in prokaryotes and representatives of three or fewer major clades of eukaryotes (e.g. Amoebozoa, Archaeplastida, Excavata, Opisthokonta, SAR and orphan lineages). The majority of these genes have phylogenetic patterns that are consistent with recent interdomain LGTs and, with the notable exception of EGTs involving photosynthetic eukaryotes, we detect few ancient interdomain LGTs. These analyses suggest that LGTs have probably occurred throughout the history of eukaryotes, but that ancient events are not maintained unless they are associated with endosymbiotic gene transfer among photosynthetic lineages.     

Lateral gene transfer and phylogenetic assignment of environmental fosmid clones

Metagenomic data, especially sequence data from large insert clones, are most useful when reasonable inferences about phylogenetic origins of inserts can be made. Often, clones that bear phylotypic markers (usually ribosomal RNA genes) are sought, but sometimes phylogenetic assignments have been based on the preponderance of blast hits obtained with predicted protein coding sequences (CDSs). Here we use a cloning method which greatly enriches for ribosomal RNA-bearing fosmid clones to ask two questions: (i) how reliably can we judge the phylogenetic origin of a clone (that is, its RNA phylotype) from the sequences of its CDSs? and (ii) how much lateral gene transfer (LGT) do we see, as assessed by CDSs of different phylogenetic origins on the same fosmid? We sequenced 12 rRNA containing fosmid clones, obtained from libraries constructed using DNA isolated from Baltimore harbour sediments. Three of the clones are from bacterial candidate divisions for which no cultured representatives are available, and thus represent the first protein coding sequences from these major bacterial lineages. The amount of LGT was assessed by making phylogenetic trees of all the CDSs in the fosmid clones and comparing the phylogenetic position of the CDS to the rRNA phylotype. We find that the majority of CDSs in each fosmid, 57-96%, agree with their respective rRNA genes. However, we also find that a significant fraction of the CDSs in each fosmid, 7-44%, has been acquired by LGT. In several cases, we can infer co-transfer of functionally related genes, and generate hypotheses about mechanism and ecological significance of transfer.     

Phage as agents of lateral gene transfer

When establishing lysogeny, temperate phages integrate their genome as a prophage into the bacterial chromosome. Prophages thus constitute in many bacteria a substantial part of laterally acquired DNA. Some prophages contribute lysogenic conversion genes that are of selective advantage to the bacterial host. Occasionally, phages are also involved in the lateral transfer of other mobile DNA elements or bacterial DNA. Recent advances in the field of genomics have revealed a major impact by phages on bacterial chromosome evolution.