Artisan procedures to generate uniform tilings

This paper try to prove how artisans c ould discover all uniform tilings and very interesting others us ing artisanal combinatorial pro cedures without having to use mathematical procedures out of their reac h. Plane Geometry started up his way through History by means of fundamental drawing tools: ruler and co mpass. Artisans used same tools to carry out their orna mental patterns but at some point they began to work manually using physical representations of fi gures or tiles previously drawing by means of ruler and compass. That is an important step for craftsman because this way provides tools that let him come in the world of symmetry opera tions and empirical knowledge of symmetry groups. Artisans started up to pr oduce little wooden, ceramic or clay tiles and began to experiment with them by means of joining pieces whether edge to edge or vertex to vertex in that way so it can c over the plane without gaps. Economy in making floor or ceramic tiles could be most important reason to develop these procedures. This empiric way to develop tilings led not only to discover all uniform tilings but later discovering of aperiodic tilings.

Automated wordlength optimization framework for multi-source statistical interval-based analysis of nonlinear systems with control-flow structures

El uso de aritmética de punto fijo es una opción de diseño muy extendida en sistemas con fuertes restricciones de área, consumo o rendimiento. Para producir implementaciones donde los costes se minimicen sin impactar negativamente en la precisión de los resultados debemos llevar a cabo una asignación cuidadosa de anchuras de palabra. Encontrar la combinación óptima de anchuras de palabra en coma fija para un sistema dado es un problema combinatorio NP-hard al que los diseñadores dedican entre el 25 y el 50 % del ciclo de diseño. Las plataformas hardware reconfigurables, como son las FPGAs, también se benefician de las ventajas que ofrece la aritmética de coma fija, ya que éstas compensan las frecuencias de reloj más bajas y el uso más ineficiente del hardware que hacen estas plataformas respecto a los ASICs. A medida que las FPGAs se popularizan para su uso en computación científica los diseños aumentan de tamaño y complejidad hasta llegar al punto en que no pueden ser manejados eficientemente por las técnicas actuales de modelado de señal y ruido de cuantificación y de optimización de anchura de palabra. En esta Tesis Doctoral exploramos distintos aspectos del problema de la cuantificación y presentamos nuevas metodologías para cada uno de ellos: Las técnicas basadas en extensiones de intervalos han permitido obtener modelos de propagación de señal y ruido de cuantificación muy precisos en sistemas con operaciones no lineales. Nosotros llevamos esta aproximación un paso más allá introduciendo elementos de Multi-Element Generalized Polynomial Chaos (ME-gPC) y combinándolos con una técnica moderna basada en Modified Affine Arithmetic (MAA) estadístico para así modelar sistemas que contienen estructuras de control de flujo. Nuestra metodología genera los distintos caminos de ejecución automáticamente, determina las regiones del dominio de entrada que ejercitarán cada uno de ellos y extrae los momentos estadísticos del sistema a partir de dichas soluciones parciales. Utilizamos esta técnica para estimar tanto el rango dinámico como el ruido de redondeo en sistemas con las ya mencionadas estructuras de control de flujo y mostramos la precisión de nuestra aproximación, que en determinados casos de uso con operadores no lineales llega a tener tan solo una desviación del 0.04% con respecto a los valores de referencia obtenidos mediante simulación. Un inconveniente conocido de las técnicas basadas en extensiones de intervalos es la explosión combinacional de términos a medida que el tamaño de los sistemas a estudiar crece, lo cual conlleva problemas de escalabilidad. Para afrontar este problema presen tamos una técnica de inyección de ruidos agrupados que hace grupos con las señales del sistema, introduce las fuentes de ruido para cada uno de los grupos por separado y finalmente combina los resultados de cada uno de ellos. De esta forma, el número de fuentes de ruido queda controlado en cada momento y, debido a ello, la explosión combinatoria se minimiza. También presentamos un algoritmo de particionado multi-vía destinado a minimizar la desviación de los resultados a causa de la pérdida de correlación entre términos de ruido con el objetivo de mantener los resultados tan precisos como sea posible. La presente Tesis Doctoral también aborda el desarrollo de metodologías de optimización de anchura de palabra basadas en simulaciones de Monte-Cario que se ejecuten en tiempos razonables. Para ello presentamos dos nuevas técnicas que exploran la reducción del tiempo de ejecución desde distintos ángulos: En primer lugar, el método interpolativo aplica un interpolador sencillo pero preciso para estimar la sensibilidad de cada señal, y que es usado después durante la etapa de optimización. En segundo lugar, el método incremental gira en torno al hecho de que, aunque es estrictamente necesario mantener un intervalo de confianza dado para los resultados finales de nuestra búsqueda, podemos emplear niveles de confianza más relajados, lo cual deriva en un menor número de pruebas por simulación, en las etapas iniciales de la búsqueda, cuando todavía estamos lejos de las soluciones optimizadas. Mediante estas dos aproximaciones demostramos que podemos acelerar el tiempo de ejecución de los algoritmos clásicos de búsqueda voraz en factores de hasta x240 para problemas de tamaño pequeño/mediano. Finalmente, este libro presenta HOPLITE, una infraestructura de cuantificación automatizada, flexible y modular que incluye la implementación de las técnicas anteriores y se proporciona de forma pública. Su objetivo es ofrecer a desabolladores e investigadores un entorno común para prototipar y verificar nuevas metodologías de cuantificación de forma sencilla. Describimos el flujo de trabajo, justificamos las decisiones de diseño tomadas, explicamos su API pública y hacemos una demostración paso a paso de su funcionamiento. Además mostramos, a través de un ejemplo sencillo, la forma en que conectar nuevas extensiones a la herramienta con las interfaces ya existentes para poder así expandir y mejorar las capacidades de HOPLITE. ABSTRACT Using fixed-point arithmetic is one of the most common design choices for systems where area, power or throughput are heavily constrained. In order to produce implementations where the cost is minimized without negatively impacting the accuracy of the results, a careful assignment of word-lengths is required. The problem of finding the optimal combination of fixed-point word-lengths for a given system is a combinatorial NP-hard problem to which developers devote between 25 and 50% of the design-cycle time. Reconfigurable hardware platforms such as FPGAs also benefit of the advantages of fixed-point arithmetic, as it compensates for the slower clock frequencies and less efficient area utilization of the hardware platform with respect to ASICs. As FPGAs become commonly used for scientific computation, designs constantly grow larger and more complex, up to the point where they cannot be handled efficiently by current signal and quantization noise modelling and word-length optimization methodologies. In this Ph.D. Thesis we explore different aspects of the quantization problem and we present new methodologies for each of them: The techniques based on extensions of intervals have allowed to obtain accurate models of the signal and quantization noise propagation in systems with non-linear operations. We take this approach a step further by introducing elements of MultiElement Generalized Polynomial Chaos (ME-gPC) and combining them with an stateof- the-art Statistical Modified Affine Arithmetic (MAA) based methodology in order to model systems that contain control-flow structures. Our methodology produces the different execution paths automatically, determines the regions of the input domain that will exercise them, and extracts the system statistical moments from the partial results. We use this technique to estimate both the dynamic range and the round-off noise in systems with the aforementioned control-flow structures. We show the good accuracy of our approach, which in some case studies with non-linear operators shows a 0.04 % deviation respect to the simulation-based reference values. A known drawback of the techniques based on extensions of intervals is the combinatorial explosion of terms as the size of the targeted systems grows, which leads to scalability problems. To address this issue we present a clustered noise injection technique that groups the signals in the system, introduces the noise terms in each group independently and then combines the results at the end. In this way, the number of noise sources in the system at a given time is controlled and, because of this, the combinato rial explosion is minimized. We also present a multi-way partitioning algorithm aimed at minimizing the deviation of the results due to the loss of correlation between noise terms, in order to keep the results as accurate as possible. This Ph.D. Thesis also covers the development of methodologies for word-length optimization based on Monte-Carlo simulations in reasonable times. We do so by presenting two novel techniques that explore the reduction of the execution times approaching the problem in two different ways: First, the interpolative method applies a simple but precise interpolator to estimate the sensitivity of each signal, which is later used to guide the optimization effort. Second, the incremental method revolves on the fact that, although we strictly need to guarantee a certain confidence level in the simulations for the final results of the optimization process, we can do it with more relaxed levels, which in turn implies using a considerably smaller amount of samples, in the initial stages of the process, when we are still far from the optimized solution. Through these two approaches we demonstrate that the execution time of classical greedy techniques can be accelerated by factors of up to ×240 for small/medium sized problems. Finally, this book introduces HOPLITE, an automated, flexible and modular framework for quantization that includes the implementation of the previous techniques and is provided for public access. The aim is to offer a common ground for developers and researches for prototyping and verifying new techniques for system modelling and word-length optimization easily. We describe its work flow, justifying the taken design decisions, explain its public API and we do a step-by-step demonstration of its execution. We also show, through an example, the way new extensions to the flow should be connected to the existing interfaces in order to expand and improve the capabilities of HOPLITE.

Ectopic expression of the minimal whiE polyketide synthase generates a library of aromatic polyketides of diverse sizes and shapes

The single recombinant expressing the Streptomyces coelicolor minimal whiE (spore pigment) polyketide synthase (PKS) is uniquely capable of generating a large array of well more than 30 polyketides, many of which, so far, are novel to this recombinant. The characterized polyketides represent a diverse set of molecules that differ in size (chain length) and shape (cyclization pattern). This combinatorial biosynthetic library is, by far, the largest and most complex of its kind described to date and indicates that the minimal whiE PKS does not independently control polyketide chain length nor dictate the first cyclization event. Rather, the minimal PKS enzyme complex must rely on the stabilizing effects of additional subunits (i.e., the cyclase whiE-ORFVI) to ensure that the chain reaches the full 24 carbons and cyclizes correctly. This dramatic loss of control implies that the growing polyketide chain does not remain enzyme bound, resulting in the spontaneous cyclization of the methyl terminus. Among the six characterized dodecaketides, four different first-ring cyclization regiochemistries are represented, including C7/C12, C8/C13, C10/C15, and C13/C15. The dodecaketide TW93h possesses a unique 2,4-dioxaadamantane ring system and represents a new structural class of polyketides with no related structures isolated from natural or engineered organisms, thus supporting the claim that engineered biosynthesis is capable of producing novel chemotypes.

A novel glutamine–RNA interaction identified by screening libraries in mammalian cells

The arginine-rich motif provides a versatile framework for RNA recognition in which few amino acids other than arginine are needed to mediate specific binding. Using a mammalian screening system based on transcriptional activation by HIV Tat, we identified novel arginine-rich peptides from combinatorial libraries that bind tightly to the Rev response element of HIV. Remarkably, a single glutamine, but not asparagine, within a stretch of polyarginine can mediate high-affinity binding. These results, together with the structure of a Rev peptide-Rev response element complex, suggest that the carboxamide groups of glutamine or asparagine are well-suited to hydrogen bond to G-A base pairs and begin to establish an RNA recognition code for the arginine-rich motif. The screening approach may provide a relatively general method for screening expression libraries in mammalian cells.

The structure and organization within the membrane of the helices composing the pore-forming domain of Bacillus thuringiensis δ-endotoxin are consistent with an “umbrella-like” structure of the pore

The aim of this study was to elucidate the mechanism of membrane insertion and the structural organization of pores formed by Bacillus thuringiensis δ-endotoxin. We determined the relative affinities for membranes of peptides corresponding to the seven helices that compose the toxin pore-forming domain, their modes of membrane interaction, their structures within membranes, and their orientations relative to the membrane normal. In addition, we used resonance energy transfer measurements of all possible combinatorial pairs of membrane-bound helices to map the network of interactions between helices in their membrane-bound state. The interaction of the helices with the bilayer membrane was also probed by a Monte Carlo simulation protocol to determine lowest-energy orientations. Our results are consistent with a situation in which helices α4 and α5 insert into the membrane as a helical hairpin in an antiparallel manner, while the other helices lie on the membrane surface like the ribs of an umbrella (the “umbrella model”). Our results also support the suggestion that α7 may serve as a binding sensor to initiate the structural rearrangement of the pore-forming domain.

The 2.0-Å resolution crystal structure of a trimeric antibody fragment with noncognate VH–VL domain pairs shows a rearrangement of VH CDR3

The 2.0-Å resolution x-ray crystal structure of a novel trimeric antibody fragment, a “triabody,” has been determined. The trimer is made up of polypeptides constructed in a manner identical to that previously described for some “diabodies”: a VL domain directly fused to the C terminus of a VH domain—i.e., without any linker sequence. The trimer has three Fv heads with the polypeptides arranged in a cyclic, head-to-tail fashion. For the particular structure reported here, the polypeptide was constructed with a VH domain from one antibody fused to the VL domain from an unrelated antibody giving rise to “combinatorial” Fvs upon formation of the trimer. The structure shows that the exchange of the VL domain from antibody B1-8, a Vλ domain, with the VL domain from antibody NQ11, a Vκ domain, leads to a dramatic conformational change in the VH CDR3 loop of antibody B1-8. The magnitude of this change is similar to the largest of the conformational changes observed in antibody fragments in response to antigen binding. Combinatorial pairing of VH and VL domains constitutes a major component of antibody diversity. Conformationally flexible antigen-binding sites capable of adapting to the specific CDR3 loop context created upon VH–VL pairing may be employed by the immune system to maximize the structural diversity of the immune response.

Phage display of a catalytic antibody to optimize affinity for transition-state analog binding

Catalytic antibodies have shown great promise for catalyzing a tremendously diverse set of natural and unnatural chemical transformations. However, few catalytic antibodies have efficiencies that approach those of natural enzymes. In principle, random mutagenesis procedures such as phage display could be used to improve the catalytic activities of existing antibodies; however, these studies have been hampered by difficulties in the recombinant expression of antibodies. Here, we have grafted the antigen binding loops from a murine-derived catalytic antibody, 17E8, onto a human antibody framework in an effort to overcome difficulties associated with recombinant expression and phage display of this antibody. “Humanized” 17E8 retained similar catalytic and hapten binding properties as the murine antibody while levels of functional Fab displayed on phage were 200-fold higher than for a murine variable region/human constant region chimeric Fab. This construct was used to prepare combinatorial libraries. Affinity panning of these resulted in the selection of variants with 2- to 8-fold improvements in binding affinity for a phosphonate transition-state analog. Surprisingly, none of the affinity-matured variants was more catalytically active than the parent antibody and some were significantly less active. By contrast, a weaker binding variant was identified with 2-fold greater catalytic activity and incorporation of a single substitution (Tyr-100aH → Asn) from this variant into the parent antibody led to a 5-fold increase in catalytic efficiency. Thus, phage display methods can be readily used to optimize binding of catalytic antibodies to transition-state analogs, and when used in conjunction with limited screening for catalysis can identify variants with higher catalytic efficiencies.

Polyvalent binding to carbohydrates immobilized on an insoluble resin

Numerous studies have established that polyvalency is a critical feature of cell surface carbohydrate recognition. Nevertheless, carbohydrate–protein interactions are typically evaluated by using assays that focus on the behavior of monovalent carbohydrate ligands in solution. It has generally been assumed that the relative affinities of monovalent carbohydrate ligands in solution correlate with their polyvalent avidities. In this paper we show that carbohydrate ligands synthesized directly on TentaGel beads interact with carbohydrate-binding proteins in a polyvalent manner. The carbohydrate-derivatized beads can, therefore, be used as model systems for cell surfaces to evaluate polyvalent carbohydrate–protein interactions. By using a combinatorial approach to synthesize solid-phase libraries of polyvalent carbohydrates, one can rapidly address key issues in the area of cell surface carbohydrate recognition. For example, studies reported herein demonstrate that there is an unanticipated degree of specificity in recognition processes involving polyvalent carbohydrates. However, the correlation between polyvalent avidities and solution affinities is poor. Apparently, the presentation of carbohydrates on the polymer surface has a profound influence on the interaction of the ligand with the protein receptor. These findings have implications for how carbohydrates function as recognition signals in nature, as well as for how polyvalent carbohydrate–protein interactions should be studied.

Making chemistry selectable by linking it to infectivity

The link between recognition and replication is fundamental to the operation of the immune system. In recent years, modeling this process in a format of phage-display combinatorial libraries has afforded a powerful tool for obtaining valuable antibodies. However, the ability to readily select and isolate rare catalysts would expand the scope of library technology. A technique in which phage infection controlled the link between recognition and replication was applied to show that chemistry is a selectable process. An antibody that operated by covalent catalysis to form an acyl intermediate restored phage infectivity and allowed selection from a library in which the catalyst constituted 1 in 105 members. Three different selection approaches were examined for their convenience and generality. Incorporating these protocols together with well known affinity labels and mechanism-based inactivators should allow the procurement of a wide range of novel catalytic antibodies.

Protein–protein interactions among the Aux/IAA proteins

The plant hormone indoleacetic acid (IAA) transcriptionally activates early genes in plants. The Aux/IAA family of early genes encodes proteins that are short-lived and nuclear-localized. They also contain a putative prokaryotic βαα DNA binding motif whose formation requires protein dimerization. Here, we show that the pea PS-IAA4 and Arabidopsis IAA1 and IAA2 proteins perform homo- and heterotypic interactions in yeast using the two-hybrid system. Gel-filtration chromatography and chemical cross-linking experiments demonstrate that the PS-IAA4 and IAA1 proteins interact to form homodimers in vitro. Deletion analysis of PS-IAA4 indicates that the βαα containing acidic C terminus of the protein is necessary for homotypic interactions in the yeast two-hybrid system. Screening an Arabidopsis λ-ACT cDNA library using IAA1 as a bait reveals heterotypic interactions of IAA1 with known and newly discovered members of the Arabidopsis Aux/IAA gene family. The new member IAA24 has similarity to ARF1, a transcription factor that binds to an auxin response element. Combinatorial interactions among the various members of the Aux/IAA gene family may regulate a variety of late genes as well as serve as autoregulators of early auxin-regulated gene expression. These interactions provide a molecular basis for the developmental and tissue-specific manner of auxin action.

Synthesis and screening of small molecule libraries active in binding to DNA

Five synthetic combinatorial libraries of 2,080 components each were screened as mixtures for inhibition of DNA binding to two transcription factors. Rapid, solution-phase synthesis coupled to a gel-shift assay led to the identification of two compounds active at a 5- to 10-μM concentration level. The likely mode of inhibition is intercalation between DNA base pairs. The efficient deconvolution through sublibrary synthesis augurs well for the use of large mixtures of small, nonpeptide molecules in biological screens.

Molding a peptide into an RNA site by in vivo peptide evolution

Short peptides corresponding to the arginine-rich domains of several RNA-binding proteins are able to bind to their specific RNA sites with high affinities and specificities. In the case of the HIV-1 Rev-Rev response element (RRE) complex, the peptide forms a single α-helix that binds deeply in a widened, distorted RNA major groove and makes a substantial set of base-specific and backbone contacts. Using a reporter system based on antitermination by the bacteriophage λ N protein, it has been possible to identify novel arginine-rich peptides from combinatorial libraries that recognize the RRE with affinities and specificities similar to Rev but that appear to bind in nonhelical conformations. Here we have used codon-based mutagenesis to evolve one of these peptides, RSG-1, into an even tighter binder. After two rounds of evolution, RSG-1.2 bound the RRE with 7-fold higher affinity and 15-fold higher specificity than the wild-type Rev peptide, and in vitro competition experiments show that RSG-1.2 completely displaces the intact Rev protein from the RRE at low peptide concentrations. By fusing RRE-binding peptides to the activation domain of HIV-1 Tat, we show that the peptides can deliver Tat to the RRE site and activate transcription in mammalian cells, and more importantly, that the fusion proteins can inhibit the activity of Rev in chloramphenicol acetyltransferase reporter assays. The evolved peptides contain proline and glutamic acid mutations near the middle of their sequences and, despite the presence of a proline, show partial α-helix formation in the absence of RNA. These directed evolution experiments illustrate how readily complex peptide structures can be evolved within the context of an RNA framework, perhaps reflecting how early protein structures evolved in an “RNA world.”

A G protein γ subunit-like domain shared between RGS11 and other RGS proteins specifies binding to Gβ5 subunits

Regulators of G protein signaling (RGS) proteins act as GTPase-activating proteins (GAPs) toward the α subunits of heterotrimeric, signal-transducing G proteins. RGS11 contains a G protein γ subunit-like (GGL) domain between its Dishevelled/Egl-10/Pleckstrin and RGS domains. GGL domains are also found in RGS6, RGS7, RGS9, and the Caenorhabditis elegans protein EGL-10. Coexpression of RGS11 with different Gβ subunits reveals specific interaction between RGS11 and Gβ5. The expression of mRNA for RGS11 and Gβ5 in human tissues overlaps. The Gβ5/RGS11 heterodimer acts as a GAP on Gαo, apparently selectively. RGS proteins that contain GGL domains appear to act as GAPs for Gα proteins and form complexes with specific Gβ subunits, adding to the combinatorial complexity of G protein-mediated signaling pathways.

Inhibition of gene expression in human cells through small molecule-RNA interactions

Small molecules that bind their biological receptors with high affinity and selectivity can be isolated from randomized pools of combinatorial libraries. RNA-protein interactions are important in many cellular functions, including transcription, RNA splicing, and translation. One example of such interactions is the mechanism of trans-activation of HIV-1 gene expression that requires the interaction of Tat protein with the trans-activation responsive region (TAR) RNA, a 59-base stem-loop structure located at the 5′ end of all nascent HIV-1 transcripts. Here we demonstrate the isolation of small TAR RNA-binding molecules from an encoded combinatorial library. We have made an encoded combinatorial tripeptide library of 24,389 possible members from d-and l-alpha amino acids on TentaGel resin. Using on-bead screening we have identified a small family of mostly heterochiral tripeptides capable of structure-specific binding to the bulge loop of TAR RNA. In vitro binding studies reveal stereospecific discrimination when the best tripeptide ligand is compared with diastereomeric peptide sequences. In addition, the most strongly binding tripeptide was shown to suppress transcriptional activation by Tat protein in human cells with an IC50 of ≈50 nM. Our results indicate that tripeptide RNA ligands are cell permeable, nontoxic to cells, and capable of inhibiting expression of specific genes by interfering with RNA-protein interactions.

Synergistic inhibition of tumor growth in a murine mammary adenocarcinoma model by combinational gene therapy using IL-12, pro-IL-18, and IL-1β converting enzyme cDNA

We report here that a cancer gene therapy protocol using a combination of IL-12, pro-IL-18, and IL-1β converting enzyme (ICE) cDNA expression vectors simultaneously delivered via gene gun can significantly augment antitumor effects, evidently by generating increased levels of bioactive IL-18 and consequently IFN-γ. First, we compared the levels of IFN-γ secreted by mouse splenocytes stimulated with tumor cells transfected with various test genes, including IL-12 alone; pro-IL-18 alone; pro-IL-18 and ICE; IL-12 and pro-IL-18; and IL-12, pro-IL-18, and ICE. Among these treatments, the combination of IL-12, pro-IL-18, and ICE cDNA resulted in the highest level of IFN-γ production from splenocytes in vitro, and similar results were obtained when these same treatments were delivered to the skin of a mouse by gene gun and IFN-γ levels were measured at the skin transfection site in vivo. Furthermore, the triple gene combinatorial gene therapy protocol was the most effective among all tested groups at suppressing the growth of TS/A (murine mammary adenocarcinoma) tumors previously implanted intradermally at the skin site receiving DNA transfer by gene gun on days 6, 8, 10, and 12 after tumor implantation. Fifty percent of mice treated with the combined three-gene protocol underwent complete tumor regression. In vivo depletion experiments showed that this antitumor effect was CD8+ T cell-mediated and partially IFN-γ-dependent. These results suggest that a combinatorial gene therapy protocol using a mixture of IL-12, pro-IL-18, and ICE cDNAs can confer potent antitumor activities against established TS/A tumors via cytotoxic CD8+ T cells and IFN-γ-dependent pathways.