The N-degrons, a set of degradation signals recognized by the N-end rule 
pathway, comprise a protein's destabilizing N-terminal residue and an internal 
lysine residue. We show that the strength of an N-degron can be markedly 
increased, without loss of specificity, through the addition of lysine residues. 
A nearly exhaustive screen was carried out for N-degrons in the lysine 
(K)-asparagine (N) sequence space of the 14-residue peptides containing either K 
or N (16 384 different sequences). Of these sequences, 68 were found to function 
as N-degrons, and three of them were at least as active and specific as any of 
the previously known N-degrons. All 68 K/N-based N-degrons lacked the lysine at 
position 2, and all three of the strongest N-degrons contained lysines at 
positions 3 and 15. The results support a model of the targeting mechanism in 
which the binding of the E3-E2 complex to the substrate's destabilizing 
N-terminal residue is followed by a stochastic search for a sterically suitable 
lysine residue. Our strategy of screening a small library that encompasses the 
entire sequence space of two amino acids should be of use in many settings, 
including studies of protein targeting and folding.