Le Design computationnel de protéines, en anglais « Computational Protein Design » (CPD), est un champ derecherche récent qui vise à fournir des outils de prédiction pour compléter l'ingénierie des protéines. En effet,outre la compréhension théorique des propriétés physico-chimiques fondamentales et fonctionnelles desprotéines, l’ingénierie des protéines a d’importantes applications dans un large éventail de domaines, y comprisdans la biomédecine, la biotechnologie, la nanobiotechnologie et la conception de composés respectueux del’environnement. Le CPD cherche ainsi à accélérer le design de protéines dotées des propriétés désirées enpermettant le traitement d’espaces de séquences de large taille tout en limitant les coûts financier et humain auniveau expérimental.Pour atteindre cet objectif, le CPD requière trois ingrédients conçus de manière appropriée: 1) une modélisationréaliste du système à remodeler; 2) une définition précise des fonctions objectives permettant de caractériser lafonction biochimique ou la propriété physico-chimique cible; 3) et enfin des méthodes d'optimisation efficacespour gérer de grandes tailles de combinatoire.Dans cette thèse, nous avons abordé le CPD avec une attention particulière portée sur l’optimisationcombinatoire. Dans une première série d'études, nous avons appliqué pour la première fois les méthodesd'optimisation de réseaux de fonctions de coût à la résolution de problèmes de CPD. Nous avons constaté qu’encomparaison des autres méthodes existantes, nos approches apportent une accélération du temps de calcul parplusieurs ordres de grandeur sur un large éventail de cas réels de CPD comprenant le design de la stabilité deprotéines ainsi que de complexes protéine-protéine et protéine-ligand. Un critère pour définir l'espace demutations des résidus a également été introduit afin de biaiser les séquences vers celles attendues par uneévolution naturelle en prenant en compte des propriétés structurales des acides aminés. Les méthodesdéveloppées ont été intégrées dans un logiciel dédié au CPD afin de les rendre plus facilement accessibles à lacommunauté scientifique. / Computational Protein Design (CPD) is a very young research field which aims at providing predictive tools to complementprotein engineering. Indeed, in addition to the theoretical understanding of fundamental properties and function of proteins,protein engineering has important applications in a broad range of fields, including biomedical applications, biotechnology,nanobiotechnology and the design of green reagents. CPD seeks at accelerating the design of proteins with wanted propertiesby enabling the exploration of larger sequence space while limiting the financial and human costs at experimental level.To succeed this endeavor, CPD requires three ingredients to be appropriately conceived: 1) a realistic modeling of the designsystem; 2) an accurate definition of objective functions for the target biochemical function or physico-chemical property; 3)and finally an efficient optimization framework to handle large combinatorial sizes.In this thesis, we addressed CPD problems with a special focus on combinatorial optimization. In a first series of studies, weapplied for the first time the Cost Function Network optimization framework to solve CPD problems and found that incomparison to other existing methods, it brings several orders of magnitude speedup on a wide range of real CPD instancesthat include the stability design of proteins, protein-protein and protein-ligand complexes. A tailored criterion to define themutation space of residues was also introduced in order to constrain output sequences to those expected by natural evolutionthrough the integration of some structural properties of amino acids in the protein environment. The developed methods werefinally integrated into a CPD-dedicated software in order to facilitate its accessibility to the scientific community.

Red fluorescent proteins (RFPs) are used extensively in biological research because their longer emission wavelengths are less phototoxic and allow deeper imaging of animal tissue. However, far-red RFPs generally display low brightness, emphasizing the need to develop brighter variants. Here, we investigate three approaches to rigidify the RFP chromophore to increase the quantum yield, and thereby brightness. We first used computational protein design on a maturation-efficient mRojo-VHSV variant previously engineered in our lab to introduce a Superdecker motif, a parallel pi-stack comprising aromatic residue side chains and the phenolate moiety of the chromophore, which we hypothesized would enhance chromophore packing and reduce non-radiative decay. The best mutants identified showed up to 1.7-fold higher quantum yield at pH 9, relative to their parent protein. We next postulated that brightness could be further increased by rigidifying the chromophore via branched aliphatic residues. Computational protein design was performed on a dim mCherry variant, mRojoA, followed by directed evolution on the brightest mutant. The combination of these methodologies yielded mSandy2, the brightest Discosoma-derived monomeric RFP with an emission maximum above 600 nm. Finally, we aimed to increase brightness by focusing on positions where residue rigidity correlated to quantum yield in mCherry-related RFPs according to NMR data that had been previously acquired in our lab. Combinatorial site-saturation mutagenesis was performed on two different surface patches of mCherry at positions 144/145/198 and 194/196/220. Our results demonstrated that surface residues may not be adequate targets for this approach. Altogether, the work herein presents unique rational design methodologies that can be used to increase brightness in RFPs.

abstract: Proteins are, arguably, the most complicated molecular machines found in nature. From the receptor proteins that decorate the exterior of cell membranes to enzymes that catalyze the slowest of chemical reactions, proteins perform a wide variety of essential biological functions. A reductionist view of proteins as a macromolecular group, however, may hold that they simply interact with other chemical species. Notably, proteins interact with other proteins, other biological macromolecules, small molecules, and ions. This in turn makes proteins uniquely qualified for use technological use as sensors of said chemical species (biosensors). Several methods have been developed to convert proteins into biosensors. Many of these techniques take advantage of fluorescence spectroscopy because it is a fast, non-invasive, non-destructive and highly sensitive method that also allows for spatiotemporal control. This, however, requires that first a fluorophore be added to a target protein. Several methods for achieving this have been developed from large, genetically encoded autofluorescent protein tags, to labeling with small molecule fluorophores using bioorthogonal chemical handles, to genetically encoded fluorescent non-canonical amino acids (fNCAA). In recent years, the fNCAA, L-(7-hydroxycoumarin-4yl)ethylglycine (7-HCAA) has been used in to develop several types of biosensors. The dissertation I present here specifically addresses the use of the fNCAA L-(7-hydroxycoumarin-4-yl)ethylglycine (7-HCAA) in protein-based biosensors. I demonstrate 7-HCAA’s ability to act as a Förster resonance energy transfer (FRET) acceptor with tryptophan as the FRET donor in a single protein containing multiple tryptophans. I the describe efforts to elucidate—through both spectroscopic and structural characterization—interactions within a 7-HCAA containing protein that governs 7-HCAA fluorescence. Finally, I present a top-down computational design strategy for incorporating 7-HCAA into proteins that takes advantage of previously described interactions. These reports show the applicability of 7-HCAA and the wider class of fNCAAs as a whole for their use of rationally designed biosensors. / Dissertation/Thesis / Doctoral Dissertation Biochemistry 2020

Le dessin computationnel de protéine, ou CPD, est une technique qui permet de modifier les protéines pour leur conférer de nouvelles propriétés, en exploitant leurs structures 3D et une modélisation moléculaire. Pour rendre la méthode de plus en plus prédictive, les modèles employés doivent constamment progresser. Dans cette thèse, nous avons abordé le problème de la représentation explicite de la flexibilité du squelette protéique. Nous avons développé une méthode de dessin "multi-états", qui se base sur une bibliothèque discrète de conformations du squelette, établie à l'avance. Dans un contexte de simulation Monte Carlo, le paysage énergétique d'une protéine étant rugueux, les changements de squelettes ne peuvent etre acceptés que moyennant certaines précautions. Aussi, pour explorer ces conformations, en même temps que des mutations et des mouvements de chaînes latérales, nous avons introduit un nouveau type de déplacement dans une méthode Monte Carlo existante. Il s'agit d'un déplacement "hybride", où un changement de squelette est suivi d'une courte relaxation Monte Carlo des chaînes latérales seules, après laquelle un test d'acceptation est effectué. Pour respecter une distribution de Boltzmann des états, la probabilité doit avoir une forme précise, qui contient une intégrale de chemin, difficile à calculer en pratique. Deux approximations sont explorées en détail: une basée sur un seul chemin de relaxation, ou chemin "générateur" (Single Path Approximation, ou SPA), et une plus complexe basée sur un ensemble de chemins, obtenus en permutant les étapes élémentaires du chemin générateur (Permuted Path Approximation, ou PPA). Ces deux approximations sont étudiées et comparées sur deux protéines. En particulier, nous calculons les énergies relatives des conformations du squelette en utilisant trois méthodes différentes, qui passent réversiblement d'une conformation à l'autre en empruntent des chemins très différents. Le bon accord entre les méthodes, obtenu avec de nombreuses paramétrisations différentes, montre que l'énergie libre se comporte bien comme une fonction d'état, suggérant que les états sont bien échantillonnés selon la distribution de Boltzmann. La méthode d'échantillonnage est ensuite appliquée à une boucle dans le site actif de la tyrosyl-ARNt synthétase, permettant d'identifier des séquences qui favorisent une conformation, soit ouverte, soit fermée de la boucle, permettant en principe de contrôler ou redessiner sa conformation. Nous décrivons enfin un travail préliminaire visant à augmenter encore la flexibilité du squelette, en explorant un espace de conformations continu et non plus discret. Ce changement d'espace oblige à restructurer complètement le calcul des énergies et le déroulement des simulations, augmente considérable le coût des calculs, et nécessite une parallélisation beaucoup plus agressive du logiciel de simulation. / Computational protein design is a method to modify proteins and obtain new properties, using their 3D structure and molecular modelling. To make the method more predictive, the models need continued improvement. In this thesis, we addressed the problem of explicitly representing the flexibility of the protein backbone. We developed a "multi-state" design approach, based on a small library of backbone conformations, defined ahead of time. In a Monte Carlo framework, given the rugged protein energy landscape, large backbone motions can only be accepted if precautions are taken. Thus, to explore these conformations, along with sidechain mutations and motions, we have introduced a new type of Monte Carlo move. The move is a "hybrid" one, where the backbone changes its conformation, then a short Monte Carlo relaxation of the sidechains is done, followed by an acceptation test. To obtain a Boltzmann sampling of states, the acceptation probability should have a specific form, which involves a path integral that is difficult to calculate. Two approximate forms are explored: the first is based on a single relaxation path, or "generating path" (Single Path Approximation or SPA). The second is more complex and relies on a collection of paths, obtained by shuffling the elementary steps of the generating path (Permuted Path Approximation or PPA). These approximations are tested in depth and compared on two proteins. Free energy differences between the backbone conformations are computed using three different approaches, which move the system reversibly from one conformation to another, but follow very different routes. Good agreement is obtained between the methods and a wide range of parameterizations, indicating that the free energy behaves as a state function, as it should, and strongly suggesting that Boltzmann sampling is verified. The sampling method is applied to the tyrosyl-tRNA synthetase enzyme, allowing us to identify sequences that prefer either an open or a closed conformation of an active site loop, so that in principle we can control, or design the loop conformation. Finally, we describe preliminary work to make the protein backbone fully flexible, moving within a continuous and not a discrete space. This new conformational space requires a complete reorganization of the energy calculation and Monte Carlo simulation scheme, increases simulation cost substantially, and requires a much more aggressive parallelization of our software.

abstract: Continuing and increasing reliance on fossil fuels to satisfy our population’s energy demands has encouraged the search for renewable carbon-free and carbon-neutral sources, such as hydrogen gas or CO2 reduction products. Inspired by nature, one of the objectives of this dissertation was to develop protein-based strategies that can be applied in the production of green fuels. The first project of this dissertation aimed at developing a controllable strategy to incorporate domains with different functions (e. g. catalytic sites, electron transfer modules, light absorbing subunits) into a single multicomponent system. This was accomplished through the rational design of 2,2’-bipyridine modified dimeric peptides that allowed their metal-directed oligomerization by forming tris(bipyridine) complexes, thus resulting in the formation of a hexameric assembly. Additionally, two different approaches to incorporate non-natural organometallic catalysts into protein matrix are discussed. First, cobalt protoporphyrin IX was incorporated into cytochrome b562 to produce a water-soluble proton and CO2 reduction catalyst that is active upon irradiation in the presence of a photosensitizer. The effect of the porphyrin axial ligands provided by the protein environment has been investigated by introducing mutations into the native scaffold, indicating that catalytic activity of proton reduction is dependent on axial coordination to the porphyrin. It is also shown that effects of the protein environment are not directly transferred when applied to other reactions, such as CO2 reduction. Inspired by the active site of [FeFe]-hydrogenases, the second approach is based on the stereoselective preparation of a novel amino acid bearing a 1,2-benzenedithiol side chain. This moiety can serve as an anchoring point for the introduction of metal complexes into protein matrices. By doing so, this strategy enables the study of protein interactions with non-natural cofactors and the effects that it may have on catalysis. The work developed herein lays a foundation for furthering the study of the use of proteins as suitable environments for tuning the activity of organometallic catalysts in aqueous conditions, and interfacing these systems with other supporting units into supramolecular assemblies. / Dissertation/Thesis / Doctoral Dissertation Chemistry 2019

Cellulase activity is due to the activity of multiple enzymes, including endoglucanases, cellobiohydrolases and glucosidases that work synergistically to solubilize crystalline cellulose efficiently. The dependence of hydrolysis reaction rate on temperature predicts that large increases in performance and decreased enzyme cost would be achieved if the enzymatic degradation could be operated at elevated temperatures. However there is always a tradeoff between the activity and stability of enzymes. So obtaining cellulases with high thermostability and simultaneously enhanced activity is a great challenge in the field of bioethanol production. In the studies presented in this dissertation, different computational techniques, such as Molecular Dynamics (MD), Molecular Docking, Quantum Mechanics (QM) and hybrid Quantum Mechanics and Molecular Mechanics (QM/MM), along with several site-directed mutagenesis and in vitro assays have been applied to the study and design of the activity and stability of cellulases. Using molecular dynamics to investigate the thermal unfolding of endoglucanases of family 5 of glycoside hydrolases (GH5), a good correlation between the optimum activity temperatures of cellulases and their structural fluctuations was revealed. These data led us to hypothesize that cellulase stability could be enhanced by redesign of enzyme dynamics through altering the amino acid composition in the highly flexible regions of an endoglucanase that would increase its local or global rigidity. Cellulase C, a GH5 member, was stabilized thermally and chemically by cross linking its highly flexible subdomain. Family 1 of glycoside hydrolases were investigated by QM and hybrid QM/MM methods to analyze the role of non-catalytic polar residues at the active site of GH1 glucosidases that make hydrogen bonds to the glucose moiety at subsite -1. A tyrosine residue in simultaneous interaction with O5 of the glucose ring and the carboxylate group of the nucleophilic glutamate was found to play a significant role in the energy profile along the hydrolysis reaction coordinates. It was shown to reduce the energy barrier of the deglycosylation step by ~12 Kcal/mol. Exclusion of this tyrosine from QM calculation substantially influenced the preactivated structure of the glucose moiety in the enzyme-substrate complex and affected the structural distortion and charge distribution in transition states. / Ph. D.

The next generation of toxic chemicals and hazardous wastes from sophisticated chemical industries will demand the environmental agencies to employ biological methods over the conventional physical and chemical remediation methods. Over the past decade, natural metallo-enzymes have been identified to degrade some of the major chemical contaminants through electron transfer pathways. However, these natural enzymes are less stable in organic solvents and they are not effective for the degradation of toxic compounds such as polychlorinated biphenyls or dioxins. This thesis explores the use of protein design approaches to produce chemically and molecularly modified enzymes, which are highly stable, possess little substrate specificity, and have higher activity than the natural enzymes. The experiments presented in this thesis make use of solid phase synthesis and site-directed mutagenesis for the synthesis and production of these enzymes and popular chromatographic techniques for their purification. The partial characterization of these proteins revealed the essential structural features of these proteins, and their catalytic activity was demonstrated by the use of peroxidase assays. / Master of Science

Synthetic construction of protein molecules has been widely pursued over the last two decades. A primary goal behind de novo protein design has been to build minimal systems by capturing the essential features of protein structures. Such minimal models can be used to understand underlying principles governing folding, structure, and function of proteins molecules. Several approaches envisioning successful construction of synthetic proteins have been described over the years, some of them being admirably successful (DeGrado et al, 1999; Richardson et al> 1992; Baltzer, 1998). Specific patterning of polar and apolar residues in synthetic sequences has been widely used to achieve designed polypeptide structures like helix bundles (DeGrado et ah, 1999) and (3-sheets (Smith and Regan, 1997; Lacroix et a/., 1998), with reliance on hydrophobic driving forces for folding. Our laboratory has been pursuing a distinctly alternative approach, that employs stereochemically constrained amino acids to generate specific secondary structures which can then be assembled into composite structures by appropriately chosen linking segments. This approach, which involves linking prefabricated modules of secondary structures can be termed as a "Meccano set" approach to protein design (Balaram, 1992). The studies embodied in the present thesis describe attempts at construction of synthetic polypeptide motifs using the stereochemically directing influence of conformationally constrained amino acid residues, such as DPro or Aib (α-aminoisobutyric acid). This thesis is subdivided into 8 chapters, with Chapter 1 providing a perspective of the field of protein design. Subsequent chapters (2-8) describe studies directed towards the specific goal of construction of polypeptide motifs. Chapter 2 describes synthesis and conformational characterization of two octapeptides Boc-Leu-Val-Val-DPro-LAla-Leu-Val-Val-OMe (1) and Boc-Leu-Val-Val-DPro-DAla-Leu-Val-Val-OMe (2), designed to investigate the effect of specific β-turn stereochemistry on β-hairpin structures. 500 MHz NMR studies establish that both peptides 1 and 2 adopt predominantly β-hairpin conformations in chloroform and methanol solutions, with interstrand registry established by observation of long-range nuclear Overhauser effects (NOEs). Specific NOEs provide evidence for a type II' β-turn conformation for the DPro-LAla segment in 1, while the NMR data suggest that a type I' DPro-DAla β-turn conformation predominates in the peptide 2. The crystal structure of 1 reveals two independent molecules in the crystallographic asymmetric unit, both of which adopt β-hairpin conformations nucleated by a type II’ β-turn across DPro-LAla and stabilized by 3 cross strand hydrogen bonds. These designed β-hairpins with defined tight turns produce characteristic vibrational circular dichroism (VCD) patterns, demonstrating the utility of VCD as a probe for conformational analysis of β-hairpins. In Chapter 3, we present conformational analysis on designed β-hairpin sequences incorporating a 'Phe-Phe' residue pair at a non-hydrogen bonding position. Two octapeptides Boc-Leu-Phe-Val-DPro-Gly-Leu-Phe-Val-OMe and Boc-Leu-Phe-Val-DPro-Ala-Leu-Phe-Val-OMe were synthesized and conformationally characterized by 500 MHz NMR spectroscopy. Specific NOEs observed in solution provide conclusive evidence favoring specific orientation effects pertaining to the 'Phe-Phe' pair. The peptides exhibited anomalous electronic CD, which has been explained in terms of aromatic contributions by the side chain chromophores. Interestingly, the VCD patterns obtained for these peptides were almost identical to those obtained for other β-hairpins, described in Chapter 2. Chapter 4 describes the synthesis and conformational analysis of designed decapeptide sequences with centrally located DPro-Xxx β-trun segments. Two sequences Boc-Met-Leu»Phe-Val'DPro-Ala-Leu-Val-Val-Phe-OMe (1) and Boc-Met-Leu-Val-Val-^ro-Gly-Leu-Val-Val-Phe-OMe (2) were designed to study the effect of chain length elongation, of β-strands, on designed β-hairpin structures. 500 MHz NMR studies establish β-hairpin folds in both these sequences, with strand segments aligned even at the termini of the structures. Multi-stranded, antiparallel β-sheet structures can be generated by successive placement of β-hairpin sequences in a single polypeptide chain. The successful construction of three stranded β-sheet structures is described in Chapter 5 of this dissertation. A 14-residue peptide Boc-Leu-Phe-Val-DPro-Gly-Leu-Val-Leu-Ala-DPro-Gly-Phe-Val-Leu-OMe (LFV14) was designed such that it is composed of three strand segments linked by two DPro-Gly turn segments. The peptide showed excellent solubility in apolar media, permitting detailed conformational analysis by 500 MHz NMR spectroscopy in organic solvents. Observation of long-range, interstrand NOEs, diagnostic of multiple hairpin structures, provides conclusive evidence for a predominantly populated three stranded β-sheet structure in solution. Extension of this strategy has been described in which an 18-residue peptide, Arg-Gly-Thr-Ile-Lys-DPro-Gly-Val-Thr-Phe-Ala-DPro-Ala-Thr-Lys-Tyr-Gly-Arg, was designed with enhanced solutility in water to probe (β-sheet structure formation in aqueous and mixed aqueous-methanol systems. NMR data provided conclusive evidence in favor of the desired structure being significantly populated in methanol and methanol-water mixtures (50 %, v/v). In water, spectroscopic evidence suggests that the long-range order expected of a three-stranded structure is lost, possibly due to water invading the interstrand hydrogen bonds. Successful construction of a four-stranded antiparallel β-sheet structure has been demonstrated in Chapter 6. A 26-residue peptide Arg-Gly-Thr-Ile-Lys»DPro-Gly-Ile-Thr- Phe-Ala-DPro-Ala-Thr-Val-Leu-Phe-Ala-Val-DPro-Gly-Lys-Thr-Leu-Tyr-Arg was designed to have four strand segments linked by three DPro-Xxx turn segments. The peptide exhibited excellent NMR properties permitting structure determination by analysis of NOE data, which revealed that a four stranded β-sheet structure is indeed populated in methanol. Structural studies on this peptide in mixed methanol-water established that the four stranded β-sheet is appreciably populated at a composition of 50 % (v/v) methanol-water mixture, with the β-sheet structure still detectable even at a composition of 70 % water-30 % methanol. In a completely aqueous environment, the β-sheet structures is significantly disrupted, presumably due to solvent invasion. The nucleating β-turns, however, appear to have retained their structural integrity even in this competitive environment. Chapter 7 describes the insertion of L-Lactic acid (Lac), a hydroxy acid, into polypeptide helices stabilized by a-aminoisobutyricacid (Aib). This study was undertaken to investigate the effect of hydrogen bond deletion on peptide helices. Crystal structure determination of three oligopeptides containing Lac residues has been performed. Peptide 1, Boc-Val-Ala-Leu-Aib-Val-Lac-Leu-Aib-Val-Ala-Leu-OMe, and peptide 2, Boc-Val-Ala-Leu-Aib-Val-Lac-Leu-Aib-Val-Leu-OMe adopt completely helical conformations in the crystalline state, with the Lac(6) residue comfortably accommodated in the center of a helix. NMR studies of peptide 1 and its all amide analog 4, Boc-Val-Ala-Leu-Aib-Val-Ala-Leu-Aib-Val-Ala-Leu-OMe, provide firm evidence for a continuous helical segment in both the cases. In a 14-residue peptide 3, Boc-Val-Ala-Leu-Aib- Val- Ala-Leu- Val- Ala-Leu- Aib-Val-Lac-Leu-OMe, residues Val( 1 )-Leu( 10) adopt a helical conformation, which is terminated by formation of a Schellman motif, with Aib(ll) as the site of chiral reversal. The loss of the hydrogen bond at the C-terminus appears to facilitate the chiral reversal at Aib(l 1). In the final section of this thesis, Chapter 8, successful construction of a synthetic motif containing two distinct elements of secondary structure, a (β-hairpin and a helix, has been described. The design of a 17-residue peptide Boc-Val-Ala-Leu-Aib-Val-Ala-Leu-Gly-Gly-Leu-Phe-Val-DPro-Gly-Leu-Phe-Val-OMe, BH17, is based on a modular approach, in which previously characterized β-hairpin (Leu-Phe-Val-DPro-Gly-Leu-Phe-Val) and helix (Val-Ala-Leu-Aib-Val-Ala-Leu) modules are linked by a Gly-Gly linker. The positioning of the achiral Gly residue at position 8 facilitates termination of the potential helical segment (residues 1-7) by formation of a Schellman motif. Gly(9) is anticipated to be the sole conformationally flexible residue. NMR studies on BH17 indicated the presence of both the helix (residues 1-7) and the β-hairpin (residues 10-17) structures in the sequence, with four major conformational possibilities at the linking segment. Crystal structure determination of BH17 revealed that the two elements of structure are approximately arranged in an orthogonal fashion. The crystal structure validates the original premise that a modular assembly strategy may be viable for the construction of larger synthetic structures. Chapter 9 summarises the major results of this thesis. (For formulae, please refer "pdf" format)

No description available.

<p>Computational protein design aims at identifying protein mutations and conformations with desired target properties (such as increased protein stability, switch of substrate specificity, or novel function) from a vast combinatorial space of candidate solutions. The development of algorithms to efficiently and accurately solve problems in protein design has thus posed significant computational and modeling challenges. Despite the inherent hardness of protein design, a number of computational techniques have been previously developed and applied to a wide range of protein design problems. In many cases, however, the available computational protein design techniques are deficient both in computational power and modeling accuracy. Typical simplifying modeling assumptions for computational protein design are the rigidity of the protein backbone and the discretization of the protein side-chain conformations. Here, we present the derivation, proofs of correctness and complexity, implementation, and application of novel algorithms for computational protein design that, unlike previous approaches, have provably-accurate guarantees even when backbone or continuous side-chain flexibility are incorporated into the model. We also describe novel divide-and-conquer and dynamic programming algorithms for improved computational efficiency that are shown to result in speed-ups of up to several orders of magnitude as compared to previously-available techniques. Our novel algorithms are further incorporated as part of K*, a provably-accurate ensemble-based algorithm for protein-ligand binding prediction and protein design. The application of our suite of protein design algorithms to a variety of problems, including enzyme redesign and small-molecule inhibitor design, is described. Experimental validation, performed by our collaborators, of a set of our computational predictions confirms the feasibility and usefulness of our novel algorithms for computational protein design.</p> / Dissertation