Ten Years of Collaborative Progress in the Quest for Orthologs.

Accurate determination of the evolutionary relationships between genes is a foundational challenge in biology. Homology-evolutionary relatedness-is in many cases readily determined based on sequence similarity analysis. By contrast, whether or not two genes directly descended from a common ancestor by a speciation event (orthologs) or duplication event (paralogs) is more challenging, yet provides critical information on the history of a gene. Since 2009, this task has been the focus of the Quest for Orthologs (QFO) Consortium. The sixth QFO meeting took place in Okazaki, Japan in conjunction with the 67th National Institute for Basic Biology conference. Here, we report recent advances, applications, and oncoming challenges that were discussed during the conference. Steady progress has been made toward standardization and scalability of new and existing tools. A feature of the conference was the presentation of a panel of accessible tools for phylogenetic profiling and several developments to bring orthology beyond the gene unit-from domains to networks. This meeting brought into light several challenges to come: leveraging orthology computations to get the most of the incoming avalanche of genomic data, integrating orthology from domain to biological network levels, building better gene models, and adapting orthology approaches to the broad evolutionary and genomic diversity recognized in different forms of life and viruses.

Indirect identification of horizontal gene transfer.

Several implicit methods to infer horizontal gene transfer (HGT) focus on pairs of genes that have diverged only after the divergence of the two species in which the genes reside. This situation defines the edge set of a graph, the later-divergence-time (LDT) graph, whose vertices correspond to genes colored by their species. We investigate these graphs in the setting of relaxed scenarios, i.e., evolutionary scenarios that encompass all commonly used variants of duplication-transfer-loss scenarios in the literature. We characterize LDT graphs as a subclass of properly vertex-colored cographs, and provide a polynomial-time recognition algorithm as well as an algorithm to construct a relaxed scenario that explains a given LDT. An edge in an LDT graph implies that the two corresponding genes are separated by at least one HGT event. The converse is not true, however. We show that the complete xenology relation is described by an rs-Fitch graph, i.e., a complete multipartite graph satisfying constraints on the vertex coloring. This class of vertex-colored graphs is also recognizable in polynomial time. We finally address the question "how much information about all HGT events is contained in LDT graphs" with the help of simulations of evolutionary scenarios with a wide range of duplication, loss, and HGT events. In particular, we show that a simple greedy graph editing scheme can be used to efficiently detect HGT events that are implicitly contained in LDT graphs.

Alternative characterizations of Fitch's xenology relation.

Horizontal gene transfer (HGT) is an important factor for the evolution of prokaryotes as well as eukaryotes. According to Walter M. Fitch, two genes are xenologs if they are separated by at least one HGT. This concept is formalized through Fitch relations, which are defined as binary relations that comprise all pairs (x, y) of genes x and y for which y has been horizontally transferred at least once since it diverged from the last common ancestor of x and y. This definition, in particular, preserves the directional character of the transfer. Fitch relations are characterized by a small set of forbidden induced subgraphs on three vertices and can be recognized in linear time. The mathematical characterization of Fitch relations is crucial to understand whether putative xenology relations are at least to some extent "biologically feasible". In this contribution, we provide two novel characterizations of Fitch relations. In particular, these results allow us directly to reconstruct gene trees (together with the location of the horizontal transfer events) that explain the underlying Fitch relation. As a biological side result, we can conclude that the phylogenetic signal to infer these gene trees is entirely contained in those pairs of genes x and y for which no directional transfer has been taken place in the common history of y and the last common ancestor of x and y. In other words, non-HGT events provide the essential information about the gene trees. In addition, we utilize the new characterizations to present an alternative, short and elegant proof of the characterization theorem established by Geiß et al. (J Math Bio 77(5), 2018).

Reconstructing gene trees from Fitch's xenology relation.

Two genes are xenologs in the sense of Fitch if they are separated by at least one horizontal gene transfer event. Horizonal gene transfer is asymmetric in the sense that the transferred copy is distinguished from the one that remains within the ancestral lineage. Hence xenology is more precisely thought of as a non-symmetric relation: y is xenologous to x if y has been horizontally transferred at least once since it diverged from the least common ancestor of x and y. We show that xenology relations are characterized by a small set of forbidden induced subgraphs on three vertices. Furthermore, each xenology relation can be derived from a unique least-resolved edge-labeled phylogenetic tree. We provide a linear-time algorithm for the recognition of xenology relations and for the construction of its least-resolved edge-labeled phylogenetic tree. The fact that being a xenology relation is a heritable graph property, finally has far-reaching consequences on approximation problems associated with xenology relations.

Plant expansins in bacteria and fungi: evolution by horizontal gene transfer and independent domain fusion.

Horizontal gene transfer (HGT) has been described as a common mechanism of transferring genetic material between prokaryotes, whereas genetic transfers from eukaryotes to prokaryotes have been rarely documented. Here we report a rare case of HGT in which plant expansin genes that code for plant cell-wall loosening proteins were transferred from plants to bacteria, fungi, and amoebozoa. In several cases, the species in which the expansin gene was found is either in intimate association with plants or is a known plant pathogen. Our analyses suggest that at least two independent genetic transfers occurred from plants to bacteria and fungi. These events were followed by multiple HGT events within bacteria and fungi. We have also observed that in bacteria expansin genes have been independently fused to DNA fragments that code for an endoglucanase domain or for a carbohydrate binding module, pointing to functional convergence at the molecular level. Furthermore, the functional similarities between microbial expansins and their plant xenologs suggest that these proteins mediate microbial-plant interactions by altering the plant cell wall and therefore may provide adaptive advantages to these species. The evolution of these nonplant expansins represents a unique case in which bacteria and fungi have found innovative and adaptive ways to interact with and infect plants by acquiring genes from their host. This evolutionary paradigm suggests that despite their low frequency such HGT events may have significantly contributed to the evolution of prokaryotic and eukaryotic species.

Relative timing information and orthology in evolutionary scenarios.

BACKGROUND: Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree T to vertices and edges of a species tree S. The relative timing of the last common ancestors of two extant genes (leaves of T) and the last common ancestors of the two species (leaves of S) in which they reside is indicative of horizontal gene transfers (HGT) and ancient duplications. Orthologous gene pairs, on the other hand, require that their last common ancestors coincides with a corresponding speciation event. The relative timing information of gene and species divergences is captured by three colored graphs that have the extant genes as vertices and the species in which the genes are found as vertex colors: the equal-divergence-time (EDT) graph, the later-divergence-time (LDT) graph and the prior-divergence-time (PDT) graph, which together form an edge partition of the complete graph. RESULTS: Here we give a complete characterization in terms of informative and forbidden triples that can be read off the three graphs and provide a polynomial time algorithm for constructing an evolutionary scenario that explains the graphs, provided such a scenario exists. While both LDT and PDT graphs are cographs, this is not true for the EDT graph in general. We show that every EDT graph is perfect. While the information about LDT and PDT graphs is necessary to recognize EDT graphs in polynomial-time for general scenarios, this extra information can be dropped in the HGT-free case. However, recognition of EDT graphs without knowledge of putative LDT and PDT graphs is NP-complete for general scenarios. In contrast, PDT graphs can be recognized in polynomial-time. We finally connect the EDT graph to the alternative definitions of orthology that have been proposed for scenarios with horizontal gene transfer. With one exception, the corresponding graphs are shown to be colored cographs.

Inferring Horizontal Gene Transfer with DarkHorse, Phylomizer, and ETE Toolkits.

In this chapter, we describe how to use DarkHorse2.0 to search for xenologs in the genome of the cyanobacterium Synechococcus elongatus PCC 7942. DarkHorse is an implicit phylogenetic method that uses BLAST searches to identify proteins having close homologs of unexpected taxonomic affiliation. Once a set of putative xenologs are identified, Phylomizer is used to reconstruct phylogenetic trees. Phylomizer reproduces all the necessary steps to perform a basic phylogenetic analysis. The combined use of DarkHorse and Phylomizer allows the identification of genes incorporated into a given genome by HGT.