Monte Carlo methods are widely used in protein design, but such methods can be inefficient when many local minima exist. Modified Monte Carlo methods are presented in the context of protein design and sequence sampling: Monte Carlo with replica exchange (MCREM) and biased Monte Carlo with replica exchange (BMCREM). Both methods are applied to an atom based model of the calcium binding protein calbindin (PDB code 4ICB). BMCREM more efficiently samples low temperatures sequences, from which the site-specific probabilities of each amino acid can be obtained. (C) 2004 Elsevier B.V. All rights reserved.