Phylo SI: a new genome-wide approach for prokaryotic phylogeny

The evolutionary history of all life forms is usually represented as a vertical tree-like process. In prokaryotes, however, the vertical signal is partly obscured by the massive influence of horizontal gene transfer (HGT). The HGT creates widespread discordance between evolutionary histories of different genes as genomes become mosaics of gene histories. Thus, the Tree of Life (TOL) has been questioned as an appropriate representation of the evolution of prokaryotes. Nevertheless a common hypothesis is that prokaryotic evolution is primarily tree-like, and a routine effort is made to place new isolates in their appropriate location in the TOL. Moreover, it appears desirable to exploit non–tree-like evolutionary processes for the task of microbial classification. In this work, we present a novel technique that builds on the straightforward observation that gene order conservation (‘synteny’) decreases in time as a result of gene mobility. This is particularly true in prokaryotes, mainly due to HGT. Using a ‘synteny index’ (SI) that measures the average synteny between a pair of genomes, we developed the phylogenetic reconstruction tool ‘Phylo SI’. Phylo SI offers several attractive properties such as easy bootstrapping, high sensitivity in cases where phylogenetic signal is weak and computational efficiency. Phylo SI was tested both on simulated data and on two bacterial data sets and compared with two well-established phylogenetic methods. Phylo SI is particularly efficient on short evolutionary distances where synteny footprints remain detectable, whereas the nucleotide substitution signal is too weak for reliable sequence-based phylogenetic reconstruction. The method is publicly available at http://research.haifa.ac.il/ssagi/software/PhyloSI.zip.     

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.     

VSDK: Virtual screening of small molecules using AutoDock Vina on Windows platform

Screening of ligand molecules to target proteins using computer-aided docking is a critical step in rational drug discovery. Based on this circumstance, we attempted to develop a virtual screening application system, named VSDK Virtual Screening by Docking, which can function under the Windows platform. This is a user-friendly, flexible, and versatile tool which can be used by users who are familiar with Windows OS. The virtual screening performance was tested for an arbitrarily-selected receptor, FGFR tyrosine kinase (pdb code: 1agw), by using ligands downloaded from ZINC database with its grid size of x,y,z = 30,30,30 and run number of 10. It took 90 minutes for 100 molecules for this virtual screening. VSDK is freely available at the designated URL, and a simplified manual can be downloaded from VSDK home page. This tool will have a more challenging scope and achievement as the computer speed and accuracy are increased and secured in the future.

Availability

The database is available for free at http://www.pharm.kobegakuin.ac.jp/˜akaho/english_top.html     

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.     

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.

     

MetaMetaDB: A Database and Analytic System for Investigating Microbial Habitability

MetaMetaDB (http://mmdb.aori.u-tokyo.ac.jp/) is a database and analytic system for investigating microbial habitability, i.e., how a prokaryotic group can inhabit different environments. The interaction between prokaryotes and the environment is a key issue in microbiology because distinct prokaryotic communities maintain distinct ecosystems. Because 16S ribosomal RNA (rRNA) sequences play pivotal roles in identifying prokaryotic species, a system that comprehensively links diverse environments to 16S rRNA sequences of the inhabitant prokaryotes is necessary for the systematic understanding of the microbial habitability. However, existing databases are biased to culturable prokaryotes and exhibit limitations in the comprehensiveness of the data because most prokaryotes are unculturable. Recently, metagenomic and 16S rRNA amplicon sequencing approaches have generated abundant 16S rRNA sequence data that encompass unculturable prokaryotes across diverse environments; however, these data are usually buried in large databases and are difficult to access. In this study, we developed MetaMetaDB (Meta-Metagenomic DataBase), which comprehensively and compactly covers 16S rRNA sequences retrieved from public datasets. Using MetaMetaDB, users can quickly generate hypotheses regarding the types of environments a prokaryotic group may be adapted to. We anticipate that MetaMetaDB will improve our understanding of the diversity and evolution of prokaryotes.     

Phylogeny, host-parasite relationship and zoogeography

Phylogeny is the evolutionary history of a group or the lineage of organisms and is reconstructed based on morphological, molecular and other characteristics. The genealogical relationship of a group of taxa is often expressed as a phylogenetic tree. The difficulty in categorizing the phylogeny is mainly due to the existence of frequent homoplasies that deceive observers. At the present time, cladistic analysis is believed to be one of the most effective methods of reconstructing a phylogenetic tree. Excellent computer program software for phylogenetic analysis is available. As an example, cladistic analysis was applied for nematode genera of the family Acuariidae, and the phylogenetic tree formed was compared with the system used currently. Nematodes in the genera Nippostrongylus and Heligmonoides were also analyzed, and the validity of the reconstructed phylogenetic trees was observed from a zoogeographical point of view. Some of the theories of parasite evolution were briefly reviewed as well. Coevolution of parasites and humans was discussed with special reference to the evolutionary relationship between Enterobius and primates.     

ggtreeExtra: Compact Visualization of Richly Annotated Phylogenetic Data

We present the ggtreeExtra package for visualizing heterogeneous data with a phylogenetic tree in a circular or rectangular layout (https://www.bioconductor.org/packages/ggtreeExtra). The package supports more data types and visualization methods than other tools. It supports using the grammar of graphics syntax to present data on a tree with richly annotated layers and allows evolutionary statistics inferred by commonly used software to be integrated and visualized with external data. GgtreeExtra is a universal tool for tree data visualization. It extends the applications of the phylogenetic tree in different disciplines by making more domain-specific data to be available to visualize and interpret in the evolutionary context.     

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.     

Advances in the use of DNA barcodes to build a community phylogeny for tropical trees in a Puerto Rican forest dynamics plot

Background

Species number, functional traits, and phylogenetic history all contribute to characterizing the biological diversity in plant communities. The phylogenetic component of diversity has been particularly difficult to quantify in species-rich tropical tree assemblages. The compilation of previously published (and often incomplete) data on evolutionary relationships of species into a composite phylogeny of the taxa in a forest, through such programs as Phylomatic, has proven useful in building community phylogenies although often of limited resolution. Recently, DNA barcodes have been used to construct a robust community phylogeny for nearly 300 tree species in a forest dynamics plot in Panama using a supermatrix method. In that study sequence data from three barcode loci were used to generate a well-resolved species-level phylogeny.

Methodology/Principal Findings

Here we expand upon this earlier investigation and present results on the use of a phylogenetic constraint tree to generate a community phylogeny for a diverse, tropical forest dynamics plot in Puerto Rico. This enhanced method of phylogenetic reconstruction insures the congruence of the barcode phylogeny with broadly accepted hypotheses on the phylogeny of flowering plants (i.e., APG III) regardless of the number and taxonomic breadth of the taxa sampled. We also compare maximum parsimony versus maximum likelihood estimates of community phylogenetic relationships as well as evaluate the effectiveness of one- versus two- versus three-gene barcodes in resolving community evolutionary history.

Conclusions/Significance

As first demonstrated in the Panamanian forest dynamics plot, the results for the Puerto Rican plot illustrate that highly resolved phylogenies derived from DNA barcode sequence data combined with a constraint tree based on APG III are particularly useful in comparative analysis of phylogenetic diversity and will enhance research on the interface between community ecology and evolution.     

From a phylogenetic tree to a reticulated network.

In many phylogenetic problems, assuming that species have evolved from a common ancestor by a simple branching process is unrealistic. Reticulate phylogenetic models, however, have been largely neglected because the concept of reticulate evolution have not been supported by using appropriate analytical tools and software. The reticulate model can adequately describe such complicated mechanisms as hybridization between species or lateral gene transfer in bacteria. In this paper, we describe a new algorithm for inferring reticulate phylogenies from evolutionary distances among species. The algorithm is capable of detecting contradictory signals encompassed in a phylogenetic tree and identifying possible reticulate events that may have occurred during evolution. The algorithm produces a reticulate phylogeny by gradually improving upon the initial solution provided by a phylogenetic tree model. The new algorithm is compared to the popular SplitsGraph method in a reanalysis of the evolution of photosynthetic organisms. A computer program to construct and visualize reticulate phylogenies, called T-Rex (Tree and Reticulogram Reconstruction), is available to researchers at the following URL: www.fas.umontreal.ca/biol/casgrain/en/labo/t-rex.     

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.     

Phylogeny of γ‐proteobacteria: resolution of one branch of the universal tree?

The reconstruction of bacterial evolutionary relationships has proven to be a daunting task because variable mutation rates and horizontal gene transfer (HGT) among species can cause grave incongruities between phylogenetic trees based on single genes. Recently, a highly robust phylogenetic tree was constructed for 13 gamma-proteobacteria using the combined alignments of 205 conserved orthologous proteins.1 Only two proteins had incongruent tree topologies, which were attributed to HGT between Pseudomonas species and Vibrio cholerae or enterics. While the evolutionary relationships among these species appears to be resolved, further analysis suggests that HGT events with other bacterial partners likely occurred; this alters the implicit assumption of gamma-proteobacteria monophyly. Thus, any thorough reconstruction of bacterial evolution must not only choose a suitable set of molecular markers but also strive to reduce potential bias in the selection of species.     

Phylogenetic analysis of nitrite, nitric oxide, and nitrous oxide respiratory enzymes reveal a complex evolutionary history for denitrification

Denitrification is a facultative respiratory pathway in which nitrite (NO2(-)), nitric oxide (NO), and nitrous oxide (N2O) are successively reduced to nitrogen gas (N(2)), effectively closing the nitrogen cycle. The ability to denitrify is widely dispersed among prokaryotes, and this polyphyletic distribution has raised the possibility of horizontal gene transfer (HGT) having a substantial role in the evolution of denitrification. Comparisons of 16S rRNA and denitrification gene phylogenies in recent studies support this possibility; however, these results remain speculative as they are based on visual comparisons of phylogenies from partial sequences. We reanalyzed publicly available nirS, nirK, norB, and nosZ partial sequences using Bayesian and maximum likelihood phylogenetic inference. Concomitant analysis of denitrification genes with 16S rRNA sequences from the same organisms showed substantial differences between the trees, which were supported by examining the posterior probability of monophyletic constraints at different taxonomic levels. Although these differences suggest HGT of denitrification genes, the presence of structural variants for nirK, norB, and nosZ makes it difficult to determine HGT from other evolutionary events. Additional analysis using phylogenetic networks and likelihood ratio tests of phylogenies based on full-length sequences retrieved from genomes also revealed significant differences in tree topologies among denitrification and 16S rRNA gene phylogenies, with the exception of the nosZ gene phylogeny within the data set of the nirK-harboring genomes. However, inspection of codon usage and G + C content plots from complete genomes gave no evidence for recent HGT. Instead, the close proximity of denitrification gene copies in the genomes of several denitrifying bacteria suggests duplication. Although HGT cannot be ruled out as a factor in the evolution of denitrification genes, our analysis suggests that other phenomena, such gene duplication/divergence and lineage sorting, may have differently influenced the evolution of each denitrification gene.     

Determination of whole prokaryotic phylogeny by the development of a random extraction method

The construction of accurate prokaryotic phylogeny is important not only in the field of evolutionary biology, but also in microbiology and pathology. However, in constructing a phylogenetic tree to trace prokaryotic evolution, the phylogenetic relationship is often changed by the choice of species. For the estimation of the accurate lineage of prokaryotes, a new method, named the "random extraction method", was developed. In this method, 16S rRNA sequence data were randomly extracted 1000 times from each closely-related taxa such as seven phyla of Eubacteria and one domain of Archaea and phylogenetic trees were constructed by the data to clarify the relationship of those groups. Next, the tree topology was counted and the most supported tree topology was found as the most plausible phylogenetic tree. To evaluate the reliability of each node, we developed the "Branching rate" (BR) and calculated for every tree. And also, computational simulation analysis was carried out to confirm these methods. On the assumption that the root of life is between Archaea and Eubacteria, the obtained phylogenetic relationships of phyla are the following. At first, Archaea (Euryarchaeota, Crenarchaeota and Korarchaeota) diverged, and Thermotogales, Cyanobacteria and Chlamydiales diverged in this order, then Firmicutes (Actinobacteria and Bacillus/Clostridium group cluster) and Proteobacteria (alpha and beta/gamma cluster) diverged. In addition, it was shown by the BR that the position of the node of Firmicutes Actinobacteria and Firmicutes Bacillus/Clostridium was changeable for each extraction. Therefore, it was suggested that the differences among the phylogenetic trees of prokaryotes were caused by the influence of these phyla.     

GHOSTX: An Improved Sequence Homology Search Algorithm Using a Query Suffix Array and a Database Suffix Array

DNA sequences are translated into protein coding sequences and then further assigned to protein families in metagenomic analyses, because of the need for sensitivity. However, huge amounts of sequence data create the problem that even general homology search analyses using BLASTX become difficult in terms of computational cost. We designed a new homology search algorithm that finds seed sequences based on the suffix arrays of a query and a database, and have implemented it as GHOSTX. GHOSTX achieved approximately 131–165 times acceleration over a BLASTX search at similar levels of sensitivity. GHOSTX is distributed under the BSD 2-clause license and is available for download at http://www.bi.cs.titech.ac.jp/ghostx/. Currently, sequencing technology continues to improve, and sequencers are increasingly producing larger and larger quantities of data. This explosion of sequence data makes computational analysis with contemporary tools more difficult. We offer this tool as a potential solution to this problem.     

DendroBLAST: Approximate Phylogenetic Trees in the Absence of Multiple Sequence Alignments

The rapidly growing availability of genome information has created considerable demand for both fast and accurate phylogenetic inference algorithms. We present a novel method called DendroBLAST for reconstructing phylogenetic dendrograms/trees from protein sequences using BLAST. This method differs from other methods by incorporating a simple model of sequence evolution to test the effect of introducing sequence changes on the reliability of the bipartitions in the inferred tree. Using realistic simulated sequence data we demonstrate that this method produces phylogenetic trees that are more accurate than other commonly-used distance based methods though not as accurate as maximum likelihood methods from good quality multiple sequence alignments. In addition to tests on simulated data, we use DendroBLAST to generate input trees for a supertree reconstruction of the phylogeny of the Archaea. This independent analysis produces an approximate phylogeny of the Archaea that has both high precision and recall when compared to previously published analysis of the same dataset using conventional methods. Taken together these results demonstrate that approximate phylogenetic trees can be produced in the absence of multiple sequence alignments, and we propose that these trees will provide a platform for improving and informing downstream bioinformatic analysis. A web implementation of the DendroBLAST method is freely available for use at http://www.dendroblast.com/.     

Does a tree-like phylogeny only exist at the tips in the prokaryotes?

The extent to which prokaryotic evolution has been influenced by horizontal gene transfer (HGT) and therefore might be more of a network than a tree is unclear. Here we use supertree methods to ask whether a definitive prokaryotic phylogenetic tree exists and whether it can be confidently inferred using orthologous genes. We analysed an 11-taxon dataset spanning the deepest divisions of prokaryotic relationships, a 10-taxon dataset spanning the relatively recent gamma-proteobacteria and a 61-taxon dataset spanning both, using species for which complete genomes are available. Congruence among gene trees spanning deep relationships is not better than random. By contrast, a strong, almost perfect phylogenetic signal exists in gamma-proteobacterial genes. Deep-level prokaryotic relationships are difficult to infer because of signal erosion, systematic bias, hidden paralogy and/or HGT. Our results do not preclude levels of HGT that would be inconsistent with the notion of a prokaryotic phylogeny. This approach will help decide the extent to which we can say that there is a prokaryotic phylogeny and where in the phylogeny a cohesive genomic signal exists.     

Reconstructing evolutionary relationships from functional data: a consistent classification of organisms based on translation inhibition response

The last two decades have witnessed an unsurpassed effort aimed at reconstructing the history of life from the genetic information contained in extant organisms. The availability of many sequenced genomes has allowed the reconstruction of phylogenies from gene families and its comparison with traditional single-gene trees. However, the appearance of major discrepancies between both approaches questions whether horizontal gene transfer (HGT) has played a prominent role in shaping the topology of the Tree of Life. Recent attempts at solving this controversy and reaching a consensus tree combine molecular data with additional phylogenetic markers. Translation is a universal cellular function that involves a meaningful, highly conserved set of genes: both rRNA and r-protein operons have an undisputed phylogenetic value and rarely undergo HGT. Ribosomal function reflects the concerted expression of that genetic network and consequently yields information about the evolutionary paths followed by the organisms. Here we report on tree reconstruction using a measure of the performance of the ribosome: antibiotic sensitivity of protein synthesis. A large database has been used where 33 ribosomal systems belonging to the three major cellular lineages were probed against 38 protein synthesis inhibitors. Different definitions of distance between pairs of organisms have been explored, and the classical algorithm of bootstrap evaluation has been adapted to quantify the reliability of the reconstructions obtained. Our analysis returns a consistent phylogeny, where archaea are systematically affiliated to eukarya, in agreement with recent reconstructions which used information-processing systems. The integration of the information derived from relevant functional markers into current phylogenetic reconstructions might facilitate achieving a consensus Tree of Life.