Reconstructible Phylogenetic Networks: Do Not Distinguish the Indistinguishable

Phylogenetic networks represent the evolution of organisms that have undergone reticulate events, such as recombination, hybrid speciation or lateral gene transfer. An important way to interpret a phylogenetic network is in terms of the trees it displays, which represent all the possible histories of the characters carried by the organisms in the network. Interestingly, however, different networks may display exactly the same set of trees, an observation that poses a problem for network reconstruction: from the perspective of many inference methods such networks are indistinguishable. This is true for all methods that evaluate a phylogenetic network solely on the basis of how well the displayed trees fit the available data, including all methods based on input data consisting of clades, triples, quartets, or trees with any number of taxa, and also sequence-based approaches such as popular formalisations of maximum parsimony and maximum likelihood for networks. This identifiability problem is partially solved by accounting for branch lengths, although this merely reduces the frequency of the problem. Here we propose that network inference methods should only attempt to reconstruct what they can uniquely identify. To this end, we introduce a novel definition of what constitutes a uniquely reconstructible network. For any given set of indistinguishable networks, we define a canonical network that, under mild assumptions, is unique and thus representative of the entire set. Given data that underwent reticulate evolution, only the canonical form of the underlying phylogenetic network can be uniquely reconstructed. While on the methodological side this will imply a drastic reduction of the solution space in network inference, for the study of reticulate evolution this is a fundamental limitation that will require an important change of perspective when interpreting phylogenetic networks.     

Phylogenomic networks

Phylogenomics is aimed at studying functional and evolutionary aspects of genome biology using phylogenetic analysis of whole genomes. Current approaches to genome phylogenies are commonly founded in terms of phylogenetic trees. However, several evolutionary processes are non tree-like in nature, including recombination and lateral gene transfer (LGT). Phylogenomic networks are a special type of phylogenetic network reconstructed from fully sequenced genomes. The network model, comprising genomes connected by pairwise evolutionary relations, enables the reconstruction of both vertical and LGT events. Modeling genome evolution in the form of a network enables the use of an extensive toolbox developed for network research. The structural properties of phylogenomic networks open up fundamentally new insights into genome evolution.     

Quantifying the Extent of Lateral Gene Transfer Required to Avert a ‘Genome of Eden’

The complex pattern of presence and absence of many genes across different species provides tantalising clues as to how genes evolved through the processes of gene genesis, gene loss, and lateral gene transfer (LGT). The extent of LGT, particularly in prokaryotes, and its implications for creating a ‘network of life’ rather than a ‘tree of life’ is controversial. In this paper, we formally model the problem of quantifying LGT, and provide exact mathematical bounds, and new computational results. In particular, we investigate the computational complexity of quantifying the extent of LGT under the simple models of gene genesis, loss, and transfer on which a recent heuristic analysis of biological data relied. Our approach takes advantage of a relationship between LGT optimization and graph-theoretical concepts such as tree width and network flow.     

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

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

Gene gain and gene loss in streptococcus: is it driven by habitat?

Bacterial genomes can evolve either by gene gain, gene loss, mutating existing genes, and/or by duplication of existing genes. Recent studies have clearly demonstrated that the acquisition of new genes by lateral gene transfer (LGT) is a predominant force in bacterial evolution. To better understand the significance of LGT, we employed a comparative genomics approach to model species-specific and intraspecies gene insertions/deletions (ins/del among 12 sequenced streptococcal genomes using a maximum likelihood method. This study indicates that the rate of gene ins/del is higher on the external branches and varies dramatically for each species. We have analyzed here some of the experimentally characterized species-specific genes that have been acquired by LGT and conclude that at least a portion of these genes have a role in adaptation.     

The role of lateral gene transfer in the evolution of isoprenoid biosynthesis pathways

Lateral gene transfer (LGT) is a major force in microbial genome evolution. Here, we present an overview of lateral transfers affecting genes involved in isopentenyl diphosphate (IPP) synthesis. Two alternative metabolic pathways can synthesize this universal precursor of isoprenoids, the 1-deoxy-D-xylulose 5-phosphate (DOXP) pathway and the mevalonate (MVA) pathway. We have surveyed recent genomic data and the biochemical literature to determine the distribution of the genes composing these pathways within the bacterial domain. The scattered distribution observed is incompatible with a simple scheme of vertical transmission. LGT (among and between bacteria, archaea and eukaryotes) more parsimoniously explains many features of this pattern. This alternative scenario is supported by phylogenetic analyses, which unambiguously confirm several cases of lateral transfer. Available biochemical data allow the formulation of hypotheses about selective pressures favouring transfer. The phylogenetic diversity of the organisms involved and the range of possible causes and effects of these transfer events make the IPP biosynthetic pathways an ideal system for studying the evolutionary role of LGT.     

Trends and barriers to lateral gene transfer in prokaryotes

Gene acquisition by lateral gene transfer (LGT) is an important mechanism for natural variation among prokaryotes. Laboratory experiments show that protein-coding genes can be laterally transferred extremely fast among microbial cells, inherited to most of their descendants, and adapt to a new regulatory regime within a short time. Recent advance in the phylogenetic analysis of microbial genomes using networks approach reveals a substantial impact of LGT during microbial genome evolution. Phylogenomic networks of LGT among prokaryotes reconstructed from completely sequenced genomes uncover barriers to LGT in multiple levels. Here we discuss the kinds of barriers to gene acquisition in nature including physical barriers for gene transfer between cells, genomic barriers for the integration of acquired DNA, and functional barriers for the acquisition of new genes.     

The Frequency of Eubacterium-to-Eukaryote Lateral Gene Transfers Shows Significant Cross-Taxa Variation Within Amoebozoa

Single-celled bacterivorous eukaryotes offer excellent test cases for evaluation of the frequency of prey-to-predator lateral gene transfer (LGT). Here we use analysis of expressed sequence tag (EST) data sets to quantify the extent of LGT from eubacteria to two amoebae, Acanthamoeba castellanii and Hartmannella vermiformis. Stringent screening for LGT proceeded in several steps intended to enrich for authentic events while at the same time minimizing the incidence of false positives due to factors such as limitations in database coverage and ancient paralogy. The results were compared with data obtained when the same methodology was applied to EST libraries from a number of other eukaryotic taxa. Significant differences in the extent of apparent eubacterium-to-eukaryote LGT were found between taxa. Our results indicate that there may be substantial inter-taxon variation in the number of LGT events that become fixed even between amoebozoan species that have similar feeding modalities. Electronic Supplementary Material Electronic Supplementary material is available for this article at and accessible for authorised users. [Reviewing Editor: Martin Kreitman]     

Archaeal phylogeny based on ribosomal proteins

Until recently, phylogenetic analyses of Archaea have mainly been based on ribosomal RNA (rRNA) sequence comparisons, leading to the distinction of the two major archaeal phyla: the Euryarchaeota and the Crenarchaeota. Here, thanks to the recent sequencing of several archaeal genomes, we have constructed a phylogeny based on the fusion of the sequences of the 53 ribosomal proteins present in most of the archaeal species. This phylogeny was remarkably congruent with the rRNA phylogeny, suggesting that both reflected the actual phylogeny of the domain Archaea even if some nodes remained unresolved. In both cases, the branches leading to hyperthermophilic species were short, suggesting that the evolutionary rate of their genes has been slowed down by structural constraints related to environmental adaptation. In addition, to estimate the impact of lateral gene transfer (LGT) on our tree reconstruction, we used a new method that revealed that 8 genes out of the 53 ribosomal proteins used in our study were likely affected by LGT. This strongly suggested that a core of 45 nontransferred ribosomal protein genes existed in Archaea that can be tentatively used to infer the phylogeny of this domain. Interestingly, the tree obtained using only the eight ribosomal proteins likely affected by LGT was not very different from the consensus tree, indicating that LGT mainly brought random phylogenetic noise. The major difference involves organisms living in similar environments, suggesting that LGTs are mainly directed by the physical proximity of the organisms rather than by their phylogenetic proximity.     

Lateral transfer of genes and gene fragments in Staphylococcus extends beyond mobile elements

The widespread presence of antibiotic resistance and virulence among Staphylococcus isolates has been attributed in part to lateral genetic transfer (LGT), but little is known about the broader extent of LGT within this genus. Here we report the first systematic study of the modularity of genetic transfer among 13 Staphylococcus genomes covering four distinct named species. Using a topology-based phylogenetic approach, we found, among 1,354 sets of homologous genes examined, strong evidence of LGT in 368 (27.1%) gene sets, and weaker evidence in another 259 (19.1%). Within-gene and whole-gene transfer contribute almost equally to the topological discordance of these gene sets against a reference phylogeny. Comparing genetic transfer in single-copy and in multicopy gene sets, we observed a higher frequency of LGT in the latter, and a substantial functional bias in cases of whole-gene transfer (little such bias was observed in cases of fragmentary genetic transfer). We found evidence that lateral transfer, particularly of entire genes, impacts not only functions related to antibiotic, drug, and heavy-metal resistance, as well as membrane transport, but also core informational and metabolic functions not associated with mobile elements. Although patterns of sequence similarity support the cohesion of recognized species, LGT within S. aureus appears frequently to disrupt clonal complexes. Our results demonstrate that LGT and gene duplication play important parts in functional innovation in staphylococcal genomes.     

Phylogenomics of T4 cyanophages: lateral gene transfer in the 'core' and origins of host genes

The last two decades have revealed that phages (viruses that infect bacteria) are abundant and play fundamental roles in the Earth System, with the T4-like myoviruses (herein T4-like phages) emerging as a dominant 'signal' in wild populations. Here we examine 27 T4-like phage genomes, with a focus on 17 that infect ocean picocyanobacteria (cyanophages), to evaluate lateral gene transfer (LGT) in this group. First, we establish a reference tree by evaluating concatenated core gene supertrees and whole genome gene content trees. Next, we evaluate what fraction of these 'core genes' shared by all 17 cyanophages appear prone to LGT. Most (47 out of 57 core genes) were vertically transferred as inferred from tree tests and genomic synteny. Of those 10 core genes that failed the tree tests, the bulk (8 of 10) remain syntenic in the genomes with only a few (3 of the 10) having identifiable signatures of mobile elements. Notably, only one of these 10 is shared not only by the 17 cyanophages, but also by all 27 T4-like phages (thymidylate synthase); its evolutionary history suggests cyanophages may be the origin of these genes to Prochlorococcus. Next, we examined intragenic recombination among the core genes and found that it did occur, even among these core genes, but that the rate was significantly higher between closely related phages, perhaps reducing any detectable LGT signal and leading to taxon cohesion. Finally, among 18 auxiliary metabolic genes (AMGs, a.k.a. 'host' genes), we found that half originated from their immediate hosts, in some cases multiple times (e.g. psbA, psbD, pstS), while the remaining have less clear evolutionary origins ranging from cyanobacteria (4 genes) or microbes (5 genes), with particular diversity among viral TalC and Hsp20 sequences. Together, these findings highlight the patterns and limits of vertical evolution, as well as the ecological and evolutionary roles of LGT in shaping T4-like phage genomes.     

Harvesting evolutionary signals in a forest of prokaryotic gene trees

Phylogenomic studies produce increasingly large phylogenetic forests of trees with patchy taxonomical sampling. Typically, prokaryotic data generate thousands of gene trees of all sizes that are difficult, if not impossible, to root. Their topologies do not match the genealogy of lineages, as they are influenced not only by duplication, losses, and vertical descent but also by lateral gene transfer (LGT) and recombination. Because this complexity in part reflects the diversity of evolutionary processes, the study of phylogenetic forests is thus a great opportunity to improve our understanding of prokaryotic evolution. Here, we show how the rich evolutionary content of such novel phylogenetic objects can be exploited through the development of new approaches designed specifically for extracting the multiple evolutionary signals present in the forest of life, that is, by slicing up trees into remarkable bits and pieces: clans, slices, and clips. We harvested a forest of 6,901 unrooted gene trees comprising up to 100 prokaryotic genomes (41 archaea and 59 bacteria) to search for evolutionary events that a species tree would not account for. We identified 1) trees and partitions of trees that reflected the lifestyle of organisms rather than their taxonomy, 2) candidate lifestyle-specific genetic modules, used by distinct unrelated organisms to adapt to the same environment, 3) gene families, nonrandomly distributed in the functional space, that were frequently exchanged between archaea and bacteria, sometimes without major changes in their sequences. Finally, 4) we reconstructed polarized networks of genetic partnerships between archaea and bacteria to describe some of the rules affecting LGT between these two Domains.     

The complexity of comparing reaction systems

MOTIVATION: As more genomic data becomes available there is increased attention on understanding the mechanisms encoded in the genome. New XML dialects like CellML and Systems Biology Markup Language (SBML) are being developed to describe biological networks of all types. In the absence of detailed kinetic information for these networks, stoichiometric data is an especially valuable source of information. Network databases are the next logical step beyond storing purely genomic information. Just as comparison of entries in genomic databases has been a vital algorithmic problem through the course of the sequencing project, comparison of networks in network databases will be a crucial problem as we seek to integrate higher-order network knowledge. RESULTS: We show that comparing the stoichiometric structure of two reactions systems is equivalent to the graph isomorphism problem. This is encouraging because graph isomorphism is, in practice, a tractable problem using heuristics. The analogous problem of searching for a subsystem of a reaction system is NP-complete. We also discuss heuristic issues in implementations for practical comparison of stoichiometric matrices.     

GraphCrunch 2: Software tool for network modeling,alignment and clustering

Background  

Recent advancements in experimental biotechnology have produced large amounts of protein-protein interaction (PPI) data. The topology of PPI networks is believed to have a strong link to their function. Hence, the abundance of PPI data for many organisms stimulates the development of computational techniques for the modeling, comparison, alignment, and clustering of networks. In addition, finding representative models for PPI networks will improve our understanding of the cell just as a model of gravity has helped us understand planetary motion. To decide if a model is representative, we need quantitative comparisons of model networks to real ones. However, exact network comparison is computationally intractable and therefore several heuristics have been used instead. Some of these heuristics are easily computable "network properties," such as the degree distribution, or the clustering coefficient. An important special case of network comparison is the network alignment problem. Analogous to sequence alignment, this problem asks to find the "best" mapping between regions in two networks. It is expected that network alignment might have as strong an impact on our understanding of biology as sequence alignment has had. Topology-based clustering of nodes in PPI networks is another example of an important network analysis problem that can uncover relationships between interaction patterns and phenotype.     

A Review of Bacteria-Animal Lateral Gene Transfer May Inform Our Understanding of Diseases like Cancer

Lateral gene transfer (LGT) from bacteria to animals occurs more frequently than was appreciated prior to the advent of genome sequencing. In 2007, LGT from bacterial Wolbachia endosymbionts was detected in ∼33% of the sequenced arthropod genomes using a bioinformatic approach. Today, Wolbachia/host LGT is thought to be widespread and many other cases of bacteria-animal LGT have been described. In insects, LGT may be more frequently associated with endosymbionts that colonize germ cells and germ stem cells, like Wolbachia endosymbionts. We speculate that LGT may occur from bacteria to a wide variety of eukaryotes, but only becomes vertically inherited when it occurs in germ cells. As such, LGT may happen routinely in somatic cells but never become inherited or fixed in the population. Lack of inheritance of such mutations greatly decreases our ability to detect them. In this review, we propose that such noninherited bacterial DNA integration into chromosomes in human somatic cells could induce mutations leading to cancer or autoimmune diseases in a manner analogous to mobile elements and viral integrations.     

Assessing the effects of a sequestered germline on interdomain lateral gene transfer in Metazoa

A sequestered germline in Metazoa has been argued to be an obstacle to lateral gene transfer (LGT), though few studies have specifically assessed this claim. Here, we test the hypothesis that the origin of a sequestered germline reduced LGT events in Bilateria (i.e., triploblast lineages) as compared to early‐diverging Metazoa (i.e., Ctenophora, Cnidaria, Porifera, and Placozoa). We analyze single‐gene phylogenies generated with over 900 species sampled from among Bacteria, Archaea, and Eukaryota to identify well‐supported interdomain LGTs. We focus on ancient interdomain LGT (i.e., those between prokaryotes and multiple lineages of Metazoa) as systematic errors in single‐gene tree reconstruction create uncertainties for interpreting eukaryote‐to‐eukaryote transfer. The breadth of the sampled Metazoa enables us to estimate the timing of LGTs, and to examine the pattern before versus after the evolution of a sequestered germline. We identified 58 LGTs found only in Metazoa and prokaryotes (i.e., bacteria and/or archaea), and seven genes transferred from prokaryotes into Metazoa plus one other eukaryotic clade. Our analyses indicate that more interdomain transfers occurred before the development of a sequestered germline, consistent with the hypothesis that this feature is an obstacle to LGT.     

Defining the Core of Nontransferable Prokaryotic Genes: The Euryarchaeal Core

If lateral gene transfer (LGT) has affected all genes over the course of prokaryotic evolution, reconstruction of organismal phylogeny is compromised. However, if a core of genes is immune to transfer, then the evolutionary history of that core might be our most reliable guide to the evolution of organisms. Such a core should be preferentially included in the subset of genes shared by all organisms, but where universally conserved genes have been analyzed, there is too little phylogenetic signal to allow determination of whether or not they indeed have the same history (Hansmann and Martin 2000; Teichmann and Mitchison 1999). Here we look at a more restricted set, 521 homologous genes (COGs) simultaneously present in four sequenced euryarchaeal genomes. Although there is overall little robust phylogenetic signal in this data set, there is, among well-supported trees, strong representation of all three possible four-taxon topologies. ``Informational' genes seem no less subject to LGT than are ``operational genes,' within the euryarchaeotes. We conclude that (i) even in this collection of conserved genes there has been extensive LGT (orthologous gene replacement) and (ii) the notion that there is a core of nontransferable genes (the ``core hypothesis') has not been proven and may be unprovable. Received: 7 November 2000 / Accepted: 20 February 2001     

Cohesion Group Approach for Evolutionary Analysis of Aspartokinase,an Enzyme That Feeds a Branched Network of Many Biochemical Pathways

Summary: Aspartokinase (Ask) exists within a variable network that supports the synthesis of 9 amino acids and a number of other important metabolites. Lysine, isoleucine, aromatic amino acids, and dipicolinate may arise from the ASK network or from alternative pathways. Ask proteins were subjected to cohesion group analysis, a methodology that sorts a given protein assemblage into groups in which evolutionary continuity is assured. Two subhomology divisions, ASK_α and ASK_β, have been recognized. The ASK_α subhomology division is the most ancient, being widely distributed throughout the Archaea and Eukarya and in some Bacteria. Within an indel region of about 75 amino acids near the N terminus, ASK_β sequences differ from ASK_α sequences by the possession of a proposed ancient deletion. ASK_β sequences are present in most Bacteria and usually exhibit an in-frame internal translational start site that can generate a small Ask subunit that is identical to the C-terminal portion of the larger subunit of a heterodimeric unit. Particularly novel are ask genes embedded in gene contexts that imply specialization for ectoine (osmotic agent) or aromatic amino acids. The cohesion group approach is well suited for the easy recognition of relatively recent lateral gene transfer (LGT) events, and many examples of these are described. Given the current density of genome representation for Proteobacteria, it is possible to reconstruct more ancient landmark LGT events. Thus, a plausible scenario in which the three well-studied and iconic Ask homologs of Escherichia coli are not within the vertical genealogy of Gammaproteobacteria, but rather originated via LGT from a Bacteroidetes donor, is supported.     

Characterization of an Ancient Lepidopteran Lateral Gene Transfer

Bacteria to eukaryote lateral gene transfers (LGT) are an important potential source of material for the evolution of novel genetic traits. The explosion in the number of newly sequenced genomes provides opportunities to identify and characterize examples of these lateral gene transfer events, and to assess their role in the evolution of new genes. In this paper, we describe an ancient lepidopteran LGT of a glycosyl hydrolase family 31 gene (GH31) from an Enterococcus bacteria. PCR amplification between the LGT and a flanking insect gene confirmed that the GH31 was integrated into the Bombyx mori genome and was not a result of an assembly error. Database searches in combination with degenerate PCR on a panel of 7 lepidopteran families confirmed that the GH31 LGT event occurred deep within the Order approximately 65–145 million years ago. The most basal species in which the LGT was found is Plutella xylostella (superfamily: Yponomeutoidea). Array data from Bombyx mori shows that GH31 is expressed, and low dN/dS ratios indicates the LGT coding sequence is under strong stabilizing selection. These findings provide further support for the proposition that bacterial LGTs are relatively common in insects and likely to be an underappreciated source of adaptive genetic material.