Inferring and validating horizontal gene transfer events using bipartition dissimilarity

PSA: an effective method for predicting horizontal gene transfers through parsimonious phylogenetic networks

Horizontal gene transfer (HGT) from one organism to another, according to some researchers, can be abundant in the evolution of species. A phylogenetic network is a network structure that describes the HGTs among species. Several studies have proposed methods to construct phylogenetic networks to predict HGTs based on parsimony values. Existing definitions of parsimony values for a phylogenetic network are based on the assumption that each gene site or segment evolves independently along different trees in the network. However, in the current study, we define a novel parsimony value, denoted the p definition, for phylogenetic networks, considering that a gene as a whole typically evolves along a tree. Using Simulated Annealing, a new method called the Phylogeny with Simulated Annealing (PSA) algorithm is proposed to search for an optimal network based on the p definition. The PSA method is tested on the simulated data. The results reveal that the parsimonious networks constructed using PSA can better represent the evolutionary relationships of species involving HGTs. Additionally, the HGTs predicted using PSA are more accurate than those predicted using other methods. The PSA algorithm is publicly accessible at http://github.com/imustu/sap.

Host-Virus Cophylogenetic Trajectories: Investigating Molecular Relationships between Coronaviruses and Bat Hosts

Bats, with their virus tolerance, social behaviors, and mobility, are reservoirs for emerging viruses, including coronaviruses (CoVs) known for genetic flexibility. Studying the cophylogenetic link between bats and CoVs provides vital insights into transmission dynamics and host adaptation. Prior research has yielded valuable insights into phenomena such as host switching, cospeciation, and other dynamics concerning the interaction between CoVs and bats. Nonetheless, a distinct gap exists in the current literature concerning a comparative cophylogenetic analysis focused on elucidating the contributions of sequence fragments to the co-evolution between hosts and viruses. In this study, we analyzed the cophylogenetic patterns of 69 host-virus connections. Among the 69 host-virus links examined, 47 showed significant cophylogeny based on ParaFit and PACo analyses, affirming strong associations. Focusing on two proteins, ORF1ab and spike, we conducted a comparative analysis of host and CoV phylogenies. For ORF1ab, the specific window ranged in multiple sequence alignment (positions 520-680, 770-870, 2930-3070, and 4910-5080) exhibited the lowest Robinson-Foulds (RF) distance (i.e., 84.62%), emphasizing its higher contribution in the cophylogenetic association. Similarly, within the spike region, distinct window ranges (positions 0-140, 60-180, 100-410, 360-550, and 630-730) displayed the lowest RF distance at 88.46%. Our analysis identified six recombination regions within ORF1ab (positions 360-1390, 550-1610, 680-1680, 700-1710, 2060-3090, and 2130-3250), and four within the spike protein (positions 10-510, 50-560, 170-710, and 230-730). The convergence of minimal RF distance regions with combination regions robustly affirms the pivotal role of recombination in viral adaptation to host selection pressures. Furthermore, horizontal gene transfer reveals prominent instances of partial gene transfer events, occurring not only among variants within the same host species but also crossing host species boundaries. This suggests a more intricate pattern of genetic exchange. By employing a multifaceted approach, our comprehensive strategy offers a nuanced understanding of the intricate interactions that govern the co-evolutionary dynamics between bat hosts and CoVs. This deeper insight enhances our comprehension of viral evolution and adaptation mechanisms, shedding light on the broader dynamics that propel viral diversity.

Generalization of Phylogenetic Matching Metrics with Experimental Tests of Practical Advantages

The ability to quantify a dissimilarity of different phylogenetic trees is required in various types of phylogenetic studies, for example, such metrics are used to assess the quality of phylogeny construction methods and to define optimization criteria in supertree building algorithms. In this article, starting from the already described concept of matching metrics, we define three new metrics for rooted phylogenetic trees. One of them, Matching Pair Jaccard (MPJ) distance, is still purely topological, but we now utilize the Jaccard index set dissimilarity measure in its construction. This modification substantially changes the structural features of the metric space. In particular, we investigate the properties of the previously known Matching Cluster Jaccard (MCJ) and the new MPJ metrics, such as the asymptotic behavior of their expected distance between two random trees, the space diameter, and the change of a distance after a single leaf relocation. The other two metrics, Matching Cluster Weight-aware (MCW) and Matching Cluster Jaccard Weight-aware (MCJW) distances, are the first propositions of generalization of matching metrics designed for rooted phylogenies with branch lengths. The experimental tests of the practical utility of the phylogenetic metrics show the superiority of MCJ, MPJ over the previous best tree comparison method. To define the MCW and MCJW metrics, we introduce a general method for constructing matching metrics for weighted rooted phylogenetic trees.

Building alternative consensus trees and supertrees using k-means and Robinson and Foulds distance

MOTIVATION

Each gene has its own evolutionary history which can substantially differ from evolutionary histories of other genes. For example, some individual genes or operons can be affected by specific horizontal gene transfer or recombination events. Thus, the evolutionary history of each gene should be represented by its own phylogenetic tree which may display different evolutionary patterns from the species tree that accounts for the main patterns of vertical descent. However, the output of traditional consensus tree or supertree inference methods is a unique consensus tree or supertree.

RESULTS

We present a new efficient method for inferring multiple alternative consensus trees and supertrees to best represent the most important evolutionary patterns of a given set of gene phylogenies. We show how an adapted version of the popular k-means clustering algorithm, based on some remarkable properties of the Robinson and Foulds distance, can be used to partition a given set of trees into one (for homogeneous data) or multiple (for heterogeneous data) cluster(s) of trees. Moreover, we adapt the popular Caliński-Harabasz, Silhouette, Ball and Hall, and Gap cluster validity indices to tree clustering with k-means. Special attention is given to the relevant but very challenging problem of inferring alternative supertrees. The use of the Euclidean property of the objective function of the method makes it faster than the existing tree clustering techniques, and thus better suited for analyzing large evolutionary datasets.

AVAILABILITY AND IMPLEMENTATION

Our KMeansSuperTreeClustering program along with its C ++ source code is available at: https://github.com/TahiriNadia/KMeansSuperTreeClustering.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

The Generalized Robinson-Foulds Distance for Phylogenetic Trees

The Robinson-Foulds (RF) distance, one of the most widely used metrics for comparing phylogenetic trees, has the advantage of being intuitive, with a natural interpretation in terms of common splits, and it can be computed in linear time, but it has a very low resolution, and it may become trivial for phylogenetic trees with overlapping taxa, that is, phylogenetic trees that share some but not all of their leaf labels. In this article, we study the properties of the Generalized Robinson-Foulds (GRF) distance, a recently proposed metric for comparing any structures that can be described by multisets of multisets of labels, when applied to rooted phylogenetic trees with overlapping taxa, which are described by sets of clusters, that is, by sets of sets of labels. We show that the GRF distance has a very high resolution, it can also be computed in linear time, and it is not (uniformly) equivalent to the RF distance.

Cultivation of a vampire: 'Candidatus Absconditicoccus praedator'

Halorhodospira halophila, one of the most-xerophilic halophiles, inhabits biophysically stressful and energetically expensive, salt-saturated alkaline brines. Here, we report an additional stress factor that is biotic: a diminutive Candidate-Phyla-Radiation bacterium, that we named 'Ca. Absconditicoccus praedator' M39-6, which predates H. halophila M39-5, an obligately photosynthetic, anaerobic purple-sulfur bacterium. We cultivated this association (isolated from the hypersaline alkaline Lake Hotontyn Nur, Mongolia) and characterized their biology. 'Ca. Absconditicoccus praedator' is the first stably cultivated species from the candidate class-level lineage Gracilibacteria (order-level lineage Absconditabacterales). Its closed-and-curated genome lacks genes for the glycolytic, pentose phosphate- and Entner-Doudoroff pathways which would generate energy/reducing equivalents and produce central carbon currencies. Therefore, 'Ca. Absconditicoccus praedator' is dependent on host-derived building blocks for nucleic acid-, protein-, and peptidoglycan synthesis. It shares traits with (the uncultured) 'Ca. Vampirococcus lugosii', which is also of the Gracilibacteria lineage. These are obligate parasitic lifestyle, feeding on photosynthetic anoxygenic Gammaproteobacteria, and absorption of host cytoplasm. Commonalities in their genomic composition and structure suggest that the entire Absconditabacterales lineage consists of predatory species which act to cull the populations of their respective host bacteria. Cultivation of vampire : host associations can shed light on unresolved aspects of their metabolism and ecosystem dynamics at life-limiting extremes.

Evolution of kaiA, a key circadian gene of cyanobacteria

The circadian system of cyanobacteria is built upon a central oscillator consisting of three genes, kaiA, kaiB, and kaiC. The KaiA protein plays a key role in phosphorylation/dephosphorylation cycles of KaiC, which occur over the 24-h period. We conducted a comprehensive evolutionary analysis of the kaiA genes across cyanobacteria. The results show that, in contrast to the previous reports, kaiA has an ancient origin and is as old as cyanobacteria. The kaiA homologs are present in nearly all analyzed cyanobacteria, except Gloeobacter, and have varying domain architecture. Some Prochlorococcales, which were previously reported to lack the kaiA gene, possess a drastically truncated homolog. The existence of the diverse kaiA homologs suggests significant variation of the circadian mechanism, which was described for the model cyanobacterium, Synechococcus elongatus PCC7942. The major structural modifications in the kaiA genes (duplications, acquisition and loss of domains) have apparently been induced by global environmental changes in the different geological periods.

Horizontal gene transfer and recombination analysis of SARS-CoV-2 genes helps discover its close relatives and shed light on its origin

BACKGROUND

The SARS-CoV-2 pandemic is one of  the greatest  global medical and social challenges that have emerged in recent history. Human coronavirus strains discovered during previous SARS outbreaks have been hypothesized to pass from bats to humans using intermediate hosts, e.g. civets for SARS-CoV and camels for MERS-CoV. The discovery of an intermediate host of SARS-CoV-2 and the identification of specific mechanism of its emergence in humans are topics of primary evolutionary importance. In this study we investigate the evolutionary patterns of 11 main genes of SARS-CoV-2. Previous studies suggested that the genome of SARS-CoV-2 is highly similar to the horseshoe bat coronavirus RaTG13 for most of the genes and to some Malayan pangolin coronavirus (CoV) strains for the receptor binding (RB) domain of the spike protein.

RESULTS

We provide a detailed list of statistically significant horizontal gene transfer and recombination events (both intergenic and intragenic) inferred for each of 11 main genes of the SARS-CoV-2 genome. Our analysis reveals that two continuous regions of genes S and N of SARS-CoV-2 may result from intragenic recombination between RaTG13 and Guangdong (GD) Pangolin CoVs. Statistically significant gene transfer-recombination events between RaTG13 and GD Pangolin CoV have been identified in region [1215-1425] of gene S and region [534-727] of gene N. Moreover, some statistically significant recombination events between the ancestors of SARS-CoV-2, RaTG13, GD Pangolin CoV and bat CoV ZC45-ZXC21 coronaviruses have been identified in genes ORF1ab, S, ORF3a, ORF7a, ORF8 and N. Furthermore, topology-based clustering of gene trees inferred for 25 CoV organisms revealed a three-way evolution of coronavirus genes, with gene phylogenies of ORF1ab, S and N forming the first cluster, gene phylogenies of ORF3a, E, M, ORF6, ORF7a, ORF7b and ORF8 forming the second cluster, and phylogeny of gene ORF10 forming the third cluster.

CONCLUSIONS

The results of our horizontal gene transfer and recombination analysis suggest that SARS-CoV-2 could not only be a chimera virus resulting from recombination of the bat RaTG13 and Guangdong pangolin coronaviruses but also a close relative of the bat CoV ZC45 and ZXC21 strains. They also indicate that a GD pangolin may be an intermediate host of this dangerous virus.

Phylogenomic analysis of Clostridioides difficile ribotype 106 strains reveals novel genetic islands and emergent phenotypes

Clostridioides difficile infection (CDI) is a major healthcare-associated diarrheal disease. Consistent with trends across the United States, C. difficile RT106 was the second-most prevalent molecular type in our surveillance in Arizona from 2015 to 2018. A representative RT106 strain displayed robust virulence and 100% lethality in the hamster model of acute CDI. We identified a unique 46 KB genomic island (GI1) in all RT106 strains sequenced to date, including those in public databases. GI1 was not found in its entirety in any other C. difficile clade, or indeed, in any other microbial genome; however, smaller segments were detected in Enterococcus faecium strains. Molecular clock analyses suggested that GI1 was horizontally acquired and sequentially assembled over time. GI1 encodes homologs of VanZ and a SrtB-anchored collagen-binding adhesin, and correspondingly, all tested RT106 strains had increased teicoplanin resistance, and a majority displayed collagen-dependent biofilm formation. Two additional genomic islands (GI2 and GI3) were also present in a subset of RT106 strains. All three islands are predicted to encode mobile genetic elements as well as virulence factors. Emergent phenotypes associated with these genetic islands may have contributed to the relatively rapid expansion of RT106 in US healthcare and community settings.

Discovery of Euryhaline Phycoerythrobilin-Containing Synechococcus and Its Mechanisms for Adaptation to Estuarine Environments

Understanding the strategies developed by different microbial groups to adapt to specific niches is critical. Through genome and transcriptome analyses of two newly isolated novel euryhaline Synechococcus strains, this study revealed that cluster 5 phycoerythrobilin-containing Synechococcus, which are thought to be strictly marine strains, could be abundant in low-salinity waters of the Pearl River estuary (salinity <15 ppt) and explained the molecular mechanisms that enabled them to adapt the low and fluctuating salinity in the estuarine environment.

Synechococcus are among the most abundant and widely distributed picocyanobacteria on earth. Cluster 5 phycoerythrobilin-containing (PEB-containing) Synechococcus, the major marine Synechococcus, were considered to prefer high salinity, and they are absent in estuarine ecosystems. However, we have detected PEB-containing Synechococcus in some low-salinity (<15-ppt) areas of the Pearl River estuary at an abundance up to 1.0 × 10⁵ cells ml⁻¹. Two PEB-containing Synechococcus strains (HK01 and LTW-R) were isolated, and tests on them revealed their ability to cope with variations in the salinity (from 14 to 44 ppt). Phylogenetic analysis showed that HK01 belonged to a novel Synechococcus clade (HK1), whereas LTW-R was clustered with S5.2 strains. Whole-genome analysis revealed that a membrane channel protein with glycine zipper motifs is unique to euryhaline Synechococcus. The upregulation of this protein, the osmotic sensors, and the heat shock protein HSP20 and the downregulation of the osmolyte biosynthesis enable euryhaline Synechococcus to well adapt to the low and fluctuating salinity in the estuarine environment. In addition, decreasing the salinity in LTW-R strongly downregulated several important metabolic pathways, including photosynthesis, and the Calvin-Benson cycle, whereas its growth was not significantly affected. Moreover, obtaining PEB genes from horizontal gene transfer expands the light niche significantly for euryhaline Synechococcus. These results provided new insights into the life strategies and ecological function of marine PEB-containing Synechococcus under the unique environmental condition of estuarine waters, particularly in response to salinity variations.

IMPORTANCE Understanding the strategies developed by different microbial groups to adapt to specific niches is critical. Through genome and transcriptome analyses of two newly isolated novel euryhaline Synechococcus strains, this study revealed that cluster 5 phycoerythrobilin-containing Synechococcus, which are thought to be strictly marine strains, could be abundant in low-salinity waters of the Pearl River estuary (salinity <15 ppt) and explained the molecular mechanisms that enabled them to adapt the low and fluctuating salinity in the estuarine environment. This study expands current understanding on mechanisms involved in niche separation of marine Synechococcus lineages.

In silico functional and evolutionary analyses of rubber oxygenases (RoxA and RoxB)

The study presents an in silico identification of poly (cis-1,4-isoprene) cleaving enzymes, viz., RoxA and RoxB in bacteria, followed by their functional and evolutionary exploration using comparative genomics. The orthologs of these proteins were found to be restricted to Gram-negative beta-, gamma-, and delta-proteobacteria. Toward the evolutionary propagation, the RoxA and RoxB genes were predicted to have evolved via a common interclass route of horizontal gene transfer in the phylum Proteobacteria (delta → gamma → beta). Besides, recombination, mutation, and gene conversion were also detected in both the genes leading to their diversification. Further, the differential selective pressure is predicted to be operating on entire RoxA and RoxB genes such that the former is diversifying further, whereas the latter is evolving to reduce its genetic diversity. However, the structurally and functionally important sites/residues of these genes were found to be preventing changes implying their evolutionary conservation. Further, the phylogenetic analysis demonstrated a sharp split between the RoxA and RoxB orthologs and indicated the emergence of their variant as another type of putative rubber oxygenase (RoxC) in the class Gammaproteobacteria. A detailed in silico analysis of the signature motifs and residues of Rox sequences exhibited important differences as well as similarities among the RoxA, RoxB, and putative RoxC sequences. Although RoxC appears to be a hybrid of RoxA and RoxB, the signature motifs and residues of RoxC are more similar to RoxB.

Patterns and impacts of nonvertical evolution in eukaryotes: a paradigm shift

Evolution of eukaryotic species and their genomes has been traditionally understood as a vertical process in which genetic material is transmitted from parents to offspring along a lineage, and in which genetic exchange is restricted within species boundaries. However, mounting evidence from comparative genomics indicates that this paradigm is often violated. Horizontal gene transfer and mating between diverged lineages blur species boundaries and challenge the reconstruction of evolutionary histories of species and their genomes. Nonvertical evolution might be more restricted in eukaryotes than in prokaryotes, yet it is not negligible and can be common in certain groups. Recognition of such processes brings about the need to incorporate this complexity into our models, as well as to conceptually reframe eukaryotic diversity and evolution. Here, I review the recent work from genomics studies that supports the effects of nonvertical modes of evolution including introgression, hybridization, and horizontal gene transfer in different eukaryotic groups. I then discuss emerging patterns and effects, illustrated by specific examples, that support the conclusion that nonvertical processes are often at the root of important evolutionary transitions and adaptations. I will argue that a paradigm shift is needed to naturally accommodate nonvertical processes in eukaryotic evolution.

Transfer index, NetUniFrac and some useful shortest path-based distances for community analysis in sequence similarity networks

MOTIVATION

Phylogenetic trees and the methods for their analysis have played a key role in many evolutionary, ecological and bioinformatics studies. Alternatively, phylogenetic networks have been widely used to analyze and represent complex reticulate evolutionary processes which cannot be adequately studied using traditional phylogenetic methods. These processes include, among others, hybridization, horizontal gene transfer, and genetic recombination. Nowadays, sequence similarity and genome similarity networks have become an efficient tool for community analysis of large molecular datasets in comparative studies. These networks can be used for tackling a variety of complex evolutionary problems such as the identification of horizontal gene transfer events, the recovery of mosaic genes and genomes, and the study of holobionts.

RESULTS

The shortest path in a phylogenetic tree is used to estimate evolutionary distances between species. We show how the shortest path concept can be extended to sequence similarity networks by defining five new distances, NetUniFrac, Spp, Spep, Spelp and Spinp, and the Transfer index, between species communities present in the network. These new distances can be seen as network analogs of the traditional UniFrac distance used to assess dissimilarity between species communities in a phylogenetic tree, whereas the Transfer index is intended for estimating the rate and direction of gene transfers, or species dispersal, between different phylogenetic, or ecological, species communities. Moreover, NetUniFrac and the Transfer index can be computed in linear time with respect to the number of edges in the network. We show how these new measures can be used to analyze microbiota and antibiotic resistance gene similarity networks.

AVAILABILITY AND IMPLEMENTATION

Our NetFrac program, implemented in R and C, along with its source code, is freely available on Github at the following URL address: https://github.com/XPHenry/Netfrac.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Distribution and asymptotic behavior of the phylogenetic transfer distance

The transfer distance (TD) was introduced in the classification framework and studied in the context of phylogenetic tree matching. Recently, Lemoine et al. (Nature 556(7702):452–456, 2018. 10.1038/s41586-018-0043-0) showed that TD can be a powerful tool to assess the branch support on large phylogenies, thus providing a relevant alternative to Felsenstein’s bootstrap. This distance allows a reference branch\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β in a reference tree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {T}}$$\end{document}T to be compared to a branch b from another tree T (typically a bootstrap tree), both on the same set of n taxa. The TD between these branches is the number of taxa that must be transferred from one side of b to the other in order to obtain \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β. By taking the minimum TD from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β to all branches in T we define the transfer index, denoted by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi (\beta ,T)$$\end{document}ϕ(β,T), measuring the degree of agreement of T with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β. Let us consider a reference branch \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β having p tips on its light side and define the transfer support (TS) as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 - \phi (\beta ,T)/(p-1)$$\end{document}1-ϕ(β,T)/(p-1). Lemoine et al. (2018) used computer simulations to show that the TS defined in this manner is close to 0 for random “bootstrap” trees. In this paper, we demonstrate that result mathematically: when T is randomly drawn, TS converges in probability to 0 when n tends to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\infty $$\end{document}∞. Moreover, we fully characterize the distribution of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi (\beta ,T)$$\end{document}ϕ(β,T) on caterpillar trees, indicating that the convergence is fast, and that even when n is small, moderate levels of branch support cannot appear by chance.

Genome-wide analysis of horizontally acquired genes in the genus Mycobacterium

Horizontal gene transfer (HGT) was attributed as a major driving force for the innovation and evolution of prokaryotic genomes. Previously, multiple research endeavors were undertaken to decipher HGT in different bacterial lineages. The genus Mycobacterium houses some of the most deadly human pathogens; however, the impact of HGT in Mycobacterium has never been addressed in a systematic way. Previous initiatives to explore the genomic imprints of HGTs in Mycobacterium were focused on few selected species, specifically among the members of Mycobacterium tuberculosis complex. Considering the recent availability of a large number of genomes, the current study was initiated to decipher the probable events of HGTs among 109 completely sequenced Mycobacterium species. Our comprehensive phylogenetic analysis with more than 9,000 families of Mycobacterium proteins allowed us to list several instances of gene transfers spread across the Mycobacterium phylogeny. Moreover, by examining the topology of gene phylogenies here, we identified the species most likely to donate and receive these genes and provided a detailed overview of the putative functions these genes may be involved in. Our study suggested that horizontally acquired foreign genes had played an enduring role in the evolution of Mycobacterium genomes and have contributed to their metabolic versatility and pathogenicity.

A Novel Glaesserella sp. Isolated from Pigs with Severe Respiratory Infections Has a Mosaic Genome with Virulence Factors Putatively Acquired by Horizontal Transfer

An unknown member of the family Pasteurellaceae was repeatedly isolated from 20- to 24-week-old pigs with severe pulmonary lesions reared on the same farm in Victoria, Australia. The etiological diagnosis of the disease was inconclusive. The complete genome sequence analysis of one strain, 15-184, revealed some phylogenic proximity to Glaesserella (Haemophilus) parasuis, the cause of Glasser's disease. However, the sequences of the 16S rRNA and housekeeping genes, as well as the average nucleotide identity scores, differed from those of all other known species in the family Pasteurellaceae The protein content of 15-184 was composite, with 60% of coding sequences matching known G. parasuis products, while more than 20% had a closer relative in the genera Actinobacillus, Mannheimia, Pasteurella, and Bibersteinia Several putative virulence genes absent from G. parasuis but present in other Pasteurellaceae were also found, including the apxIII RTX toxin gene from Actinobacillus pleuropneumoniae, ABC transporters from Actinobacillus minor, and iron transporters from various species. Three prophages and one integrative conjugative element were present in the isolate. Horizontal gene transfers might explain the mosaic genomic structure and atypical metabolic and virulence characteristics of 15-184. This organism has not been assigned a taxonomic position in the family, but this study underlines the need for a large-scale epidemiological and clinical characterization of this novel pathogen in swine populations, as a genomic analysis suggests it could have a severe impact on pig health.IMPORTANCE Several species of Pasteurellaceae cause a range of significant diseases in pigs. A novel member of this family was recently isolated from Australian pigs suffering from severe respiratory infections. Comparative whole-genome analyses suggest that this bacterium represents a new species, which possesses a number of virulence genes horizontally acquired from a diverse range of other Pasteurellaceae While the possible contribution of other coinfecting noncultivable agents to the disease has not been ruled out in this study, the repertoire of virulence genes found in this organism may nevertheless explain some aspects of the associated pathology observed on the farm. The prevalence of this novel pathogen within pig populations is currently unknown. This finding is of particular importance for the pig industry, as this organism can have a serious impact on the health of these animals.

A new fast method for inferring multiple consensus trees using k-medoids

Background

Gene trees carry important information about specific evolutionary patterns which characterize the evolution of the corresponding gene families. However, a reliable species consensus tree cannot be inferred from a multiple sequence alignment of a single gene family or from the concatenation of alignments corresponding to gene families having different evolutionary histories. These evolutionary histories can be quite different due to horizontal transfer events or to ancient gene duplications which cause the emergence of paralogs within a genome. Many methods have been proposed to infer a single consensus tree from a collection of gene trees. Still, the application of these tree merging methods can lead to the loss of specific evolutionary patterns which characterize some gene families or some groups of gene families. Thus, the problem of inferring multiple consensus trees from a given set of gene trees becomes relevant.

Results

We describe a new fast method for inferring multiple consensus trees from a given set of phylogenetic trees (i.e. additive trees or X-trees) defined on the same set of species (i.e. objects or taxa). The traditional consensus approach yields a single consensus tree. We use the popular k-medoids partitioning algorithm to divide a given set of trees into several clusters of trees. We propose novel versions of the well-known Silhouette and Caliński-Harabasz cluster validity indices that are adapted for tree clustering with k-medoids. The efficiency of the new method was assessed using both synthetic and real data, such as a well-known phylogenetic dataset consisting of 47 gene trees inferred for 14 archaeal organisms.

Conclusions

The method described here allows inference of multiple consensus trees from a given set of gene trees. It can be used to identify groups of gene trees having similar intragroup and different intergroup evolutionary histories. The main advantage of our method is that it is much faster than the existing tree clustering approaches, while providing similar or better clustering results in most cases. This makes it particularly well suited for the analysis of large genomic and phylogenetic datasets.

The Performance of Two Supertree Schemes Compared Using Synthetic and Real Data Quartet Input

Despite impressive advancements in technological and theoretical tools, construction of phylogenetic (evolutionary) trees is still a challenging task. The availability of enormous quantities of molecular data has made large-scale phylogenetic reconstruction involving thousands of species, a more viable goal. For this goal, separate trees over different, overlapping subsets of species, representing histories of various markers of these species, are collected. These trees, typically with conflicting signals, are subsequently combined into a single tree over the full set, an operation denoted as supertree construction. The amalgamation of such trees into a single tree lies at the heart of many tasks in phylogenetics, yet remains a daunting endeavor, especially in light of conflicting signals. In this work, we study the performance of matrix representation with parsimony (MRP), the most widely used supertree method to date, when confronted with quartet trees. Quartet trees are the most basic informational unit when amalgamation of unrooted trees is attempted, and they remain relevant in more general settings even though standard supertree methods are not necessarily confined to quartets. This study involves both real and simulated data, and the effects of several parameters on the results are evaluated, revealing a number of anomalies associated with MRP. We show that these anomalies are surmountable when using a recently introduced supertree method, weighted quartet MaxCut (wQMC).

Dissemination of antibiotic resistance genes from antibiotic producers to pathogens

It has been hypothesized that some antibiotic resistance genes (ARGs) found in pathogenic bacteria derive from antibiotic-producing actinobacteria. Here we provide bioinformatic and experimental evidence supporting this hypothesis. We identify genes in proteobacteria, including some pathogens, that appear to be closely related to actinobacterial ARGs known to confer resistance against clinically important antibiotics. Furthermore, we identify two potential examples of recent horizontal transfer of actinobacterial ARGs to proteobacterial pathogens. Based on this bioinformatic evidence, we propose and experimentally test a 'carry-back' mechanism for the transfer, involving conjugative transfer of a carrier sequence from proteobacteria to actinobacteria, recombination of the carrier sequence with the actinobacterial ARG, followed by natural transformation of proteobacteria with the carrier-sandwiched ARG. Our results support the existence of ancient and, possibly, recent transfers of ARGs from antibiotic-producing actinobacteria to proteobacteria, and provide evidence for a defined mechanism.

Comparing Phylogenetic Trees by Matching Nodes Using the Transfer Distance Between Partitions

Ability to quantify dissimilarity of different phylogenetic trees describing the relationship between the same group of taxa is required in various types of phylogenetic studies. For example, such metrics are used to assess the quality of phylogeny construction methods, to define optimization criteria in supertree building algorithms, or to find horizontal gene transfer (HGT) events. Among the set of metrics described so far in the literature, the most commonly used seems to be the Robinson-Foulds distance. In this article, we define a new metric for rooted trees-the Matching Pair (MP) distance. The MP metric uses the concept of the minimum-weight perfect matching in a complete bipartite graph constructed from partitions of all pairs of leaves of the compared phylogenetic trees. We analyze the properties of the MP metric and present computational experiments showing its potential applicability in tasks related to finding the HGT events.

Several steps of lateral gene transfer followed by events of 'birth-and-death' evolution shaped a fungal sorbicillinoid biosynthetic gene cluster

Background

Sorbicillinoids are a family of complex cyclic polyketides produced by only a small number of distantly related ascomycete fungi such as Trichoderma (Sordariomycetes) and Penicillium (Eurotiomycetes). In T. reesei, they are synthesized by a gene cluster consisting of eight genes including two polyketide synthases (PKS). To reconstruct the evolutionary origin of this gene cluster, we examined the occurrence of these eight genes in ascomycetes.

Results

A cluster comprising at least six of them was only found in Hypocreales (Acremonium chrysogenum, Ustilaginoidea virens, Trichoderma species from section Longibrachiatum) and in Penicillium rubens (Eurotiales). In addition, Colletotrichum graminicola contained the two pks (sor1 and sor2), but not the other sor genes. A. chrysogenum was the evolutionary eldest species in which sor1, sor2, sor3, sor4 and sor6 were present. Sor5 was gained by lateral gene transfer (LGT) from P. rubens. In the younger Hypocreales (U. virens, Trichoderma spp.), the cluster evolved by vertical transfer, but sor2 was lost and regained by LGT from C. graminicola. SorB (=sor2) and sorD (=sor4) were symplesiomorphic in P. rubens, whereas sorA, sorC and sorF were obtained by LGT from A. chrysogenum, and sorE by LGT from Pestalotiopsis fici (Xylariales). The sorbicillinoid gene cluster in Trichoderma section Longibrachiatum is under strong purifying selection. The T. reesei sor genes are expressed during fast vegetative growth, during antagonism of other fungi and regulated by the secondary metabolism regulator LAE1.

Conclusions

Our findings pinpoint the evolution of the fungal sorbicillinoid biosynthesis gene cluster. The core cluster arose in early Hypocreales, and was complemented by LGT. During further speciation in the Hypocreales, it became subject to birth and death evolution in selected lineages. In P. rubrens (Eurotiales), two cluster genes were symplesiomorphic, and the whole cluster formed by LGT from at least two different fungal donors.

Electronic supplementary material

The online version of this article (doi:10.1186/s12862-016-0834-6) contains supplementary material, which is available to authorized users.

Detecting Horizontal Gene Transfer between Closely Related Taxa

Horizontal gene transfer (HGT), the transfer of genetic material between organisms, is crucial for genetic innovation and the evolution of genome architecture. Existing HGT detection algorithms rely on a strong phylogenetic signal distinguishing the transferred sequence from ancestral (vertically derived) genes in its recipient genome. Detecting HGT between closely related species or strains is challenging, as the phylogenetic signal is usually weak and the nucleotide composition is normally nearly identical. Nevertheless, there is a great importance in detecting HGT between congeneric species or strains, especially in clinical microbiology, where understanding the emergence of new virulent and drug-resistant strains is crucial, and often time-sensitive.

We developed a novel, self-contained technique named Near HGT, based on the synteny index, to measure the divergence of a gene from its native genomic environment and used it to identify candidate HGT events between closely related strains. The method confirms candidate transferred genes based on the constant relative mutability (CRM). Using CRM, the algorithm assigns a confidence score based on “unusual” sequence divergence. A gene exhibiting exceptional deviations according to both synteny and mutability criteria, is considered a validated HGT product. We first employed the technique to a set of three E. coli strains and detected several highly probable horizontally acquired genes. We then compared the method to existing HGT detection tools using a larger strain data set.

When combined with additional approaches our new algorithm provides richer picture and brings us closer to the goal of detecting all newly acquired genes in a particular strain.

The transfer of genetic material between organisms, usually denoted as horizontal (or lateral) gene transfer (HGT or LGT), is a prime mechanism in microbial evolution and responsible for genetic innovation and the evolution of genome architecture. Detecting HGT between closely related species or strains is imperative as drug-resistant pathogenic strains most often acquire their virulence from closely related bacteria. The proposed method combines two evolutionary signals that were not employed in the past for this task. One is the synteny index (SI), measuring the loss of synteny in an organism, and the other is a novel concept—constant relative mutability (CRM), maintaining that genes preserve their relative evolution rate along linages (although the latter ones may each change).

We show both in simulation and real biological data that the method is sound and, in the cases examined, provides stronger sensitivity than existing methods. We therefore believe this novel approach represents a significant advance, for the first time enabling the detection of previously ignored HGT events that will bring us closer to the goal of detecting all newly acquired genes in a particular strain.

Availability: The method is publicly available at http://research.haifa.ac.il/~ssagi/software/nearHGT.zip

Involvement of aph(3')-IIa in the formation of mosaic aminoglycoside resistance genes in natural environments

Intragenic recombination leading to mosaic gene formation is known to alter resistance profiles for particular genes and bacterial species. Few studies have examined to what extent aminoglycoside resistance genes undergo intragenic recombination. We screened the GenBank database for mosaic gene formation in homologs of the aph(3')-IIa (nptII) gene. APH(3')-IIa inactivates important aminoglycoside antibiotics. The gene is widely used as a selectable marker in biotechnology and enters the environment via laboratory discharges and the release of transgenic organisms. Such releases may provide opportunities for recombination in competent environmental bacteria. The retrieved GenBank sequences were grouped in three datasets comprising river water samples, duck pathogens and full-length variants from various bacterial genomes and plasmids. Analysis for recombination in these datasets was performed with the Recombination Detection Program (RDP4), and the Genetic Algorithm for Recombination Detection (GARD). From a total of 89 homologous sequences, 83% showed 99-100% sequence identity with aph(3')-IIa originally described as part of transposon Tn5. Fifty one were unique sequence variants eligible for recombination analysis. Only a single recombination event was identified with high confidence and indicated the involvement of aph(3')-IIa in the formation of a mosaic gene located on a plasmid of environmental origin in the multi-resistant isolate Pseudomonas aeruginosa PA96. The available data suggest that aph(3')-IIa is not an archetypical mosaic gene as the divergence between the described sequence variants and the number of detectable recombination events is low. This is in contrast to the numerous mosaic alleles reported for certain penicillin or tetracycline resistance determinants.

Gene acquisition convergence between entomopoxviruses and baculoviruses

Organisms from diverse phylogenetic origins can thrive within the same ecological niches. They might be induced to evolve convergent adaptations in response to a similar landscape of selective pressures. Their genomes should bear the signature of this process. The study of unrelated virus lineages infecting the same host panels guarantees a clear identification of phyletically independent convergent adaptation. Here, we investigate the evolutionary history of genes in the accessory genome shared by unrelated insect large dsDNA viruses: the entomopoxviruses (EPVs, Poxviridae) and the baculoviruses (BVs). EPVs and BVs have overlapping ecological niches and have independently evolved similar infection processes. They are, in theory, subjected to the same selective pressures from their host’s immune responses. Their accessory genomes might, therefore, bear analogous genomic signatures of convergent adaption and could point out key genomic mechanisms of adaptation hitherto undetected in viruses. We uncovered 32 homologous, yet independent acquisitions of genes originating from insect hosts, different eukaryotes, bacteria and viruses. We showed different evolutionary levels of gene acquisition convergence in these viruses, underlining a continuous evolutionary process. We found both recent and ancient gene acquisitions possibly involved to the adaptation to both specific and distantly related hosts. Multidirectional and multipartite gene exchange networks appear to constantly drive exogenous gene assimilations, bringing key adaptive innovations and shaping the life histories of large DNA viruses. This evolutionary process might lead to genome level adaptive convergence.

A new efficient algorithm for inferring explicit hybridization networks following the Neighbor-Joining principle

Several algorithms and software have been developed for inferring phylogenetic trees. However, there exist some biological phenomena such as hybridization, recombination, or horizontal gene transfer which cannot be represented by a tree topology. We need to use phylogenetic networks to adequately represent these important evolutionary mechanisms. In this article, we present a new efficient heuristic algorithm for inferring hybridization networks from evolutionary distance matrices between species. The famous Neighbor-Joining concept and the least-squares criterion are used for building networks. At each step of the algorithm, before joining two given nodes, we check if a hybridization event could be related to one of them or to both of them. The proposed algorithm finds the exact tree solution when the considered distance matrix is a tree metric (i.e. it is representable by a unique phylogenetic tree). It also provides very good hybrids recovery rates for large trees (with 32 and 64 leaves in our simulations) for both distance and sequence types of data. The results yielded by the new algorithm for real and simulated datasets are illustrated and discussed in detail.

Distinct molecular features facilitating ice-binding mechanisms in hyperactive antifreeze proteins closely related to an Antarctic sea ice bacterium

Antifreeze proteins or ice-binding proteins (IBPs) facilitate the survival of certain cellular organisms in freezing environment by inhibiting the growth of ice crystals in solution. Present study identifies orthologs of the IBP of Colwellia sp. SLW05, which were obtained from a wide range of taxa. Phylogenetic analysis on the basis of conserved regions (predicted as the 'ice-binding domain' [IBD]) present in all the orthologs, separates the bacterial and archaeal orthologs from that of the eukaryotes'. Correspondence analysis pointed out that the bacterial and archaeal IBDs have relatively higher average hydrophobicity than the eukaryotic members. IBDs belonging to bacterial as well as archaeal AFPs contain comparatively more strands, and therefore are revealed to be under higher evolutionary selection pressure. Molecular docking studies prove that the ice crystals form more stable complex with the bacterial as well as archaeal proteins than the eukaryotic orthologs. Analysis of the docked structures have traced out the ice-binding sites (IBSs) in all the orthologs which continue to facilitate ice-binding activity even after getting mutated with respect to the well-studied IBSs of Typhula ishikariensis and notably, all these mutations performing ice-binding using 'anchored clathrate mechanism' have been found to prefer polar and hydrophilic amino acids. Horizontal gene transfer studies point toward a strong selection pressure favoring independent evolution of the IBPs in some polar organisms including prokaryotes as well as eukaryotes because these proteins facilitate the polar organisms to acclimatize to the adversities in their niche, thus safeguarding their existence.

Reconciliation of gene and species trees

The first part of the paper briefly overviews the problem of gene and species trees reconciliation with the focus on defining and algorithmic construction of the evolutionary scenario. Basic ideas are discussed for the aspects of mapping definitions, costs of the mapping and evolutionary scenario, imposing time scales on a scenario, incorporating horizontal gene transfers, binarization and reconciliation of polytomous trees, and construction of species trees and scenarios. The review does not intend to cover the vast diversity of literature published on these subjects. Instead, the authors strived to overview the problem of the evolutionary scenario as a central concept in many areas of evolutionary research. The second part provides detailed mathematical proofs for the solutions of two problems: (i) inferring a gene evolution along a species tree accounting for various types of evolutionary events and (ii) trees reconciliation into a single species tree when only gene duplications and losses are allowed. All proposed algorithms have a cubic time complexity and are mathematically proved to find exact solutions. Solving algorithms for problem (ii) can be naturally extended to incorporate horizontal transfers, other evolutionary events, and time scales on the species tree.

Interactions in the microbiome: communities of organisms and communities of genes

A central challenge in microbial community ecology is the delineation of appropriate units of biodiversity, which can be taxonomic, phylogenetic, or functional in nature. The term 'community' is applied ambiguously; in some cases, the term refers simply to a set of observed entities, while in other cases, it requires that these entities interact with one another. Microorganisms can rapidly gain and lose genes, potentially decoupling community roles from taxonomic and phylogenetic groupings. Trait-based approaches offer a useful alternative, but many traits can be defined based on gene functions, metabolic modules, and genomic properties, and the optimal set of traits to choose is often not obvious. An analysis that considers taxon assignment and traits in concert may be ideal, with the strengths of each approach offsetting the weaknesses of the other. Individual genes also merit consideration as entities in an ecological analysis, with characteristics such as diversity, turnover, and interactions modeled using genes rather than organisms as entities. We identify some promising avenues of research that are likely to yield a deeper understanding of microbial communities that shift from observation-based questions of 'Who is there?' and 'What are they doing?' to the mechanistically driven question of 'How will they respond?'

Inferring explicit weighted consensus networks to represent alternative evolutionary histories

BACKGROUND

The advent of molecular biology techniques and constant increase in availability of genetic material have triggered the development of many phylogenetic tree inference methods. However, several reticulate evolution processes, such as horizontal gene transfer and hybridization, have been shown to blur the species evolutionary history by causing discordance among phylogenies inferred from different genes.

METHODS

To tackle this problem, we hereby describe a new method for inferring and representing alternative (reticulate) evolutionary histories of species as an explicit weighted consensus network which can be constructed from a collection of gene trees with or without prior knowledge of the species phylogeny.

RESULTS

We provide a way of building a weighted phylogenetic network for each of the following reticulation mechanisms: diploid hybridization, intragenic recombination and complete or partial horizontal gene transfer. We successfully tested our method on some synthetic and real datasets to infer the above-mentioned evolutionary events which may have influenced the evolution of many species.

CONCLUSIONS

Our weighted consensus network inference method allows one to infer, visualize and validate statistically major conflicting signals induced by the mechanisms of reticulate evolution. The results provided by the new method can be used to represent the inferred conflicting signals by means of explicit and easy-to-interpret phylogenetic networks.

The origin of parasitism gene in nematodes: evolutionary analysis through the construction of domain trees

Inferring evolutionary history of parasitism genes is important to understand how evolutionary mechanisms affect the occurrences of parasitism genes. In this study, we constructed multiple domain trees for parasitism genes and genes under free-living conditions. Further analyses of horizontal gene transfer (HGT)-like phylogenetic incongruences, duplications, and speciations were performed based on these trees. By comparing these analyses, the contributions of pre-adaptations were found to be more important to the evolution of parasitism genes than those of duplications, and pre-adaptations are as crucial as previously reported HGTs to parasitism. Furthermore, speciation may also affect the evolution of parasitism genes. In addition, Pristionchus pacificus was suggested to be a common model organism for studies of parasitic nematodes, including root-knot species. These analyses provided information regarding mechanisms that may have contributed to the evolution of parasitism genes.

New insights on the biology of swine respiratory tract mycoplasmas from a comparative genome analysis

BACKGROUND

Mycoplasma hyopneumoniae, Mycoplasma flocculare and Mycoplasma hyorhinis live in swine respiratory tracts. M. flocculare, a commensal bacterium, is genetically closely related to M. hyopneumoniae, the causative agent of enzootic porcine pneumonia. M. hyorhinis is also pathogenic, causing polyserositis and arthritis. In this work, we present the genome sequences of M. flocculare and M. hyopneumoniae strain 7422, and we compare these genomes with the genomes of other M. hyoponeumoniae strain and to the a M. hyorhinis genome. These analyses were performed to identify possible characteristics that may help to explain the different behaviors of these species in swine respiratory tracts.

RESULTS

The overall genome organization of three species was analyzed, revealing that the ORF clusters (OCs) differ considerably and that inversions and rearrangements are common. Although M. flocculare and M. hyopneumoniae display a high degree of similarity with respect to the gene content, only some genomic regions display considerable synteny. Genes encoding proteins that may be involved in host-cell adhesion in M. hyopneumoniae and M. flocculare display differences in genomic structure and organization. Some genes encoding adhesins of the P97 family are absent in M. flocculare and some contain sequence differences or lack of domains that are considered to be important for adhesion to host cells. The phylogenetic relationship of the three species was confirmed by a phylogenomic approach. The set of genes involved in metabolism, especially in the uptake of precursors for nucleic acids synthesis and nucleotide metabolism, display some differences in copy number and the presence/absence in the three species.

CONCLUSIONS

The comparative analyses of three mycoplasma species that inhabit the swine respiratory tract facilitated the identification of some characteristics that may be related to their different behaviors. M. hyopneumoniae and M. flocculare display many differences that may help to explain why one species is pathogenic and the other is considered to be commensal. However, it was not possible to identify specific virulence determinant factors that could explain the differences in the pathogenicity of the analyzed species. The M. hyorhinis genome contains differences in some components involved in metabolism and evasion of the host's immune system that may contribute to its growth aggressiveness. Several horizontal gene transfer events were identified. The phylogenomic analysis places M. hyopneumoniae, M. flocculare and M. hyorhinis in the hyopneumoniae clade.

In silico analysis of tkt1 from avian pathogenic Escherichia coli and its virulence evaluation in chickens

Extraintestinal pathogenic Escherichia coli (ExPEC) contain tktA and tktB which code for transketolases involved in the pentose phosphate pathway. Recent studies demonstrated that a third gene coding for transketolase 1 (tkt1) was located in a pathogenicity island of avian and human ExPEC belonging to phylogenetic group B2. In the present study, in silico analysis of tkt1 revealed 68% and 69% identity with tktA and tktB, respectively, of ExPEC and 68% identity with tktA and tktB of E. coli MG1655. The translated tkt1 shared 69% and 68% identity with TktA and TktB proteins, respectively, of ExPEC and E. coli MG1655. Phylogenetically, it is shown that the three genes (tktA, tktB and tkt1) cluster in three different clades. Further analysis suggests that tkt1 has been acquired though horizontal gene transfer from plant-associated bacteria within the family Enterobacteriaceae. Virulence studies were performed in order to evaluate whether tkt1 played a role in avian pathogenic E. coli CH2 virulence in chickens. The evaluation revealed that mutant virulence was slightly lower based on LD50 when compared to the wild type during infection of chickens, but there were no significant differences when the two strains were compared based on the number of deaths and lesion scores.

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.

Simultaneous identification of duplications, losses, and lateral gene transfers

We give a fixed-parameter algorithm for the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Our algorithm can work for the weighted version of the problem, where the costs of a gene duplication, a gene loss, and an LGT are left to the user's discretion. The algorithm runs in O(m + 3(k/c)n) time, where m is the number of vertices in S, n is the number of vertices in G, c is the smaller between a gene duplication cost and an LGT cost, and k is the minimum cost of an LCA-reconciliation between S and G. The time complexity is indeed better if the cost of a gene loss is greater than 0. In particular, when the cost of a gene loss is at least 0.614c, the running time of the algorithm is O(m + 2.78(k/c)n).

Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss

MOTIVATION

Gene family evolution is driven by evolutionary events such as speciation, gene duplication, horizontal gene transfer and gene loss, and inferring these events in the evolutionary history of a given gene family is a fundamental problem in comparative and evolutionary genomics with numerous important applications. Solving this problem requires the use of a reconciliation framework, where the input consists of a gene family phylogeny and the corresponding species phylogeny, and the goal is to reconcile the two by postulating speciation, gene duplication, horizontal gene transfer and gene loss events. This reconciliation problem is referred to as duplication-transfer-loss (DTL) reconciliation and has been extensively studied in the literature. Yet, even the fastest existing algorithms for DTL reconciliation are too slow for reconciling large gene families and for use in more sophisticated applications such as gene tree or species tree reconstruction.

RESULTS

We present two new algorithms for the DTL reconciliation problem that are dramatically faster than existing algorithms, both asymptotically and in practice. We also extend the standard DTL reconciliation model by considering distance-dependent transfer costs, which allow for more accurate reconciliation and give an efficient algorithm for DTL reconciliation under this extended model. We implemented our new algorithms and demonstrated up to 100 000-fold speed-up over existing methods, using both simulated and biological datasets. This dramatic improvement makes it possible to use DTL reconciliation for performing rigorous evolutionary analyses of large gene families and enables its use in advanced reconciliation-based gene and species tree reconstruction methods.

AVAILABILITY

Our programs can be freely downloaded from http://compbio.mit.edu/ranger-dtl/.

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.

T-REX: a web server for inferring, validating and visualizing phylogenetic trees and networks

T-REX (Tree and reticulogram REConstruction) is a web server dedicated to the reconstruction of phylogenetic trees, reticulation networks and to the inference of horizontal gene transfer (HGT) events. T-REX includes several popular bioinformatics applications such as MUSCLE, MAFFT, Neighbor Joining, NINJA, BioNJ, PhyML, RAxML, random phylogenetic tree generator and some well-known sequence-to-distance transformation models. It also comprises fast and effective methods for inferring phylogenetic trees from complete and incomplete distance matrices as well as for reconstructing reticulograms and HGT networks, including the detection and validation of complete and partial gene transfers, inference of consensus HGT scenarios and interactive HGT identification, developed by the authors. The included methods allows for validating and visualizing phylogenetic trees and networks which can be built from distance or sequence data. The web server is available at: www.trex.uqam.ca.

Using directed phylogenetic networks to retrace species dispersal history

Methods designed for inferring phylogenetic trees have been widely applied to reconstruct biogeographic history. Because traditional phylogenetic methods used in biogeographic reconstruction are based on trees rather than networks, they follow the strict assumption in which dispersal among geographical units have occurred on the basis of single dispersal routes across regions and are, therefore, incapable of modelling multiple alternative dispersal scenarios. The goal of this study is to describe a new method that allows for retracing species dispersal by means of directed phylogenetic networks obtained using a horizontal gene transfer (HGT) detection method as well as to draw parallels between the processes of HGT and biogeographic reconstruction. In our case study, we reconstructed the biogeographic history of the postglacial dispersal of freshwater fishes in the Ontario province of Canada. This case study demonstrated the utility and robustness of the new method, indicating that the most important events were south-to-north dispersal patterns, as one would expect, with secondary faunal interchange among regions. Finally, we showed how our method can be used to explore additional questions regarding the commonalities in dispersal history patterns and phylogenetic similarities among species.

Detecting highways of horizontal gene transfer

In a horizontal gene transfer (HGT) event, a gene is transferred between two species that do not have an ancestor-descendant relationship. Typically, no more than a few genes are horizontally transferred between any two species. However, several studies identified pairs of species between which many different genes were horizontally transferred. Such a pair is said to be linked by a highway of gene sharing. We present a method for inferring such highways. Our method is based on the fact that the evolutionary histories of horizontally transferred genes disagree with the corresponding species phylogeny. Specifically, given a set of gene trees and a trusted rooted species tree, each gene tree is first decomposed into its constituent quartet trees and the quartets that are inconsistent with the species tree are identified. Our method finds a pair of species such that a highway between them explains the largest (normalized) fraction of inconsistent quartets. For a problem on n species and m input quartet trees, we give an efficient O(m + n(2))-time algorithm for detecting highways, which is optimal with respect to the quartets input size. An application of our method to a dataset of 1128 genes from 11 cyanobacterial species, as well as to simulated datasets, illustrates the efficacy of our method.

Armadillo 1.1: an original workflow platform for designing and conducting phylogenetic analysis and simulations

In this paper we introduce Armadillo v1.1, a novel workflow platform dedicated to designing and conducting phylogenetic studies, including comprehensive simulations. A number of important phylogenetic and general bioinformatics tools have been included in the first software release. As Armadillo is an open-source project, it allows scientists to develop their own modules as well as to integrate existing computer applications. Using our workflow platform, different complex phylogenetic tasks can be modeled and presented in a single workflow without any prior knowledge of programming techniques. The first version of Armadillo was successfully used by professors of bioinformatics at Université du Quebec à Montreal during graduate computational biology courses taught in 2010–11. The program and its source code are freely available at: <http://www.bioinfo.uqam.ca/armadillo>.

Detecting laterally transferred genes

Methods for identifying alien genes in genomes fall into two general classes. Phylogenetic methods examine the distribution of a gene's homologues among genomes to find those with relationships not consistent with vertical inheritance. These approaches include identifying orphan genes which lack homologues in closely related genomes and genes with unduly high levels of similarity to genes in otherwise unrelated genomes. Rigorous statistical tests are available to place confidence intervals for predicted alien genes. Parametric methods examine the compositional properties of genes within a genome to find those with atypical properties, likely indicating the directional mutational pressures of a donor genome. These methods may compare the properties of genes to genomic averages, properties of genes to each other, or properties of large, multigene regions of the chromosome. Here, we discuss the strengths and weaknesses of each approach.

Detecting genomic regions associated with a disease using variability functions and Adjusted Rand Index

BACKGROUND

The identification of functional regions contained in a given multiple sequence alignment constitutes one of the major challenges of comparative genomics. Several studies have focused on the identification of conserved regions and motifs. However, most of existing methods ignore the relationship between the functional genomic regions and the external evidence associated with the considered group of species (e.g., carcinogenicity of Human Papilloma Virus). In the past, we have proposed a method that takes into account the prior knowledge on an external evidence (e.g., carcinogenicity or invasivity of the considered organisms) and identifies genomic regions related to a specific disease.

RESULTS AND CONCLUSION

We present a new algorithm for detecting genomic regions that may be associated with a disease. Two new variability functions and a bipartition optimization procedure are described. We validate and weigh our results using the Adjusted Rand Index (ARI), and thus assess to what extent the selected regions are related to carcinogenicity, invasivity, or any other species classification, given as input. The predictive power of different hit region detection functions was assessed on synthetic and real data. Our simulation results suggest that there is no a single function that provides the best results in all practical situations (e.g., monophyletic or polyphyletic evolution, and positive or negative selection), and that at least three different functions might be useful. The proposed hit region identification functions that do not benefit from the prior knowledge (i.e., carcinogenicity or invasivity of the involved organisms) can provide equivalent results than the existing functions that take advantage of such a prior knowledge. Using the new algorithm, we examined the Neisseria meningitidis FrpB gene product for invasivity and immunologic activity, and human papilloma virus (HPV) E6 oncoprotein for carcinogenicity, and confirmed some well-known molecular features, including surface exposed loops for N. meningitidis and PDZ domain for HPV.

Cheating, trade-offs and the evolution of aggressiveness in a natural pathogen population

The evolutionary dynamics of pathogens are critically important for disease outcomes, prevalence and emergence. In this study we investigate ecological conditions that may promote the long-term maintenance of virulence polymorphisms in pathogen populations. Recent theory predicts that evolution towards increased virulence can be reversed if less-aggressive social 'cheats' exploit more aggressive 'cooperator' pathogens. However, there is no evidence that social exploitation operates within natural pathogen populations. We show that for the bacterium Pseudomonas syringae, major polymorphisms for pathogenicity are maintained at unexpectedly high frequencies in populations infecting the host Arabidopsis thaliana. Experiments reveal that less-aggressive strains substantially increase their growth potential in mixed infections and have a fitness advantage in non-host environments. These results suggest that niche differentiation can contribute to the maintenance of virulence polymorphisms, and that both within-host and between-host growth rates modulate cheating and cooperation in P. syringae populations.

Towards an accurate identification of mosaic genes and partial horizontal gene transfers

Many bacteria and viruses adapt to varying environmental conditions through the acquisition of mosaic genes. A mosaic gene is composed of alternating sequence polymorphisms either belonging to the host original allele or derived from the integrated donor DNA. Often, the integrated sequence contains a selectable genetic marker (e.g. marker allowing for antibiotic resistance). An effective identification of mosaic genes and detection of corresponding partial horizontal gene transfers (HGTs) are among the most important challenges posed by evolutionary biology. We developed a method for detecting partial HGT events and related intragenic recombination giving rise to the formation of mosaic genes. A bootstrap procedure incorporated in our method is used to assess the support of each predicted partial gene transfer. The proposed method can be also applied to confirm or discard complete (i.e. traditional) horizontal gene transfers detected by any HGT inferring method. While working on a full-genome scale, the new method can be used to assess the level of mosaicism in the considered genomes as well as the rates of complete and partial HGT underlying their evolution.

The Vein Patterning 1 (VEP1) gene family laterally spread through an ecological network

Lateral gene transfer (LGT) is a major evolutionary mechanism in prokaryotes. Knowledge about LGT— particularly, multicellular— eukaryotes has only recently started to accumulate. A widespread assumption sees the gene as the unit of LGT, largely because little is yet known about how LGT chances are affected by structural/functional features at the subgenic level. Here we trace the evolutionary trajectory of VEin Patterning 1, a novel gene family known to be essential for plant development and defense. At the subgenic level VEP1 encodes a dinucleotide-binding Rossmann-fold domain, in common with members of the short-chain dehydrogenase/reductase (SDR) protein family. We found: i) VEP1 likely originated in an aerobic, mesophilic and chemoorganotrophic α-proteobacterium, and was laterally propagated through nets of ecological interactions, including multiple LGTs between phylogenetically distant green plant/fungi-associated bacteria, and five independent LGTs to eukaryotes. Of these latest five transfers, three are ancient LGTs, implicating an ancestral fungus, the last common ancestor of land plants and an ancestral trebouxiophyte green alga, and two are recent LGTs to modern embryophytes. ii) VEP1's rampant LGT behavior was enabled by the robustness and broad utility of the dinucleotide-binding Rossmann-fold, which provided a platform for the evolution of two unprecedented departures from the canonical SDR catalytic triad. iii) The fate of VEP1 in eukaryotes has been different in different lineages, being ubiquitous and highly conserved in land plants, whereas fungi underwent multiple losses. And iv) VEP1-harboring bacteria include non-phytopathogenic and phytopathogenic symbionts which are non-randomly distributed with respect to the type of harbored VEP1 gene. Our findings suggest that VEP1 may have been instrumental for the evolutionary transition of green plants to land, and point to a LGT-mediated ‘Trojan Horse’ mechanism for the evolution of bacterial pathogenesis against plants. VEP1 may serve as tool for revealing microbial interactions in plant/fungi-associated environments.

In silico evidence for the horizontal transfer of gsiB, a σ(B)-regulated gene in gram-positive bacteria, to lactic acid bacteria

gsiB, coding for glucose starvation-inducible protein B, is a characteristic member of the σ(Β) stress regulon of Bacillus subtilis and several other Gram-positive bacteria. Here we provide in silico evidence for the horizontal transfer of gsiB in lactic acid bacteria that are devoid of the σ(Β) factor.