Inverse protein folding, which seeks to identify sequences that fold i
nto a given structure, has been approached by threading candidate sequ
ences onto the structure and scoring them with database-derived potent
ials. The sequences with the lowest energies are predicted to fold int
o that structure. It has been argued that the limited success of this
type of approach is not due to the discrepancy between the scoring pot
ential and the true potential but is rather due to the fact that seque
nces choose their lowest-energy structure rather than structures choos
ing the lowest-energy sequences. Here we develop a non-physical potent
ial scheme optimized for the inverse folding problem. We maximize the
average probability of success for a set of lattice proteins to obtain
the optimal potential energy function, and show that the potential ob
tained by our method is more likely to produce successful predictions
than the true potential.