Abstract Sexual reproduction consists of genome reduction by meiosis and subsequent gamete fusion. Presence of meiotic genes in prokaryotes suggests that DNA repair mechanisms evolved toward meiotic recombination; however, fusogenic proteins resembling those found in eukaryotes were not identified in prokaryotes. Here, we identify archaeal proteins that are homologs of fusexins, a superfamily of fusogens that mediate eukaryotic gamete and somatic cell fusion, as well as virus entry. The crystal structure of a trimeric archaeal Fusexin1 reveals novel features such as a six-helix bundle and an additional globular domain. Ectopically expressed Fusexin1 can fuse mammalian cells, and this process involves the additional domain and a conserved fusion loop. Archaeal fusexin genes exist within integrated mobile elements, potentially linking ancient archaeal gene exchanges and eukaryotic sex. One-Sentence Summary Cell membrane fusion proteins of viruses and eukaryotes are also present in archaea.

Abstract The surge in genome data, with ongoing efforts aiming to sequence 1.5M eukaryotes in a decade, could revolutionise genomics, revealing the origins, evolution, and genetic innovations of biological processes. Yet, traditional genomics methods scale poorly with such large datasets. Addressing this, “FastOMA” provides linear scalability, enabling the processing of thousands of eukaryotic genomes within a day. FastOMA maintains the high accuracy and resolution of the well-established OMA approach in benchmarks. FastOMA is available at https://github.com/DessimozLab/FastOMA/ .

Abstract Protein post-translational modifications (PTMs) add an enormous amount of sophistication to biological systems but their origins are largely unexplored. Citrullination, a key regulatory mechanism in human physiology and pathophysiology, is particularly enigmatic in an evolutionary context. The citrullinating enzymes peptidylarginine deiminases (PADIs) are ubiquitous across vertebrates but absent from yeast, worms and flies. Here, we map the surprising evolutionary trajectory of PADIs into the animal lineage. We present strong phylogenetic support for a clade encompassing animal and cyanobacterial PADIs that excludes fungal and other bacterial homologues. The animal and cyanobacterial PADIs share unique, functionally relevant synapomorphies that are absent from all other homologues. Molecular clock calculations and sequence divergence analyses using the fossil record estimate the last common ancestor of the cyanobacterial and animal PADIs to be approximately 1 billion years old, far younger than the 3.35-4.52 billion years known to separate bacterial and eukaryotic lineages. Under an assumption of vertical descent, PADI sequence change is anachronistically slow during this evolutionary time frame, even when compared to mitochondrial proteins, products of likely endosymbiont gene transfer and some of the most highly conserved proteins in life. The consilience of evidence indicates that PADIs were introduced from cyanobacteria into animals by horizontal gene transfer (HGT). The ancestral cyanobacterial protein is enzymatically active and can citrullinate eukaryotic proteins, suggesting that the PADI HGT event introduced a new catalytic capability into the regulatory repertoire of animals. This study reveals the unusual evolution of a pleiotropic protein modification with clear relevance in human physiology and disease.

Abstract Motivation Genes which are involved in the same biological processes tend to co-evolve. Thus, metabolic pathways, protein complexes, and other kinds of protein-protein interactions can be inferred by looking for correlated patterns of gene retention and loss across the tree of life—a technique called phylogenetic profiling. Recent methodological developments on phylogenetic profiling have focused on scalability improvements to take advantage of the rapidly accumulating genomic data. However, state-of-the-art methods assume that the correlation resulting from co-evolving proteins is uniform across all species considered. This is reasonable for interactions already present at the root of the species considered, but less so for ones that emerge in more recent lineages. To address this challenge and take advantage of recent developments in deep learning methods, we introduce a phylogenetic profiling method which processes large gene co-phylogenies using neural networks. Results We show that post-processing conventional phylogenetic profiles using deep neural networks can improve predictions, but requires onerous training on specific phylogenies. Overcoming this limitation by taking the topology of the species tree as an input, Graph Neural Networks are shown to outperform all other methods when interaction detection is not centered on just one species of interest, while also predicting when interactions appeared and in which taxa they are present. Conclusion Graph Neural Networks constitute a promising new approach for phylogenetic profiling. Our work is a first foray into “dynamic phylogenetic profiling”—the reconstruction of pairwise protein interaction across time. Availability All of the code is available on the project Git at https://github.com/DessimozLab/HogProf/tree/master/pyprofiler/notebooks/Graphnet . Datasets used are hosted at http://humap2.proteincomplexes.org/download and https://string-db.org/cgi/download . Contact dmoi@unil.ch

Phylogenetic profiling is a computational method to predict genes involved in the same biological process by identifying protein families which tend to be jointly lost or retained across the tree of life. Phylogenetic profiling has customarily been more widely used with prokaryotes than eukaryotes, because the method is thought to require many diverse genomes. There are now many eukaryotic genomes available, but these are considerably larger, and typical phylogenetic profiling methods require quadratic time or worse in the number of genes. We introduce a fast, scalable phylogenetic profiling approach entitled HogProf, which leverages hierarchical orthologous groups for the construction of large profiles and locality-sensitive hashing for efficient retrieval of similar profiles. We show that the approach outperforms Enhanced Phylogenetic Tree, a phylogeny-based method, and use the tool to reconstruct networks and query for interactors of the kinetochore complex as well as conserved proteins involved in sexual reproduction: Hap2, Spo11 and Gex1. HogProf enables large-scale phylogenetic profiling across the three domains of life, and will be useful to predict biological pathways among the hundreds of thousands of eukaryotic species that will become available in the coming few years. HogProf is available at https://github.com/DessimozLab/HogProf .

Cell-cell fusion is inherent to any form of sexual reproduction. Loss of HAPLESS 2/GENERATIVE CELL SPECIFIC 1 (HAP2/GCS1) proteins results in gamete fusion failure in different organisms but their exact role is unclear. Here we show that Arabidopsis HAP2/GCS1 expression in mammalian cells is sufficient to promote cell-cell fusion. Hemifusion and complete fusion depend on HAP2/GCS1 presence in both fusing cells. Furthermore, expression of HAP2 on the surface of pseudotyped vesicular stomatitis virus and on the target cells results in HAP2-dependent virus-cell fusion. This bilateral requirement can be bypassed by replacing the plant gene with C. elegans EFF-1 somatic cell fusogen in one of the fusing cells or the virus, indicating that HAP2/GCS1 and EFF-1 share a similar fusion mechanism. Structural modeling of the HAP2/GCS1 protein family predicts that they are homologous to EFF-1 and class II fusion proteins from enveloped viruses (e.g. dengue and Zika viruses). We name this superfamily FUSEXINS: FUSion proteins essential for sexual reproduction and EXoplasmic merger of plasma membranes. Thus, Fusexins unify the origin and evolution of sexual reproduction, enveloped virus entry into cells and somatic cell fusion.

Summary Many proteins exist in the so-called “twilight zone” of sequence alignment, where low pairwise sequence identity makes it difficult to determine homology and phylogeny 1, 2 . As protein tertiary structure is often more conserved 3 , recent advances in ab initio protein folding have made structure-based identification of putative homologs feasible 4–6 . However, structural screening and phylogenetics are in their infancy, particularly for twilight zone proteins. We present a pipeline for the identification and characterization of distant homologs, and apply it to 7-transmembrane domain ion channels (7TMICs), a protein group founded by insect Odorant and Gustatory receptors. Previous sequence and limited structure-based searches identified putatively-related proteins, mainly in other animals and plants 7–10 . However, very few 7TMICs have been identified in non-animal, non-plant taxa. Moreover, these proteins’ remarkable sequence dissimilarity made it uncertain if disparate 7TMIC types (Gr/Or, Grl, GRL, DUF3537, PHTF and GrlHz) are homologous or convergent, leaving their evolutionary history unresolved. Our pipeline identified thousands of new 7TMICs in archaea, bacteria and unicellular eukaryotes. Using graph-based analyses and protein language models to extract family-wide signatures, we demonstrate that 7TMICs have structure and sequence similarity, supporting homology. Through sequence and structure-based phylogenetics, we classify eukaryotic 7TMICs into two families (Class-A and Class-B), which are the result of a gene duplication predating the split(s) leading to Amorphea (animals, fungi and allies) and Diaphoretickes (plants and allies). Our work reveals 7TMICs as a cryptic superfamily with origins close to the evolution of cellular life. More generally, this study serves as a methodological proof of principle for the identification of extremely distant protein homologs.

Recent advances in AI-based protein structure modeling have yielded remarkable progress in predicting protein structures. Since structures are constrained by their biological function, their geometry tends to evolve more slowly than the underlying amino acids sequences. This feature of structures could in principle be used to reconstruct phylogenetic trees over longer evolutionary timescales than sequence-based approaches, but until now a reliable structure-based tree building method has been elusive. Here, we demonstrate that the use of structure-based phylogenies can outperform sequence-based ones not only for distantly related proteins but also, remarkably, for more closely related ones. This is achieved by inferring trees from protein structures using a local structural alphabet, an approach robust to conformational changes that confound traditional structural distance measures. As an illustration, we used structures to decipher the evolutionary diversification of a particularly challenging family: the fast-evolving RRNPPA quorum sensing receptors enabling gram-positive bacteria, plasmids and bacteriophages to communicate and coordinate key behaviors such as sporulation, virulence, antibiotic resistance, conjugation or phage lysis/lysogeny decision. The advent of high-accuracy structural phylogenetics enables myriad of applications across biology, such as uncovering deeper evolutionary relationships, elucidating unknown protein functions, or refining the design of bioengineered molecules.

Abstract The insect chemosensory repertoires of Gustatory Receptors (GRs) and Odorant Receptors (ORs) together represent one of the largest families of ligand-gated ion channels. Previous analyses have identified homologous “Gustatory Receptor-Like (GRL)” proteins across Animalia, but the evolutionary origin of this novel class of ion channels is unknown. We describe a survey of unicellular eukaryotic genomes for GRLs, identifying several candidates in fungi, protists and algae that contain many structural features characteristic of animal GRLs. The existence of these proteins in unicellular eukaryotes, together with ab initio protein structure predictions, supports homology between GRLs and a large family of uncharacterised plant proteins containing the DUF3537 domain. Together, this evidence suggests an origin of this protein family in the last common eukaryotic ancestor.