The BLAST tools 17 and resources at NCBI (http://www.ncbi.nlm.nih.gov/) were routinely used. Multiple sequence alignments were built using ClustalW 18 or Multialin 19 . Protein domain analysis was performed using the Pfam database tools (http://pfam.janelia.org/) 15 . Analysis of the phylogenetic distribution and physical clustering was performed in the SEED database 20 . Results are available in the “Diphthamide biosynthesis” and “DUF71-B12” subsystem on the public SEED server (http://pubseed.theseed.org/SubsysEditor.cgi). Phylogenetic profile searches were performed on the IMG platform 21 using the phylogenetic query tool (http://img.jgi.doe.gov/cgi-bin/w/main.cgi?section=PhylogenProfiler&page=phyloProfileForm). Physical clustering was analyzed with the SEED subsystem coloring tool or the Seedviewer Compare region tool 20 as well as on the MicrobesOnline (http://www.microbesonline.org/) tree based genome browser 22 . The SPELL microarray analysis resource 23 was used through the Saccharomyces Genome Database (SGD) (http://www.yeastgenome.org/) 24 to analyze yeast gene coexpression profiles. Clustering of yeast deletion mutants based on phenotype analysis was analyzed through the yeast fitness database available at http://fitdb.stanford.edu/ 25 26 . Mapping of gene distribution profile to taxonomic trees were generated using the iTOL suite (http://itol.embl.de/index.shtml) 27 . Sequence logos were derived using the WebLogo platform 28 .

Visualization and comparison of protein structures and manual docking of ligand molecules were performed using PyMol (The PyMOL Molecular Graphics System, Version 1.4.1, Schrödinger, LLC). XtalView 7 was used for the protein docking exercises.

The survey of the 1996 complete prokaryotic genomes available at the NCBI (http://www.ncbi.nlm.nih.gov/) using BLASTP 17 (default parameters) allowed identification of 119 bacterial and 144 archaeal DUF71 homologs in addition to the 182 eukaryotes homologs identified in the RefSeq database at the NCBI 29 (Additional file 1: Table S1). The retrieved sequences were aligned using MAFFT 8 and the resulting alignment was visually inspected using ED, the alignment editor of the MUST package 30 . The phylogenetic analysis of the 445 sequence was performed using the neighbor-joining distance method implemented in SeaView 31 . The robustness of the resulting tree was assessed by the non-parametric bootstrap method (100 replicates of the original dataset) implemented in SeaView. A second phylogenetic analysis restricted to 50 archaeal and eukaryotic homologs representative of the genetic and genomic diversity of these two Domains was performed using the Bayesian approach implemented in Phylobayes 6 with a LG model.

The distribution of known diphthamide biosynthesis genes in Archaea was analyzed using the SEED database and its tools 20 . The 59 archaeal genomes analyzed all contained an EF-2 encoding gene. Analysis of the distribution of Dph2 and Dph5 in Archaea showed that 58/59 genomes encoded these two proteins. The only archaeon lacking both Dph2 and Dph5 was Korarchaeum cryptofilum OPF8 (Figure 2A). We therefore hypothesized that this organism has lost the diphthamide modification pathway even if the K. cryptofilum EF-2 still harbors the conserved His residue at the site of the modification (His₆₀₃ in the K. cryptofilum sequence, Accession B1L7Q0 in UniprotKB). Using the IMG/JGI phylogenetic query tools 21 , we searched for protein families found in all Archaea except Korarchaeum cryptofilum OPF8, present in Saccharomyces cerevisiae and Homo sapiens but absent in Escherichia coli and Bacillus subtilis, as bacteria are known to lack this modification pathway. Only one family, DUF71/COG2102, followed this taxonomic distribution. This family had been described previously as a PP-loop ATPase of unknown function containing a Rossmannoid class HUP domain 32 .

Using the neighborhood analysis tool of the SEED database 20 , physical clustering was generally not observed between the dph2, dph5 and DUF71 genes except in three Methanosarcina genomes where the dph5 is located in the vicinity of DUF71 genes (Figure 2B). If members of the DUF71 catalyze the last step of diphthamide synthesis they should bind ATP 12 . Structural analysis of the DUF71 protein from Pyrococcus furiosus (PF0828) reveals the presence of two distinct domains: an N-terminal HUP domain that contains a highly conserved PP-motif that interacts with ATP (PDB id: 3RK1) and AMP (PDB id: 3RK0), and a C-terminal 100-residue domain belonging to a novel fold with a highly conserved motif GEGGEF/YE₁₈₈T/S (P. furiosus numbering) that is probably involved in substrate binding and recognition 33 .

YLR143w is the only S. cerevisiae DUF71 family member. Using YLR143w as input in the SPELL co-expression query tool 23 showed that nearly all co-expressed genes were involved in translation and ribosome biogenesis (Additional file 2: Table S2). This observation suggested that the DUF71 protein family has a role in translation as expected for a protein modifying EF-2. Like all known diphthamide synthesis genes, YLR143w is also not essential. More specifically, deletion of any of the five known diphthamide genes confers sordarin resistance in yeast 34 35 and ylr143wΔ strain was shown to be as resistant to this compound as the diphthamide deficient strains (see supplemental data in 34 ). Furthermore, in a recent complete analysis of relationships between gene fitness profiles (co-fitness) and drug inhibition profiles (co-inhibition) from several hundred chemogenomic screens in yeast 25 26 available at http://fitdb.stanford.edu/, it was found that among the top ten interactors with YLR143w by homozygous co-sensitivity are DPH5, DPH2, DPH4 (or JJJ3) and the newly identified DPH7 (or YBR246w) (Additional file 3: Figure S1). Both the coexpression and phenotype data thereby strongly support the hypothesis that YLR143w catalyzes the missing last step of diphthamide biosynthesis, even if one cannot rule out at this stage that other catalytic subunits yet to be identified may also be required.

Finally, comparison of ATP- and AMP-containing structures of PF0828 reveals that the active site of the former has a narrow groove at the end of which only the α-phosphate of ATP is exposed to the solvent whereas the active site of the latter is wide open (Figure 3A and B). Also, there is a sharp turn at the α-phosphate of ATP, suggesting that it is the site of the nucleophilic attack. We therefore performed a docking exercise using the EF-2 structure (PDB id: 3B82) 36 with the ATP-containing structure of PF0828. The docking revealed that the active site groove of the ATP-containing structure can easily accommodate diphthine with a few minor clashes between the two structures (Figure 3A and B).

The modeling also showed that the carboxyl group of diphthine resides near the α-phosphate of ATP and carboxylate group of residue Glu₁₈₈, suggesting that nucleophilic attack by diphthine on the α-phosphate of ATP is highly feasible (Figure 3B). As shown in Figure 3B, the modelling also shows that several residues which are highly conserved among archaeal and eukaryotic PF0828 and YLR143w orthologs beside E₁₈₈, including S₄₄, Y₄₅, E₇₈, Y₁₀₃, Q₁₀₄, A₁₄₉, E₁₈₃ and E₁₈₆ (Additional file 3: Figure S2), are at the interface of the modelled complex of PF0828 with EF-2, supporting the hypothesis that they play important roles in EF-2 recognition (Figure 3B).

The diphthine ammonia lyase reaction requires a source of NH₃ 12 . Domain fusions involving members of the DUF71 family in the Pfam database 15 suggests the source of NH₃ might vary depending on the organism. For example, in a few Archaea (e.g. Methanohalophilus mahii DSM 5219, Methanosalsum zhilinae DSM 4017 or ‘Candidatus Nanosalinarum sp. J07AB56′), a COG0367/AsnB asparagine synthetase [glutamine-hydrolyzing] (EC 6.3.5.4) domain is found at the N-terminus of the DUF71 domain (Figure 2C). This AsnB domain can be further separated into two subdomains, an N-terminal class-II glutamine amidotransferase domain (GAT-II) 37 and an Asn_Synthase_B_C PP-loop ATPase domain (Figure 2C) . This domain organization suggests that in this subset of enzymes, the hydrolysis of glutamine catalyzed by the GAT-II domain could provide the NH₃ moiety to both the DUF71 and the Asn_Synthase_B_C enzymes. On the other hand, in many eukaryotes such as yeast and Arabidopsis thaliana, two YjgF-YER057c-UK114-like domains are fused to the C-terminus of the DUF71 protein as previously noted by Aravind et al. 32 (Figure 2C). The stand-alone members of the YjgF-YER057c-UK114 family, now called the RidA family (for reactive intermediate/imine deaminase A), have been shown to deaminate products generated by PLP-dependent enzymes, which results in the release of NH₃ 38 . The RidA domains fused to DUF71 could therefore be involved in providing the NH₃ ammonium moiety for diphthamide synthesis.

The taxonomic distribution of DUF71 homologs in available complete genomes confirmed that DUF71 is present in one or occasionally two copies in all Archaea except the korarchaeon K. cryptofilum (Table 1 and Additional file 1: Table S1). This pattern is consistent with an ancient origin of the DUF71 gene in Archaea. In sharp contrast, DUF71 is sporadically distributed in Bacteria, being present only in a few representatives of some phyla (Table 1 and Additional file 1: Table S1). This pattern fits either with an ancient origin of DUF71 in Bacteria followed by numerous losses or, conversely, with a more recent acquisition followed by horizontal gene transfer (HGT) among bacterial lineages. To further investigate the evolutionary history of DUF71, we made a phylogenetic analysis of the homologs identified in the three Domains of Life. The resulting tree showed two divergent groups of sequences. The first group contains the eukaryotic and nearly all archaeal sequences (including the predicted yeast DPH6 (YLR143w) and P. furiosus PF0828), whereas the second encompasses all the bacterial sequences as well as the second copy found in a few archaeal genomes (Figure 4 and Additional file 3: Figure S3).

The number of genomes per phylum containing at least one homolog of DUF71 is indicated.

This second group emerged from within the archaeal sequences of the first cluster and showed various contradictions with the currently recognized taxonomy because bacterial sequences from distantly related lineages appeared intermixed in the tree (Figure 4). These observations together with the extremely patchy distribution of DUF71 in bacteria strongly supports the hypothesis that the bacterial DUF71 was of archaeal origin and spread through this domain mainly by HGT. Interestingly, the second homologs present in a few archaeal genomes emerged from bacterial sequences, suggesting that secondary HGT occurred from Bacteria to Archaea allowing them acquiring a second DUF71 homolog.

In contrast, a phylogenetic analysis focused on archaeal and eukaryotic sequences strongly supported the separation between these two Domains (posterior probabilities (PP) = 1). Moreover it recovered the monophyly of most eukaryotic and archaeal major lineages (most PP > 0.95, Additional file 3: Figure S3), suggesting that DUF71 was present in their ancestors. However, as expected given the small number of amino acid positions analyzed (182 positions), the relationships among these lineages were mainly unresolved (most PP < 0.95) precluding the in-depth analysis of the ancient evolutionary history of DUF71 in Archaea and Eucarya (Additional file 3: Figure S3). Nevertheless, the wide distribution of DUF71 in these two Domains (even in highly derived parasites such as Microsporidia, Cryptosporidium, Entamoeba or Nanoarchaeum equitans, not shown) and its ancestral presence in most of their orders/phyla suggested that this gene was present in the last common ancestor of these two Domains. This inference does not imply, however, that no HGT occurred in these Domains. Indeed, some incongruence between the DUF71 phylogeny and the reference phylogeny of organisms 39 suggested putative cases of HGT. For instance, it was observed for the Thermofilum pendens DUF71 that robustly groups with Methanomicrobia (Euryarchaeota) and not with other Thermoproteales (Additional file 3: Figure S3).

Because diphthamide is a modification specific to the archaeal and eukaryotic EF-2 proteins and bacteria lack all known diphthamide biosynthesis genes, we propose that cluster 1 in our phylogeny corresponds to bona fide Dph6 enzymes involved in diphthamide synthesis (Figure 4). This function therefore very likely represents the ancestral function of the whole DUF71 family. In contrast, bacteria do not synthesize diphthamide, suggesting that the bacterial DUF71 homologs and the few additional archaeal copies (cluster 2, Figure 4) are involved in another function, and thus a functional shift occurred after the HGT of an archaeal bona fide Dph6 to bacteria. Notably, these genes (including PF0295, the second DUF71 copy found in P. furiosus) are strongly clustered on the chromosome with vitamin B12 salvage genes. More precisely 75/102 are adjacent to vitamin B12 transporter genes (such as the BtuCDF genes) 40 and 18/102 are adjacent to cbiB genes encoding adenosylcobinamide-phosphate synthetase, an enzyme shared by the de novo and salvage pathways 41 (Figure 5A). This clustering data can be visualized in the “Duf71-B12” subsystem in the SEED database, and two typical clusters are shown in Figure 5B. On this basis, we hypothesize that the archaeal and bacterial DUF71 genes that cluster with B12 vitamin genes have a role in B12 metabolism.

Finally, some bacterial DUF71 proteins might also have other functions because a set of bacteria such as Clostridium perfringens have two or more DUF71 homologs (Figure 4 and Additional file 1: Table S1). The most extreme example is Dehalococcoides sp. CBDB1, which encodes five DUF71 homologs in its genome. In the case of C. perfringens ATCC 13124 and SM101, one homolog (YP_695745 and YP_698440) clusters both physically and phylogenetically (Figure 4 and 5A) with the B12 subgroup proteins, whereas the second homolog (YP_695178 and YP_698039) is related to Acinetobacter baumanii (Cluster 3, Figure 4) and is not found associated to gene clusters related to B12 salvage (data not shown).

Therefore, based on phylogenetic and physical clustering the DUF71 proteins were split into: the Dph6 and the DUF71-B12 subgroups that were annotated as such and captured in the “Diphthamide biosynthesis” and “Duf71-B12” subsystems in the SEED database.

As members of the DUF71-B12 subgroup clustered strongly with B12 transport genes and with cbiB (Figure 5B), we focused on the early steps on B12 salvage, which are quite diverse because several forms of cobamides [cobalamin-like or Cbl-like compounds] can be salvaged (Figure 5A). Cobinamide (Cbi) is adenylated after transport to form adenosylcobinamide (AdoCbi). In most bacteria, AdoCbi is directly phosphorylated by CobU before being transformed after several steps into adenosylcobalamin (AdoCbl or coenzyme B12), in which the lower ligand is 5,6-dimethylbenzimidazole (DMB) (see 42 for review) (Figure 5A). Archaea use a different salvage route in which AdoCbi is converted to adenosylcobyric acid (AdoCby), an intermediate of the de novo pathway, by an amidohydrolase, aCbiZ 43 (Figure 5A). AdoCby is then converted directly to adenosylcobinamide-phosphate (AdoCbi-P) by CbiB. Finally some bacteria have CbiZ homologs (bCbiZ) that hydrolyze adenosylpseudocobalamin (Ado-Pseudo-B12) 44 , which contains an adenine instead of DMB as its lower ligand (Figure 1C and 5A).

In order to gain insight into the possible function of DUF71-B12 family members, we analyzed the co-distribution pattern of CbiZ, CbiB and DUF71-B12 proteins in Archaea and Bacteria. Interestingly, to a few exceptions, all prokaryotic genomes encoding CbiB harbor either CbiZ or DUF71-B12 (Figure 6). However, in bacteria, there was strict anti-correlation between the DUF71-B12 and the CbiZ families (Figure 6A). This was not the case in Archaea where quite a few organisms (such as P. furiosis or Methanosarcina mazei Go1) harbored both families (Figure 6B). This distribution profile suggests that members of the DUF71-B12 subfamily fulfil the same roles as the bacterial CbiZ enzymes (bCbiZ), either by catalysing the same reaction (cleaving Ado-pseudo-B12 into AdoCby) or by providing another route to salvaging Pseudo-B12. This hypothesis would explain why bacteria would have one or the other while Archaea could carry both (Figure 6B), because archaeal CbiZ proteins have been predicted to lack pseudo-B12 cleavage activity 44 .

Detailed analysis of the signature motifs of the two subfamilies reveal that the strictly conserved EGGE/DXE₁₈₈ motif (P. furiosus PF0828 numbering) in Dph6 proteins is replaced by a ENGEF/YH₁₈₈ motif in the DUF71-B12 proteins (Additional file 3: Figure S2 and Additional file 3: Figure S4). In the Dph6 family, E188 is located near the predicted diphthine binding site and is predicted to be involved in catalysis (Figure 3B). The replacement of the strictly conserved E188 residue by a Histidine residue strongly suggest a change in the reaction catalyzed by the DUF71-B12 subfamily compared to the Dph6 family. The structure based comparison between the two subfamilies also strongly supports the hypothesis that their substrates are different, because all residues predicted to be involved in EF-2 binding (Figure 3B see section above) are different in the DUF71-B12 subfamily but mostly conserved within this subfamily (Additional file 3: Figure S2 and residues in green in Figure 3C). Residues that are conserved between the two DUF71 subfamilies (Additional file 3: Figure S2 and residues in blue in Figure 3C) are found around the phosphate groups of ATP, including S₁₂, G₁₃, G₁₄, K₁₅, D₁₆, H₄₈, and T₁₈₉ (PF0828 sequence numbering) or belong to the C-terminal conserved sequence motif (EGGE/D-X-E188) such as G₁₈₂, G₁₈₄, G₁₈₅, E₁₈₆, F₁₈₇ (Additional file 3: Figure S2 and Figure 3C). Further experimental studies will be required to determine whether DUF71-B12 proteins are Ado-pseudo-B12 amidohydrolases or have another role in Ado-pseudo-B12 salvage.