{'fraction_non_alphanumeric': 0.030219901774257776, 'fraction_numerical': 0.015220565461705235, 'mean_word_length': 5.160261651676206, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Multiplexed Bacterial Two-Hybrid for Rapid Characterization of Protein-Protein Interactions and Iterative Protein Design

Myriad biological functions require protein-protein interactions (PPIs), and engineered PPIs are crucial for applications ranging from drug design to synthetic cell circuits. Understanding and engineering specificity in PPIs is particularly challenging as subtle sequence changes can drastically alter specificity. Coiled-coils are small protein domains that have long served as a simple model for studying the sequence-determinants of specificity and have been used as modular building blocks to build large protein nanostructures and synthetic circuits. Despite their simple rules and long-time use, building large sets of well-behaved orthogonal pairs that can be used together is still challenging because predictions are often inaccurate, and, as the library size increases, it becomes difficult to test predictions at scale. To address these problems, we first developed a method called the Next-Generation Bacterial Two-Hybrid (NGB2H), which combines gene synthesis, a bacterial two-hybrid assay, and a high-throughput next-generation sequencing readout, allowing rapid exploration of interactions of programmed protein libraries in a quantitative and scalable way. After validating the NGB2H system on previously characterized libraries, we designed, built, and tested large sets of orthogonal synthetic coiled-coils. In an iterative set of experiments, we assayed more than 8,000 PPIs, used the dataset to train a novel linear model-based coiled-coil scoring algorithm, and then characterized nearly 18,000 interactions to identify the largest set of orthogonal PPIs to date with twenty-two on-target interactions.

is still difficult. Though numerous groups have attempted to create orthogonal sets of coiled-coils, they've been limited in size and still display significant off-target interactions 15,16 . Increasing our ability to design, build and characterize large sets of interacting proteins could help solve this problem by providing empirical data to improve computational models of PPIs. Simultaneously this would vastly increase the number of available orthogonal building blocks for nanoscale structural design allowing the creation of previously unbuildable structures.
Here we combine gene synthesis, a novel assay that allows for multiplexed bimolecular interaction screening, and a computational pipeline to design large libraries of orthogonally interacting coiled-coils. We first built and validated a novel assay, the Next-Generation Bacterial Two-Hybrid (NGB2H) system that has a number of unique advantages over other methodologies for characterizing protein libraries. In particular, the NGB2H system allows for screening of bimolecular interactions without having to test all-against-all libraries, direct large-scale synthesis using oligonucleotide arrays to explore design space, quantitative readouts on the entire library including negative interactions, and allows for understanding low affinity interactions inside the crowded cellular context. We did this iteratively with synthetically-designed libraries increasing in size from 256 interactions to more than 18,000 interactions. From this we identified the largest sets of orthogonal proteins to date and developed an improved coiled-coil design algorithm for future design purposes of this versatile protein domain.

Results:
NGB2H system design To allow iterative protein design using synthetic constructs, we built a generalizable, scalable bacterial two-hybrid system using a significantly modified version of the B. pertussis adenylate cyclase two-hybrid 17 ( Figure 1A, Supplementary Information Section 1). Briefly, the two-hybrid functions much as in Karimova et al. 17 , where interacting hybrid proteins reconstitute adenylate cyclase to produce cAMP which drives reporter gene expression. We measured relative transcription of a uniquely identifying DNA barcode residing in the reporter gene, which serves as a measure for interaction strength. The barcode is mapped to the two fully sequenced hybrid proteins at an early cloning step using high-throughput sequencing when the barcode and proteins are physically adjacent. This unambiguously identifies even highly homologous proteins and separates synthetic errors from programmed designs. Thus, measuring the relative barcode transcription provides a quantitative, massively multiplexed characterization of PPIs with short read sequencing. Because the NGB2H system uses a mapping step, it can use gene synthesis, rather than preconstructed libraries to create diversity, which further frees it from one-against-all or all-against-all testing common in two-hybrids. We made a number of other improvements, including: (1) titratable and inducible control of hybrid protein expression and optimized reporter response on a single plasmid, (2) a background strain with linear cAMP accumulation, (3) a GFP reporter instead of beta-galactosidase for more rapid individual characterization, (4) the use of multiple barcodes per construct to achieve better statistical certainty, and (5) a scarless cloning scheme that allows for library creation with any designed sequence. (More information Supplementary Information Section 1).
Validation of the NGB2H system After optimizing the system with single construct GFP measurements ( Figure S1), we validated the NGB2H system with 256 previously characterized interactions 15 , which we call the CC0 Library. The CC0 Library is a set of sixteen de novo designed, orthogonal, heterodimeric coiled-coils tested in an all-against-all configuration. The proteins are highly similar, four heptad coiled-coils which vary only at the a-position (Ile/Asn), e-position and g-position (Lys/Glu) ( Figure 1B). We designed the CC0 Library to be compatible with our system (Figure S2A), barcoded and cloned it ( Figure S3A, S4). After inducing the two-hybrid for six hours, we took samples for RNA and DNA extraction to measure interaction strength and normalize for plasmid abundance, respectively. We obtained high-quality measurements for all 256 protein pairs and calculated an Interaction score where The NGB2H assay was highly replicable, with biological replicates having similar Interaction scores (Pearson's r > 0.98, p < 10 -15 ) with a dynamic range of more than 100-fold ( Figure 1C). We checked several internal controls to validate the measurements of the NGB2H assay. First, as the protein code is degenerate, we screened nine different codon usages for each pair of proteins. Different codon usages showed consistent Interaction scores (representative pair Figure 1D) with all usages correlating with Pearson's r > 0.92 and p < 10 -15 ( Figure S5), demonstrating minimal effects from DNA sequence variation and low levels of noise in Interaction scores.
We also compared the Interaction scores of protein pairs when attached to the other half of the two-hybrid, which we call the reciprocal orientation. We found that the CC0 Library has a strong correlation between the primary and reciprocal orientations (Pearson's r = 0.92, p < 10 -15 ) ( Figure 1E), indicating that the biological machinery of the NGB2H system faithfully recapitulates the biochemical interaction. In addition, a portion of our library contained frameshift mutations which should not create functional PPIs. As expected, Interaction scores of constructs with indels cluster at the bottom of the range of correct constructs ( Figure S6). Lastly, to show that the NGB2H system does not suffer from barcode effects or selection pressure from the repeated cloning steps, we replicated the assay with an independent re-barcoding and re-cloning of the CC0 Library which showed strong correlation with the first iteration's Interaction scores (Pearson's r > 0.98, p < 10 -15 ) ( Figure 1F). Having confirmed the internal consistency of the CC0 Library, we compared it to the previously published results. When compared to circular dichroism data published in Crooks et al. 15 , we found the NGB2H system's dynamic range correlated well with melting temperatures greater than 40˚C ( Figure 1G, 1H). Given the differences in technique -in vivo versus in vitro , interaction strength versus helicity -the correlation between the Interaction score and Tm (Pearson's r > 0.75, p < 10 -15 , Figure S7) largely validates the NGB2H system. Finally, the NGB2H system needs to be highly scalable. To test its scalability, we downsampled the raw sequencing reads between 10 and 150-fold and found strong agreement with our full dataset even when downsampled 100-fold (Pearson's r > 0.85, p < 10 -15 , Figure 1I), which implies the ability to accurately screen ~25,000 interactions with an equal number of reads.
Computational design of large sets of orthogonal coiled-coils To computationally predict large, orthogonal sets of coiled-coils for empirical verification, we built a two-step computational pipeline ( Figure 2A). In brief, we calculated 16.7 million interaction scores for all four heptad coiled-coils with Ile or Asn at the a-position and Glu or Lys at the e-and g-positions using the scoring model from Potapov et al 13 . We then identified sets with an orthogonality gap-those sets where all on-target interactions had a higher predicted score than all off-target interactions. Though computationally challenging, this is tractable as a variant of the maximum independent set problem 18 . We identified the fifteen largest sets and designed each of them with three different backbones (each containing different residues at the noncontact b, c, and f-positions) to investigate their contribution to coiled-coil stability 19 . We combined these with two sets of controls spanning eleven backbones, for a total of 56 sets containing between 64 to 961 interactions (8,169 interactions overall), which we named the CCNG1 Library. After testing a subset of the CCNG1 Library to validate our in-house designs, ( Figure S8, S9, Supplementary Information Section 8.3), we designed ( Figure  S2C), cloned ( Figure S3C, S4) and ran the NGB2H assay, from which we collected quality data ( Figure S10) on 8,073 interactions.
Large orthogonal sets in the CCNG1 library Although we designed our coiled-coils to be orthogonal, the current state-of-the-art design algorithms are relatively inaccurate. Thus, similar to our designs, we reduced the problem to the maximum independent set problem to identify the largest orthogonal subset of each set. We were able to identify a set of orthogonal coiled-coils that contains twelve pairs, which includes four heterodimers and eight homodimers ( Figure 2B). We have also identified a set of seven heterodimers and three homodimers ( Figure 2C), that has fewer on-target interactions (ten versus twelve), but contains more proteins (seventeen versus sixteen) and therefore more total potential interactions (153 versus 136).
We characterized the number of on-target interactions across the CCNG1 Library and found 20 of our 51 sets have more than the seven on-target orthogonal interactions in the state-of-the-art set from Crooks et al., (Figure 2D), though many share the same interfacial residues ( Figure S11). We found that these orthogonal sets were composed of between four and seventeen proteins ( Figure S12), five of which are larger than the CC0 Library. As the CCNG1 Library represents the first large scale systematic investigation into the effects of variation at the b, c, and f-positions, we sought to understand how these positions influenced interactions. We tested six backbones containing the same interfacial residues as the CC0 Library ( Figure S13, Supplementary Information Section 8.4) and found that charged backbones led to less specific interaction profiles. To understand the limits of producing orthogonal interactions within highly constrained sequence space, we compared the number of total pairs in each set (the sum of interacting and non-interacting pairs) to the number of pairs in its largest orthogonal subset ( Figure 2E). We found that the number of orthogonal pairs appears to increase progressively slower as set size increased, suggesting much larger sets would need to be screened to identify proportionally more orthogonal coiled-coils or, alternatively, the accuracy of prediction algorithms would need to be improved.
Improving the state-of-the-art coil-coiled interaction prediction algorithms The CCNG1 Library dataset represents the largest dataset of coiled-coil interactions to date. We reasoned that our data could serve as a training set to improve on currently available models. To benchmark current models, we computed scores using algorithms bCipa 14 , Potapov/SVR 13 , Fong/SVM 20 and Vinson/CE 12 which are all linear models with features for amino acid pairings. Each algorithm is only weakly predictive of our measured interactions with the bA backbone ( Figure  3A), as all models have an R 2 < 0.2. Notably, each algorithm predicted the strongest interactions well, but also predicted many weak interactions that when measured had high Interaction scores. We built several linear models similar to bCipa which included numerous innovations ( Supplementary  Information Section 3). First, we trained a model on our data that only included weights for the a-, e-and g-position combinations. We also created versions of this simple model with terms for either consecutive residues in the a-position of the same protein or separate terms for weights at the N-terminal a-position, where fraying may occur ( Figure S14A). We then expanded these models with a novel scoring technique, which we call heptad shifts ( Figure S14B). In short, we expect the predominant form of coiled-coil interaction to be the alignment of heptads that has the strongest interaction, which is not necessarily all four heptads aligned from the N-terminus, but could be an interface of three or fewer heptads. All of our heptad shifting scoring algorithms were significantly better than the corresponding non-shifting versions and our N-terminal a-positions weights algorithm was significantly better than both the basic algorithm and the consecutive a-position algorithm ( Figure 3B). Thus, our final model which we call iCipa uses heptad shifting and terms for the N-terminal a-positions, and it is more predictive of CCNG1 Interaction scores than previous models with an R 2 = 0.27 ( Figure 3C).
iCipa is a linear model, which facilitates interpretation. The weights of iCipa have expected and unexpected characteristics ( Figure 3D). a-position residues prefer Ile/Ile pairings and tolerate Asn/Asn pairings between proteins and disfavor Ile/Asn pairings as expected. As expected, e-and g-positions favor salt bridges between Glu/Lys and disfavor Glu/Glu pairings, but counterintuitively, Lys/Lys pairings are acceptable for forming the interface which may be due to non-canonical interactions by long side chain of lysine.
To test the iCipa model, we excluded all the data from the original CC0 Library while we trained the weights. When the scoring functions are normalized and compared ( Figure 3E), both the Potapov/SVR and bCipa algorithms performed worse in predicting the measured melting points with R 2 < 0.32 compared to iCipa, R 2 = 0.48-a fifty percent increase in predictive ability. Importantly, the increase in predictive power for iCipa on the CC0 Library demonstrates that iCipa has not been trained on an artifact of the NGB2H system but that the NGB2H system provides high quality data on PPIs which can provide general insights into coiled-coil function.

CCmax Library design and verification
To evaluate iCipa's prediction capabilities, demonstrate the scalability of the NGB2H system, and identify larger orthogonal sets of coiled-coils, we built another library, the CCmax Library. The CCmax Library contains 18,491 interactions of 931 different coiled-coils in fifteen predicted orthogonal sets and seven control sets ( Figure 4A). The orthogonal sets were designed using our computational framework and scored with one of fifteen variants of iCipa. After designing ( Figure S2D) and cloning ( Figure S3C, S4) the CCmax library, we collected high quality data on 17,320 interactions ( Figure S15). The CC0 Library was a subset of the CCmax Library and it broadly agreed with its performance in our previous libraries ( Figure S16).

Orthogonal sets of the CCmax Library
We identified orthogonal sets with sizes of up to twenty-two on-target pairs ( Figure 4B) and 784 total interactions ( Figure S17). Five of the sets contained more on-target interactions than any set in the CCNG1 Library, and fifteen contained more on-target interactions than the largest published set 15 . Our largest orthogonal set ( Figure 4C) contained twenty-two coiled-coil dimers, sixteen homodimers and six heterodimers, which is ten on-target interactions larger than the state-of-the-art set from CCNG1. To characterize the accuracy of different iCipa variants, we subsampled each set (ten proteins, 500 times), and found the largest orthogonal set per subsampling. We found little significant difference between the algorithms ( Figure S18) suggesting that orthogonality is still challenging to design using current algorithmic accuracy and underscoring the necessity of large scale experimental verification. Different applications need varying levels of orthogonality; while gene circuits likely need extreme orthogonality, protein origami, which benefits from avidity, is not under such constraints. Thus, we identified the largest orthogonality gap for different numbers of on-target interactions. (Figure 4D, Table S7). As expected, smaller sets had larger gaps, but large orthogonality gaps were identified for sets as large as sixteen on-target interactions. Finally, we compared the CCmax Library's Interaction score with iCipa predictions which show substantial improvement over the CCNG1 Library. iCipa was able to predict Interaction scores with R 2 = 0.43 ( Figure 4E). We attribute the increase in iCipa's power to the use of a single coiled-coil backbone which consists of only alanine residues at the b-, c-and f-positions. The improvement in predictive power appeared in other algorithms to a lesser extent, all of which maintained an R 2 < 0.28 ( Figure S19).

Discussion:
We have developed and validated a novel system for high-throughput identification of PPIs. We built a framework to predict orthogonal coiled-coil interactions and used it to design tens of thousands of interactions which we then assayed with the NGB2H system in a design-build-test cycle. Using the data collected, we improved state-of-the-art coiled-coil interaction prediction algorithms which allowed us to design the largest set of any orthogonal proteins to date with twenty-two on-target interactions. Thus, by iterative design we demonstrate how high-throughput PPI identification can facilitate identification of desired protein function and improve design.
Our work builds on previous high-throughput two-hybrids to create a generalizable system for studying PPIs, that could include both soluble and membrane proteins. By uniting gene synthesis with a mapping step and a barcode readout, our system allows high throughput characterization of any binary PPI. Previous high-throughput studies used highly constrained libraries--either the ORFome 21-24 of one of a handful of reference genomes, targeted single residue mutations which only explore a sliver of sequence space around a primary sequence 25,26 or several randomly sheared coding sequences 27 . Using the capabilities of DNA synthesis broadens the testable sequence space which facilitates investigations of a variety of areas such as protein domains, extant genetic variation, evolutionary trajectories or epistatic effects. Furthermore, for the investigator who is not interested in an all-against-all approach, synthesis allows the explicit pairings of only certain proteins. While we benefited from the short length of our proteins of interest, recent pooled gene synthesis techniques 28,29 can be used to interrogate much larger proteins. Deconvoluting library diversity has also been a challenge for other multiplexed assays. Other multiplexed methods involved picking colonies and sanger sequencing them 21 , mapping the beginning of reading frames to reference genomes [22][23][24] or manually BLASTing obtained reads 27 . Our explicit mapping step allows for the high-throughput creation of a library to map arbitrary proteins to DNA barcodes, and because it is a separate step it could use long read sequencing to overcome the length limitations of Illumina sequencing. Finally, by using a barcode readout downstream of synthesis and mapping we can measure protein libraries in many formats.
Our improvements to coiled-coil design algorithms represent an important advance for de novo protein design. Though coiled-coil interactions have been modelled with diverse approaches, our iCipa algorithm shows clear advantages over existing models. In particular, heptad shifting provides an intuitive, biologically rational addition that can be applied to any future improvements in coiled-coil design. Overall, we found iCipa to be substantially more accurate than other tested algorithms, at least for this limited set of residues tested.
Here, we simultaneously performed a massive characterization of PPIs within a protein family and identified the largest set of orthogonal proteins identified to date. The CCmax Library characterized three times as many interactions than any previous intra-protein family work 13 . From the total of 26,049 interactions we characterized, we found a large number of orthogonal proteins-in sets of up to 12 heterodimers or 22 heterodimers and homodimers. Though orthogonal coiled-coils are particularly needed as the building blocks for protein origami 4,5 , they could be substituted for histidine kinases in orthogonal signaling pathways 30 , synthetic orthogonal transcriptional logic gates 8,31,32 , or for orthogonal cellular localization 33 .
Thus, the ability to characterize constructs across highly-diverse sequence space and for the identification of networked properties such as orthogonality, highlights the NGB2H's scalability and generality. Because it can be adapted to any sequence the experimenter desires, the NGB2H facilitates interrogation of PPIs beyond endogenous interactomes, it can be used to characterize whole protein families, empirically inform protein design, or investigate complex phenomena like epistasis.