This thesis describes recombinant proteins that have been generated by rational and combinatorial protein engineering strategies for use in subunit vaccine delivery and tumor targeting. In a first series of studies, recombinant methods for incorporating immunogens into an adjuvant formulation, e.g. immunostimulating complexes (iscoms), were evaluated. Protein immunogens, which are not typically immunogenic in themselves, are normally administered with an adjuvant to improve their immunogenicity. To accomplish iscom incorporation of a Toxoplasma gondii surface antigen through hydrophobic interaction, lipids were added either in vivo via E. coli expression, or in vitro via interaction of an introduced hexahistidyl (His6) peptide and a chelating lipid. The possibility of exploiting the strong interaction between biotin and streptavidin was also explored, in order to couple a Neospora caninum surface antigen to iscom matrix, i.e. iscom particles without any antigen. Subsequent analyses confirmed that the immunogens were successfully incorporated into iscoms by the investigated strategies. In addition, immunization of mice with the recombinant Neospora antigen NcSRS2, associated with iscoms through the biotin-streptavidin interaction, induced specific antibodies to native NcSRS2 and reduced clinical symptoms following challenge infection. The systems described in this thesis might offer convenient and efficient methods for incorporating recombinant immunogens into adjuvant formulations that might be considered for the generation of future recombinant subunit vaccines. In a second series of studies, Affibody® (affibody) ligands directed to the extracellular domain of human epidermal growth factor receptor 2 (HER2/neu), which is known to be overexpressed in ∼ 20-30% of breast cancers, were isolated by phage display in vitro selection from a combinatorial protein library based on the 58 amino acid residue staphylococcal protein A-derived Z domain. Biosensor analyses demonstrated that one of the variants from the phage selection, denoted His6-ZHER2/neu:4, selectively bound with nanomolar affinity (KD ≈ 50 nM) to the extracellular domain of HER2/neu (HER2-ECD) at a different site than the monoclonal antibody trastuzumab. In order to exploit avidity effects, a bivalent affibody ligand was constructed by head-to-tail dimerization, resulting in a 15.6 kDa affibody ligand, termed His6-(ZHER2/neu:4)2, that was shown to have an improved apparent affinity to HER2-ECD (KD ≈ 3 nM) compared to the monovalent affibody. Moreover, radiolabeled monovalent and bivalent affibody ligands showed specific binding in vitro to native HER2/neu molecules expressed in human cancer cells. Biodistribution studies in mice carrying SKOV-3 xenografted tumors revealed that significant amounts of radioactivity were specifically targeted to the tumors in vivo, and the tumors could easily be visualized with a gamma camera. These results suggest that affibody ligands would be interesting candidates for specific tumor targeting in clinical applications, such as in vivo imaging and radiotherapy.

Engineered affinity proteins have together with naturally derived antibodies becomeindispensable tools in many areas of life-science and with the increasing number ofapplications, the need for high-throughput methods for generation of such different affinityproteins is evident. Today, combinatorial protein engineering is the most successful strategy toisolate novel non-immunoglobulin affinity proteins. In this approach, generally termed directedevolution, high-complexity combinatorial libraries are created from which affinity proteins areisolated using an appropriate selection method, thus circumventing the need for detailedknowledge of the protein structure or the binding mechanism, often necessary in more rationalapproaches. Since the introduction of the phage display technology that pioneered the field ofcombinatorial engineering, several alternative selection systems have been developed for thispurpose.This thesis describes the development of a novel selection system based onstaphylococcal surface display and its implementation in directed evolution approaches. In thefirst study, the transformation efficiency to the gram-positive bacteria Staphylococcus carnosus wassuccessfully improved around 10,000-fold to a level that would allow cell surface display ofcomplex combinatorial protein libraries. In two separate studies, the staphylococcal displaysystem was investigated for the applicability in both de novo selection and affinity maturation ofaffibody molecules. First, using a pre-selection strategy with one round of phage display, ahigh-complexity affibody library was displayed on staphylococcal cells. Using fluorescenceactivatedcell sorting, binders with sub-nanomolar affinity to tumor necrosis factor-alpha(TNF-α) were isolated. Second, a combined approach using phage display for de novo selectionof first-generation affibody binders and staphylococcal display in a subsequent affinitymaturation selection was applied to generate binders with low nanomolar affinity to the humanepidermal growth factor receptor-3 (ErbB3). Moreover, in an additional study, thestaphylococcal surface display system was improved by the introduction of a protease 3Ccleavage sequence in the displayed fusion products in order to facilitate straightforwardproduction of soluble proteins for further downstream characterization.Altogether, the presented studies demonstrate that the staphylococcal selection systemindeed is a powerful tool for selection and characterization of novel affinity proteins and couldbecome an attractive alternative to existing selection techniques. / <p>QC 20100726</p>

Even though our understanding of mechanisms such as protein folding and molecular recognition is relatively poor, antibodies and alternative affinity proteins with entirely novel functions are today generated in a routine manner. The reason for this success is an engineering approach generally known as directed evolution. Directed evolution has provided researchers with a tool for circumventing our limited knowledge and hence the possibility to create novel molecules that by no means could have been designed today. The approach is based on construction of high-complexity combinatorial libraries from which protein variants with desired properties can be selected. Engineered proteins are already indispensable tools in nearly all areas of life science and the recent advent of mainly monoclonal antibodies as therapeutic agents has directed even more attention to the field of combinatorial protein engineering. In this thesis, I present the underlying research efforts of six original papers. The overall objective of the studies has been to develop and investigate a new staphylococcal surface display method for protein engineering and protein characterization. The technology is based on display of recombinant proteins on surface of the Gram-positive bacteria Staphylococcus carnosus. In two initial studies, two key issues were addressed in order to improve the protein engineering method in regard to affinity discrimination ability and transformation efficiency. The successful results enabled investigation of the staphylococcal display system for de novo generation of affibody molecules from large combinatorial libraries. In this study, a high-complexity protein library was for the first time displayed on surface of Gram-positive bacteria and by means of fluorescence-activated cell sorting, specific affinity proteins for tumor necrosis factor-alpha were isolated. Moreover, in following papers, the staphylococcal display method was further improved and investigated for affinity determination, soluble protein production and epitope mapping purposes in order to facilitate downstream characterizations of generated affinity proteins. Taken together, in these studies we have demonstrated that the staphylococcal display system is a powerful alternative to existing technologies for protein engineering and protein characterization. / QC 20100809

A poly-leucine transmembrane domain library was randomized at positions corresponding to contact surfaces for a right-handed crossing of two helices to determine the significance of small residues, GxxxG motifs, and hydrogen bonding residues in driving helix-helix interactions within membranes. About 10000 sequences, which include the interfaces of tightly interacting biological transmembrane domains, were subjected to increasing selection strength in the membrane interaction assay TOXCAT and surviving clones were sequenced to identify single site and pairwise amino acid trends. Statistical analysis identified a central glycine to be essential to strong dimerization. The next strongest statistical preference was for a phenylalanine three positions before the key glycine. Secondary to these residues, polar histidine and asparagine residues are also favored in strongly dimerizing sequences, but not to the exclusion of hydrophobic leucine and isoleucine. The analysis identifies novel pairwise combinations that contribute to or are excluded from strong dimerization, the most striking of which is that the biologically important GxxxGxxxG/A pattern is under-represented in the most strongly associating BNIP3-like transmembrane dimers. The variety of residue combinations that support strong dimerization indicates that not only key 'motif' residues, but also the residues that flank them, are important for strong dimerization. Because favorable pairwise combinations of flanking residues occur between both proximal positions and residues separated by two or more turns of helix, the complexity of how sequence context influences motif-driven dimerization is very high.

Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

In this thesis we explore a number of ways in which combinatorial games can be used to help prove results in the area of propositional proof complexity. The results in this thesis can be divided into two sets, the first being dedicated to the study of Resolution space (memory) requirements, whereas the second is centered on formalizing the notion of `dangerous' reductions. The first group of results investigate Resolution space measures by asking questions of the form, `Given a formula F and integer k, does F have a [Type of Resolution] proof with [Type of Resource] at most k?'. We refer to this as a proof complexity resource problem, and provide comprehensive results for several forms of Resolution as well as various resources. These results include the PSPACE-Completeness of Tree Resolution clause space (and the Prover/Delayer game), the PSPACE-Completeness of Input Resolution derivation total space, and the PSPACE-Hardness of Resolution variable space. This research has theoretical as well as practical motivations: Proof complexity research has focused on the size of proofs, and Resolution space requirements are an interesting new theoretical area of study. In more practical terms, the Resolution proof system forms the underpinnings of all modern SAT-solving algorithms, including clause learning. In practice, the limiting factor on these algorithms is memory space, so there is a strong motivation for better understanding it as a resource. With the second group of results in this thesis we investigate and formalize what it means for a reduction to be `dangerous'. The area of SAT-solving necessarily employs reductions in order to translate from other domains to SAT, where the power of highly-optimized algorithms can be brought to bear. Researchers have empirically observed that it is unfortunately possible for reductions to map easy instances from the input domain to hard SAT instances. We develop a non-Hamiltonicity proof system and combine it with additional results concerning the Prover/Delayer game from the first part of this thesis as well as proof complexity results for intuitionistic logic in order to provide the first formal examples of harmful and beneficial reductions, ultimately leading to the development of a framework for studying and comparing translations from one language to another.

Cancer cells display aberrant receptors on their surface that can serve as targets for the development of directed drug therapies. As such, our group has utilized two parallel approaches to redirect the cytotoxic properties of a ribosome-inactivating protein (RIP), Shiga-Like Toxin 1 (SLT 1), by altering its receptor specificity to target and kill cancer cells. The first combinatorial protein library was constructed such that a randomized 7 AA long peptide was inserted within the cytotoxic domain (A chain) of SLT-1. A high-throughput protein-based screening campaign identified a novel A chain toxin variant (named SLT 1AIYSNKLM) capable of targeting and killing human melanoma cells. This variant harbours a peptide insert (IYSNKLM) that directs the A chain to kill human melanoma cell lines. Equilibrium binding studies using 125I-radiolabeled SLT-1AIYSNKLM were conducted to determine the equilibrium binding constant and receptor density on 518-A2 human melanoma cells. When injected into SCID mice bearing a human melanoma xenograft, nanoSPECT/CT imaging as well as the biodistribution profile showed marked tumour uptake and retention of the radiolabeled toxin variant. Furthermore, preliminary experiments have shown that the SLT-1AIYSNKLM receptor is a protein, highlighting the potential for this method to be used in the discovery of novel biomarkers. A second approach was employed to demonstrate that our toxin-based combinatorial library system can be adapted to target known cancer biomarkers. Specifically, SLT-1 A chain variants harbouring 12-residue inserts were expressed in a phage display library. The library was screened against cell lines expressing the human colon cancer marker carcinoembryonic antigen (CEA; CD66e; CEACAM-5) to identify candidates that not only targeted, but internalized into cancer cells within a 1 h period. Variant, CSTA-10, was found to kill CEA-expressing BxPC-3 cells. Overall, the directed evolution of an RIP template such as SLT-1 represents a novel and powerful strategy for the identification of tumour-targeted toxin variants.

Reagents that bind proteins are applicable in biology for detection of molecules, perturbation of signaling pathways and development of small-molecule pharmaceuticals. Protein ligands interact with proteins, inhibiting or altering their function. They are isolated from combinatorial libraries to interact with a specific target, using selection techniques such as phage display or yeast-two-hybrid assay. For the latter, one inconvenience is the detection of false positives, which can be solved by screening pools containing the samples to be tested, instead of individual samples. Samples are distributed in the pools following a pooling design. The PI-deconvolution pooling design was developed to screen cDNA libraries using the yeast-two-hybrid assay, which are smaller in size than protein ligand combinatorial libraries. Modifications to the PI-deconvolution screening technique were developed to adapt it to the screening of protein ligand combinatorial libraries using the yeast-two-hybrid assay. Every spot of the array containing the combinatorial library was randomly pooled. However, the yeast-two-hybrid assay loses sensitivity when strains are pooled. As PI-deconvolution requires detecting every interaction, we determined the optimal amount of library members that can be pooled in a spot, and the optimal number of replicates to ensure the detection of an interaction.<p> The yeast-two-hybrid assay was used to perform a screening of a combinatorial library with seven domains of BCR-ABL, which were pooled according to PI-deconvolution. BCR-ABL is a chimeric protein with unregulated kinase activity that is responsible for chronic myelogenous leukemia. The scaffold used in the combinatorial library was an engineered intein that forms lariat peptides. After a screening of this library was performed, positive interactions were detected in 775 spots of the arrays that contained 1432 positive hits. Only 53 spots were deconvoluted. The coding sequences of the lariat peptides were determined for 23 lariat peptides interacted with the GEF domain of BCR, and for ABL, two with the FABD domain, one with the SH1 domain, and one with the SH3 domain. Finally, a &beta;-galactosidase assay was performed to assess the affinity of the lariat peptides for their target.<p> The isolated lariat peptides are potential inhibitors of BCR-ABL that can have therapeutic potential. This study will improve other screenings of combinatorial libraries with the yeast-two-hybrid assay.

Wassily Hoeffding, in his 1963 paper, introduces a procedure to derive inequalities between distributions. This method relies on finding a martingale coupling between the two random variables. I have developed a construction that establishes such couplings in various urn models. I use this construction to prove the inequality between the hypergeometric and binomial random variables that appears in Hoeffding's paper. I have then used and extended my urn construction to create new inequalities.

In this thesis we explore a number of ways in which combinatorial games can be used to help prove results in the area of propositional proof complexity. The results in this thesis can be divided into two sets, the first being dedicated to the study of Resolution space (memory) requirements, whereas the second is centered on formalizing the notion of `dangerous' reductions. The first group of results investigate Resolution space measures by asking questions of the form, `Given a formula F and integer k, does F have a [Type of Resolution] proof with [Type of Resource] at most k?'. We refer to this as a proof complexity resource problem, and provide comprehensive results for several forms of Resolution as well as various resources. These results include the PSPACE-Completeness of Tree Resolution clause space (and the Prover/Delayer game), the PSPACE-Completeness of Input Resolution derivation total space, and the PSPACE-Hardness of Resolution variable space. This research has theoretical as well as practical motivations: Proof complexity research has focused on the size of proofs, and Resolution space requirements are an interesting new theoretical area of study. In more practical terms, the Resolution proof system forms the underpinnings of all modern SAT-solving algorithms, including clause learning. In practice, the limiting factor on these algorithms is memory space, so there is a strong motivation for better understanding it as a resource. With the second group of results in this thesis we investigate and formalize what it means for a reduction to be `dangerous'. The area of SAT-solving necessarily employs reductions in order to translate from other domains to SAT, where the power of highly-optimized algorithms can be brought to bear. Researchers have empirically observed that it is unfortunately possible for reductions to map easy instances from the input domain to hard SAT instances. We develop a non-Hamiltonicity proof system and combine it with additional results concerning the Prover/Delayer game from the first part of this thesis as well as proof complexity results for intuitionistic logic in order to provide the first formal examples of harmful and beneficial reductions, ultimately leading to the development of a framework for studying and comparing translations from one language to another.