Biotinylation in vivo is an extremely selective post-translational event where the enzyme biotin protein ligase (BPL) catalyzes the covalent attachment of biotin to one specific and conserved lysine residue of biotin-dependent enzymes. The biotin-accepting lysine, present in a conserved Met-Lys-Met motif, resides in a structured domain that functions as the BPL substrate. We have employed phage display coupled with a genetic selection to identify determinants of the biotin domain (yPC-104) of yeast pyruvate carboxylase 1 (residues 1075-1178) required for interaction with BPL. Mutants isolated using this strategy were analyzed by in vivo biotinylation assays performed at both 30 degrees C and 37 degrees C. The temperature-sensitive substrates were reasoned to have structural mutations, leading to compromised conformations at the higher temperature. This interpretation was supplemented by molecular modeling of yPC-104, since these mutants mapped to residues involved in defining the structure of the biotin domain. In contrast, substitution of the Met residue N-terminal to the target lysine with either Val or Thr produced mutations that were temperature-insensitive in the in vivo assay. Furthermore, these two mutant proteins and wild-type yPC-104 showed identical susceptibility to trypsin, consistent with these substitutions having no structural effect. Kinetic analysis of enzymatic biotinylation using purified Met --> Thr/Val mutant proteins with both yeast and Escherichia coli BPLs revealed that these substitutions had a strong effect upon K(m) values but not k(cat). The Met --> Thr mutant was a poor substrate for both BPLs, whereas the Met --> Val substitution was a poor substrate for bacterial BPL but had only a 2-fold lower affinity for yeast BPL than the wild-type peptide. Our data suggest that substitution of Thr or Val for the Met N-terminal of the biotinyl-Lys results in mutants specifically compromised in their interaction with BPL.