Short branches lead to systematic artifacts when BLAST searches are used as surrogate for phylogenetic reconstruction.

Long Branch Attraction (LBA) is a well-known artifact in phylogenetic reconstruction when dealing with branch length heterogeneity. Here we show another phenomenon, Short Branch Attraction (SBA), which occurs when BLAST searches, a phenetic analysis, are used as a surrogate method for phylogenetic analysis. This error also results from branch length heterogeneity, but this time it is the short branches that are attracting. The SBA artifact is reciprocal and can be returned 100% of the time when multiple branches differ in length by a factor of more than two. SBA is an intended feature of BLAST searches, but becomes an issue, when top scoring BLAST hit analyses are used to infer Horizontal Gene Transfers (HGTs), assign taxonomic category with environmental sequence data in phylotyping, or gather homologous sequences for building gene families. SBA can lead researchers to believe that there has been a HGT event when only vertical descent has occurred, cause slowly evolving taxa to be over-represented and quickly evolving taxa to be under-represented in phylotyping, or systematically exclude quickly evolving taxa from analyses. SBA also contributes to the changing results of top scoring BLAST hit analyses as the database grows, because more slowly evolving taxa, or short branches, are added over time, introducing more potential for SBA. SBA can be detected by examining reciprocal best BLAST hits among a larger group of taxa, including the known closest phylogenetic neighbors. Therefore, one should look for this phenomenon when conducting best BLAST hit analyses as a surrogate method to identify HGTs, in phylotyping, or when using BLAST to gather homologous sequences.

Systematic inference of highways of horizontal gene transfer in prokaryotes.

MOTIVATION: Horizontal gene transfer (HGT) plays a crucial role in the evolution of prokaryotic species. Typically, no more than a few genes are horizontally transferred between any two species. However, several studies identified pairs of species (or linages) between which many different genes were horizontally transferred. Such a pair is said to be linked by a highway of gene sharing. Inferring such highways is crucial to understanding the evolution of prokaryotes and for inferring past symbiotic and ecological associations among different species. RESULTS: We present a new improved method for systematically detecting highways of gene sharing. As we demonstrate using a variety of simulated datasets, our method is highly accurate and efficient, and robust to noise and high rates of HGT. We further validate our method by applying it to a published dataset of >22 000 gene trees from 144 prokaryotic species. Our method makes it practical, for the first time, to perform accurate highway analysis quickly and easily even on large datasets with high rates of HGT. AVAILABILITY AND IMPLEMENTATION: An implementation of the method can be freely downloaded from: http://acgt.cs.tau.ac.il/hide.

Thermotoga lettingae can salvage cobinamide to synthesize vitamin B12.

We recently reported that the Thermotogales acquired the ability to synthesize vitamin B12 by acquisition of genes from two distantly related lineages, Archaea and Firmicutes (K. S. Swithers et al., Genome Biol. Evol. 4:730-739, 2012). Ancestral state reconstruction suggested that the cobinamide salvage gene cluster was present in the Thermotogales' most recent common ancestor. We also predicted that Thermotoga lettingae could not synthesize B12 de novo but could use the cobinamide salvage pathway to synthesize B12. In this study, these hypotheses were tested, and we found that Tt. lettingae did not synthesize B12 de novo but salvaged cobinamide. The growth rate of Tt. lettingae increased with the addition of B12 or cobinamide to its medium. It synthesized B12 when the medium was supplemented with cobinamide, and no B12 was detected in cells grown on cobinamide-deficient medium. Upstream of the cobinamide salvage genes is a putative B12 riboswitch. In other organisms, B12 riboswitches allow for higher transcriptional activity in the absence of B12. When Tt. lettingae was grown with no B12, the salvage genes were upregulated compared to cells grown with B12 or cobinamide. Another gene cluster with a putative B12 riboswitch upstream is the btuFCD ABC transporter, and it showed a transcription pattern similar to that of the cobinamide salvage genes. The BtuF proteins from species that can and cannot salvage cobinamides were shown in vitro to bind both B12 and cobinamide. These results suggest that Thermotogales species can use the BtuFCD transporter to import both B12 and cobinamide, even if they cannot salvage cobinamide.

Biased gene transfer mimics patterns created through shared ancestry.

In phylogenetic reconstruction, two types of bacterial tyrosyl-tRNA synthetases (TyrRS) form distinct clades with many bacterial phyla represented in both clades. Very few taxa possess both forms, and maximum likelihood analysis of the distribution of TyrRS types suggests horizontal gene transfer (HGT), rather than an ancient duplication followed by differential gene loss, as the contributor to the evolutionary history of TyrRS in bacteria. However, for each TyrRS type, phylogenetic reconstruction yields phylogenies similar to the ribosomal phylogeny, revealing that frequent gene transfer has not destroyed the expected phylogeny; rather, the expected phylogenetic signal was reinforced or even created by HGT. We show that biased HGT can mimic patterns created through shared ancestry by in silico simulation. Furthermore, in cases where genomic synteny is sufficient to allow comparisons of relative gene positions, both tyrRS types occupy equivalent positions in closely related genomes, rejecting the loss hypothesis. Although the two types of bacterial TyrRS are only distantly related and only rarely coexist in a single genome, they have many features in common with alleles that are swapped between related lineages. We propose to label these functionally similar homologs as homeoalleles. We conclude that the observed phylogenetic pattern reflects both vertical inheritance and biased HGT and that the signal caused by common organismal descent is difficult to distinguish from the signal due to biased gene transfer.

Protocol for an agent-based model of recombination in bacteria playing a public goods game.

Agent-based models are composed of individual agents coded for traits, such as cooperation and cheating, that interact in a virtual world based on defined rules. Here, we describe the use of an agent-based model of homologous recombination in bacteria playing a public goods game. We describe steps for software installation, setting model parameters, running and testing models, and visualization and statistical analysis. This protocol is useful in analyses of horizontal gene transfer, bacterial sociobiology, and game theory. For complete details on the use and execution of this protocol, please refer to Lee et al.1.

Recombination as an enforcement mechanism of prosocial behavior in cooperating bacteria.

Prosocial behavior is ubiquitous in nature despite the relative fitness costs carried by cooperative individuals. However, the stability of cooperation in populations is fragile and often maintained through enforcement. We propose that homologous recombination provides such a mechanism in bacteria. Using an agent-based model of recombination in bacteria playing a public goods game, we demonstrate how changes in recombination rates affect the proportion of cooperating cells. In our model, recombination converts cells to a different strategy, either freeloading (cheaters) or cooperation, based on the strategies of neighboring cells and recombination rate. Increasing the recombination rate expands the parameter space in which cooperators outcompete freeloaders. However, increasing the recombination rate alone is neither sufficient nor necessary. Intermediate benefits of cooperation, lower population viscosity, and greater population size can promote the evolution of cooperation from within populations of cheaters. Our findings demonstrate how recombination influences the persistence of cooperative behavior in bacteria.

Quartet decomposition server: a platform for analyzing phylogenetic trees.

BACKGROUND: The frequent exchange of genetic material among prokaryotes means that extracting a majority or plurality phylogenetic signal from many gene families, and the identification of gene families that are in significant conflict with the plurality signal is a frequent task in comparative genomics, and especially in phylogenomic analyses. Decomposition of gene trees into embedded quartets (unrooted trees each with four taxa) is a convenient and statistically powerful technique to address this challenging problem. This approach was shown to be useful in several studies of completely sequenced microbial genomes. RESULTS: We present here a web server that takes a collection of gene phylogenies, decomposes them into quartets, generates a Quartet Spectrum, and draws a split network. Users are also provided with various data download options for further analyses. Each gene phylogeny is to be represented by an assessment of phylogenetic information content, such as sets of trees reconstructed from bootstrap replicates or sampled from a posterior distribution. The Quartet Decomposition server is accessible at http://quartets.uga.edu. CONCLUSIONS: The Quartet Decomposition server presented here provides a convenient means to perform Quartet Decomposition analyses and will empower users to find statistically supported phylogenetic conflicts.

Ancient origin of the divergent forms of leucyl-tRNA synthetases in the Halobacteriales.

BACKGROUND: Horizontal gene transfer (HGT) has greatly impacted the genealogical history of many lineages, particularly for prokaryotes, with genes frequently moving in and out of a line of descent. Many genes that were acquired by a lineage in the past likely originated from ancestral relatives that have since gone extinct. During the course of evolution, HGT has played an essential role in the origin and dissemination of genetic and metabolic novelty. RESULTS: Three divergent forms of leucyl-tRNA synthetase (LeuRS) exist in the archaeal order Halobacteriales, commonly known as haloarchaea. Few haloarchaeal genomes have the typical archaeal form of this enzyme and phylogenetic analysis indicates it clusters within the Euryarchaeota as expected. The majority of sequenced halobacterial genomes possess a bacterial form of LeuRS. Phylogenetic reconstruction puts this larger group of haloarchaea at the base of the bacterial domain. The most parsimonious explanation is that an ancient transfer of LeuRS took place from an organism related to the ancestor of the bacterial domain to the haloarchaea. The bacterial form of LeuRS further underwent gene duplications and/or gene transfers within the haloarchaea, with some genomes possessing two distinct types of bacterial LeuRS. The cognate tRNALeu also reveals two distinct clusters for the haloarchaea; however, these tRNALeu clusters do not coincide with the groupings found in the LeuRS tree, revealing that LeuRS evolved independently of its cognate tRNA. CONCLUSIONS: The study of leucyl-tRNA synthetase in haloarchaea illustrates the importance of gene transfer originating in lineages that went extinct since the transfer occurred. The haloarchaeal LeuRS and tRNALeu did not co-evolve.

Estimating the size of the bacterial pan-genome.

The 'pan-genome' denotes the set of all genes present in the genomes of a group of organisms. Here, we extend the pan-genome concept to higher taxonomic units. Using 573 sequenced genomes, we estimate the size of the bacterial pan-genome based on the frequency of occurrences of genes among sampled genomes. Using gene- and genome-centered approaches, we characterize three distinct pools of gene families that comprise the bacterial pan-genome, each evolving under different evolutionary constraints. Our findings indicate that the pan-genome of the bacterial domain is of infinite size (the Bacteria as a whole have an open pan-genome) and that approximately 250 genes per genome belong to the extended bacterial core genome.

On the chimeric nature, thermophilic origin, and phylogenetic placement of the Thermotogales.

Since publication of the first Thermotogales genome, Thermotoga maritima strain MSB8, single- and multi-gene analyses have disagreed on the phylogenetic position of this order of Bacteria. Here we present the genome sequences of 4 additional members of the Thermotogales (Tt. petrophila, Tt. lettingae, Thermosipho melanesiensis, and Fervidobacterium nodosum) and a comprehensive comparative analysis including the original T. maritima genome. While ribosomal protein genes strongly place Thermotogales as a sister group to Aquificales, the majority of genes with sufficient phylogenetic signal show affinities to Archaea and Firmicutes, especially Clostridia. Indeed, on the basis of the majority of genes in their genomes (including genes that are also found in Aquificales), Thermotogales should be considered members of the Firmicutes. This result highlights the conflict between the taxonomic goal of assigning every species to a unique position in an inclusive Linnaean hierarchy and the evolutionary goal of understanding phylogenesis in the presence of pervasive horizontal gene transfer (HGT) within prokaryotes. Amino acid compositions of reconstructed ancestral sequences from 423 gene families suggest an origin of this gene pool even more thermophilic than extant members of this order, followed by adaptation to lower growth temperatures within the Thermotogales.

Bacterial cooperation through horizontal gene transfer.

Cooperation exists across all scales of biological organization, from genetic elements to complex human societies. Bacteria cooperate by secreting molecules that benefit all individuals in the population (i.e., public goods). Genes associated with cooperation can spread among strains through horizontal gene transfer (HGT). We discuss recent findings on how HGT mediated by mobile genetic elements promotes bacterial cooperation, how cooperation in turn can facilitate more frequent HGT, and how the act of HGT itself may be considered as a form of cooperation. We propose that HGT is an important enforcement mechanism in bacterial populations, thus creating a positive feedback loop that further maintains cooperation. To enforce cooperation, HGT serves as a homogenizing force by transferring the cooperative trait, effectively eliminating cheaters.

Genome sequence of Kosmotoga olearia strain TBF 19.5.1, a thermophilic bacterium with a wide growth temperature range, isolated from the Troll B oil platform in the North Sea.

Kosmotoga olearia strain TBF 19.5.1 is a member of the Thermotogales that grows best at 65°C and very well even at 37°C. Information about this organism is important for understanding the evolution of mesophiles from thermophiles. Its genome sequence reveals extensive gene gains and a large content of mobile genetic elements. It also contains putative hydrogenase genes that have no homologs in the other member of the Thermotogales.

Genome sequence of Thermotoga sp. strain RQ2, a hyperthermophilic bacterium isolated from a geothermally heated region of the seafloor near Ribeira Quente, the Azores.

Thermotoga sp. strain RQ2 is probably a strain of Thermotoga maritima. Its complete genome sequence allows for an examination of the extent and consequences of gene flow within Thermotoga species and strains. Thermotoga sp. RQ2 differs from T. maritima in its genes involved in myo-inositol metabolism. Its genome also encodes an apparent fructose phosphotransferase system (PTS) sugar transporter. This operon is also found in Thermotoga naphthophila strain RKU-10 but no other Thermotogales. These are the first reported PTS transporters in the Thermotogales.

Rooting the ribosomal tree of life.

The origin of the genetic code and the rooting of the tree of life (ToL) are two of the most challenging problems in the study of life's early evolution. Although both have been the focus of numerous investigations utilizing a variety of methods, until now, each problem has been addressed independently. Typically, attempts to root the ToL have relied on phylogenies of genes with ancient duplications, which are subject to artifacts of tree reconstruction and horizontal gene transfer, or specific physiological characters believed to be primitive, which are often based on subjective criteria. Here, we demonstrate a unique method for rooting based on the identification of amino acid usage biases comprising the residual signature of a more primitive genetic code. Using a phylogenetic tree of concatenated ribosomal proteins, our analysis of amino acid compositional bias detects a strong and unique signal associated with the early expansion of the genetic code, placing the root of the translation machinery along the bacterial branch.

Molecular evolution of aminoacyl tRNA synthetase proteins in the early history of life.

Aminoacyl-tRNA synthetases (aaRS) consist of several families of functionally conserved proteins essential for translation and protein synthesis. Like nearly all components of the translation machinery, most aaRS families are universally distributed across cellular life, being inherited from the time of the Last Universal Common Ancestor (LUCA). However, unlike the rest of the translation machinery, aaRS have undergone numerous ancient horizontal gene transfers, with several independent events detected between domains, and some possibly involving lineages diverging before the time of LUCA. These transfers reveal the complexity of molecular evolution at this early time, and the chimeric nature of genomes within cells that gave rise to the major domains. Additionally, given the role of these protein families in defining the amino acids used for protein synthesis, sequence reconstruction of their pre-LUCA ancestors can reveal the evolutionary processes at work in the origin of the genetic code. In particular, sequence reconstructions of the paralog ancestors of isoleucyl- and valyl- RS provide strong empirical evidence that at least for this divergence, the genetic code did not co-evolve with the aaRSs; rather, both amino acids were already part of the genetic code before their cognate aaRSs diverged from their common ancestor. The implications of this observation for the early evolution of RNA-directed protein biosynthesis are discussed.

Using comparative genome analysis to identify problems in annotated microbial genomes.

Genome annotation is a tedious task that is mostly done by automated methods; however, the accuracy of these approaches has been questioned since the beginning of the sequencing era. Genome annotation is a multilevel process, and errors can emerge at different stages: during sequencing, as a result of gene-calling procedures, and in the process of assigning gene functions. Missed or wrongly annotated genes differentially impact different types of analyses. Here we discuss and demonstrate how the methods of comparative genome analysis can refine annotations by locating missing orthologues. We also discuss possible reasons for errors and show that the second-generation annotation systems, which combine multiple gene-calling programs with similarity-based methods, perform much better than the first annotation tools. Since old errors may propagate to the newly sequenced genomes, we emphasize that the problem of continuously updating popular public databases is an urgent and unresolved one. Due to the progress in genome-sequencing technologies, automated annotation techniques will remain the main approach in the future. Researchers need to be aware of the existing errors in the annotation of even well-studied genomes, such as Escherichia coli, and consider additional quality control for their results.

Insights into gene expression changes under conditions that facilitate horizontal gene transfer (mating) of a model archaeon.

Horizontal gene transfer is a means by which bacteria, archaea, and eukaryotes are able to trade DNA within and between species. While there are a variety of mechanisms through which this genetic exchange can take place, one means prevalent in the archaeon Haloferax volcanii involves the transient formation of cytoplasmic bridges between cells and is referred to as mating. This process can result in the exchange of very large fragments of DNA between the participating cells. Genes governing the process of mating, including triggers to initiate mating, mechanisms of cell fusion, and DNA exchange, have yet to be characterized. We used a transcriptomic approach to gain a more detailed knowledge of how mating might transpire. By examining the differential expression of genes expressed in cells harvested from mating conditions on a filter over time and comparing them to those expressed in a shaking culture, we were able to identify genes and pathways potentially associated with mating. These analyses provide new insights into both the mechanisms and barriers of mating in Hfx. volcanii.

Conservation of intron and intein insertion sites: implications for life histories of parasitic genetic elements.

BACKGROUND: Inteins and introns are genetic elements that are removed from proteins and RNA after translation or transcription, respectively. Previous studies have suggested that these genetic elements are found in conserved parts of the host protein. To our knowledge this type of analysis has not been done for group II introns residing within a gene. Here we provide quantitative statistical support from an analyses of proteins that host inteins, group I introns, group II introns and spliceosomal introns across all three domains of life. RESULTS: To determine whether or not inteins, group I, group II, and spliceosomal introns are found preferentially in conserved regions of their respective host protein, conservation profiles were generated and intein and intron positions were mapped to the profiles. Fisher's combined probability test was used to determine the significance of the distribution of insertion sites across the conservation profile for each protein. For a subset of studied proteins, the conservation profile and insertion positions were mapped to protein structures to determine if the insertion sites correlate to regions of functional activity. All inteins and most group I introns were found to be preferentially located within conserved regions; in contrast, a bacterial intein-like protein, group II and spliceosomal introns did not show a preference for conserved sites. CONCLUSIONS: These findings demonstrate that inteins and group I introns are found preferentially in conserved regions of their respective host proteins. Homing endonucleases are often located within inteins and group I introns and these may facilitate mobility to conserved regions. Insertion at these conserved positions decreases the chance of elimination, and slows deletion of the elements, since removal of the elements has to be precise as not to disrupt the function of the protein. Furthermore, functional constrains on the targeted site make it more difficult for hosts to evolve immunity to the homing endonuclease. Therefore, these elements will better survive and propagate as molecular parasites in conserved sites. In contrast, spliceosomal introns and group II introns do not show significant preference for conserved sites and appear to have adopted a different strategy to evade loss.

Complete Genome Sequence of Halorubrum ezzemoulense Strain Fb21.

Isolated from Aran-Bidgol Lake in Iran, and reported here, Halorubrum ezzemoulense strain Fb21 represents the first complete genome from this archaeal species. Local recombination in this genome is in stark contrast to equidistant recombination events in bacteria. The genome's GC bias, however, points to a genome architecture and origin that resemble those of a bacterium. Its availability, genome signatures, and frequent intragenomic recombination mean that Fb21 presents an attractive model organism for this species.

Evolution of acetoclastic methanogenesis in Methanosarcina via horizontal gene transfer from cellulolytic Clostridia.

Phylogenetic analysis confirmed that two genes required for acetoclastic methanogenesis, ackA and pta, were horizontally transferred to the ancestor of Methanosarcina from a derived cellulolytic organism in the class Clostridia. This event likely occurred within the last 475 million years, causing profound changes in planetary methane biogeochemistry.