The beta-clip fold includes a diverse group of protein domains that are unified 
by the presence of two characteristic waist-like constrictions, which bound a 
central extended region. Members of this fold include enzymes like deoxyuridine 
triphosphatase and the SET methylase, carbohydrate-binding domains like the fish 
antifreeze proteins/Sialate synthase C-terminal domains, and functionally 
enigmatic accessory subunits of urease and molybdopterin biosynthesis protein 
MoeA. In this study, we reconstruct the evolutionary history of this fold using 
sensitive sequence and structure comparisons methods. Using sequence profile 
searches, we identified novel versions of the beta-clip fold in the bacterial 
flagellar chaperone FlgA and the related pilus protein CpaB, the StrU-like 
dehydrogenases, and the UxaA/GarD-like hexuronate dehydratases (SAF 
superfamily). We present evidence that these versions of the beta-clip domain, 
like the related type III anti-freeze proteins and C-terminal domains of sialic 
acid synthases, are involved in interactions with carbohydrates. We propose that 
the FlgA and CpaB-like proteins mediate the assembly of bacterial flagella and 
Flp pili by means of their interactions with the carbohydrate moieties of 
peptidoglycan. The N-terminal beta-clip domain of the hexuronate dehydratases 
appears to have evolved a novel metal-binding site, while their C-terminal 
domain is likely to adopt a metal-binding TIM barrel-like fold. Using structural 
comparisons, we show that the beta-clip fold can be further classified into two 
major groups, one that includes the SAF, SET, dUTPase superfamilies, and the 
other that includes the phage lambda head decoration protein, the beta subunit 
of urease and the C-terminal domain of the molybdenum cofactor biosynthesis 
protein MoeA. Structural comparisons also suggest the beta-clip fold was 
assembled through the duplication of a three-stranded unit. Though the 
three-stranded units are likely to have had a common origin, we present evidence 
that complete beta-clip domains were assembled through such duplications, 
independently on multiple occasions. There is also evidence for circular 
permutation of the basic three-stranded unit on different occasions in the 
evolution of the beta-clip unit. We also describe how assembly of this fold from 
a basic three-stranded unit has been utilized to accommodate a variety of 
activities in its different versions.