The amino acid sequence of the RNA 2'-O-ribose methyltranserase RrmJ was used as a probe for detecting putative homologs through iterative searches of genomic databases. We found a previously unannotated YgdE open reading frame (ORF) in the genome sequences of Escherichia coli and other gamma-Proteobacteria, which shares key features with RrmJ, despite the mutual sequence similarity of these proteins is relatively low. The predicted structural compatibility and the conservation of all functionally important residues between RrmJ and YgdE strongly suggests that the newly identified methyltranserase also modifies 2'-OH groups of ribose. The N-terminal region of YgdE, which has no counterpart in RrmJ, is predicted to form an independent domain, possibly involved in target recognition.