<p>Proteins are involved in all of life's processes and are also responsible for many diseases. Thus, engineering proteins to perform new tasks could revolutionize many areas of biomedical research. One promising technique for protein engineering is computational structure-based protein design (CSPD). CSPD algorithms search large protein conformational spaces to approximate biophysical quantities. In this dissertation we present new algorithms to realistically and accurately model how amino acid mutations change protein structure. These algorithms model continuous flexibility, protein ensembles and positive/negative design, while providing guarantees on the output. Using these algorithms and the OSPREY protein design program we design and apply protocols for three biomedically-relevant problems: (i) prediction of new drug resistance mutations in bacteria to a new preclinical antibiotic, (ii) the redesign of llama antibodies to potentially reduce their immunogenicity for use in preclinical monkey studies, and (iii) scaffold-based anti-HIV antibody design. Experimental validation performed by our collaborators confirmed the importance of the algorithms and protocols.</p> / Dissertation