Orthogonal MCMC algorithms

Monte Carlo (MC) methods are widely used in signal processing, machine learning and stochastic optimization. A well-known class of MC methods are Markov Chain Monte Carlo (MCMC) algorithms. In this work, we introduce a novel parallel interacting MCMC scheme, where the parallel chains share information using another MCMC technique working on the entire population of current states. These parallel ?vertical? chains are led by random-walk proposals, whereas the ?horizontal? MCMC uses a independent proposal, which can be easily adapted by making use of all the generated samples. Numerical results show the advantages of the proposed sampling scheme in terms of mean absolute error, as well as robustness w.r.t. to initial values and parameter choice.

Vector Boolean Functions: Applications in Symmetric Cryptography

Esta tesis establece los fundamentos teóricos y diseña una colección abierta de clases C++ denominada VBF (Vector Boolean Functions) para analizar funciones booleanas vectoriales (funciones que asocian un vector booleano a otro vector booleano) desde una perspectiva criptográfica. Esta nueva implementación emplea la librería NTL de Victor Shoup, incorporando nuevos módulos que complementan a las funciones de NTL, adecuándolas para el análisis criptográfico. La clase fundamental que representa una función booleana vectorial se puede inicializar de manera muy flexible mediante diferentes estructuras de datas tales como la Tabla de verdad, la Representación de traza y la Forma algebraica normal entre otras. De esta manera VBF permite evaluar los criterios criptográficos más relevantes de los algoritmos de cifra en bloque y de stream, así como funciones hash: por ejemplo, proporciona la no-linealidad, la distancia lineal, el grado algebraico, las estructuras lineales, la distribución de frecuencias de los valores absolutos del espectro Walsh o del espectro de autocorrelación, entre otros criterios. Adicionalmente, VBF puede llevar a cabo operaciones entre funciones booleanas vectoriales tales como la comprobación de igualdad, la composición, la inversión, la suma, la suma directa, el bricklayering (aplicación paralela de funciones booleanas vectoriales como la empleada en el algoritmo de cifra Rijndael), y la adición de funciones coordenada. La tesis también muestra el empleo de la librería VBF en dos aplicaciones prácticas. Por un lado, se han analizado las características más relevantes de los sistemas de cifra en bloque. Por otro lado, combinando VBF con algoritmos de optimización, se han diseñado funciones booleanas cuyas propiedades criptográficas son las mejores conocidas hasta la fecha. ABSTRACT This thesis develops the theoretical foundations and designs an open collection of C++ classes, called VBF, designed for analyzing vector Boolean functions (functions that map a Boolean vector to another Boolean vector) from a cryptographic perspective. This new implementation uses the NTL library from Victor Shoup, adding new modules which complement the existing ones making VBF better suited for cryptography. The fundamental class representing a vector Boolean function can be initialized in a flexible way via several alternative types of data structures such as Truth Table, Trace Representation, Algebraic Normal Form (ANF) among others. This way, VBF allows the evaluation of the most relevant cryptographic criteria for block and stream ciphers as well as for hash functions: for instance, it provides the nonlinearity, the linearity distance, the algebraic degree, the linear structures, the frequency distribution of the absolute values of the Walsh Spectrum or the Autocorrelation Spectrum, among others. In addition, VBF can perform operations such as equality testing, composition, inversion, sum, direct sum, bricklayering (parallel application of vector Boolean functions as employed in Rijndael cipher), and adding coordinate functions of two vector Boolean functions. This thesis also illustrates the use of VBF in two practical applications. On the one hand, the most relevant properties of the existing block ciphers have been analysed. On the other hand, by combining VBF with optimization algorithms, new Boolean functions have been designed which have the best known cryptographic properties up-to-date.

Estimation of Symmetric Channels for Discrete Cosine Transform Type-I Multicarrier Systems: A Compressed Sensing Approach

The problem of channel estimation for multicarrier communications is addressed. We focus on systems employing the Discrete Cosine Transform Type-I (DCT1) even at both the transmitter and the receiver, presenting an algorithm which achieves an accurate estimation of symmetric channel filters using only a small number of training symbols. The solution is obtained by using either matrix inversion or compressed sensing algorithms. We provide the theoretical results which guarantee the validity of the proposed technique for the DCT1. Numerical simulations illustrate the good behaviour of the proposed algorithm.

Bivariate Krawtchouk polynomials: Inversion and connection problems with the NAVIMA algorithm

In this paper we present a recurrent procedure to solve an inversion problem for monic bivariate Krawtchouk polynomials written in vector column form, giving its solution explicitly. As a by-product, a general connection problem between two vector column of monic bivariate Krawtchouk families is also explicitly solved. Moreover, in the non monic case and also for Krawtchouk families, several expansion formulas are given, but for polynomials written in scalar form.

Hyers–Ulam stability of functional equations with a square-symmetric operation

The stability of the functional equation f(x ○ y) = H(f(x), f(y)) (x, y ∈ S) is investigated, where H is a homogeneous function and ○ is a square-symmetric operation on the set S. The results presented include and generalize the classical theorem of Hyers obtained in 1941 on the stability of the Cauchy functional equation.

Double-level “orthogonal” dynamic combinatorial libraries on transition metal template

Dynamic combinatorial libraries are mixtures of compounds that exist in a dynamic equilibrium and can be driven to compositional self adaptation via selective binding of a specific assembly of certain components to a molecular target. We present here an extension of this initial concept to dynamic libraries that consists of two levels, the first formed by the coordination of terpyridine-based ligands to the transition metal template, and the second, by the imine formation with the aldehyde substituents on the terpyridine moieties. Dialdehyde 7 has been synthesized, converted into a variety of ligands, oxime ethers L11–L33 and acyl hydrazones L44–L77, and subsequently into corresponding cobalt complexes. A typical complex, Co(L22)22+ is shown to engage in rapid exchange with a competing ligand L11 and with another complex, Co(L22)22+ in 30% acetonitrile/water at pH 7.0 and 25°C. The exchange in the corresponding Co(III) complexes is shown to be much slower. Imine exchange in the acyl hydrazone complexes (L44–L77) is strongly controlled by pH and temperature. The two types of exchange, ligand and imine, can thus be used as independent equilibrium processes controlled by different types of external intervention, i.e., via oxidation/reduction of the metal template and/or change in the pH/temperature of the medium. The resulting double-level dynamic libraries are therefore named orthogonal, in similarity with the orthogonal protecting groups in organic synthesis. Sample libraries of this type have been synthesized and showed the complete expected set of components in electrospray ionization MS.

Orthogonal combinatorial mutagenesis: a codon-level combinatorial mutagenesis method useful for low multiplicity and amino acid-scanning protocols

We describe here a method to generate combinatorial libraries of oligonucleotides mutated at the codon-level, with control of the mutagenesis rate so as to create predictable binomial distributions of mutants. The method allows enrichment of the libraries with single, double or larger multiplicity of amino acid replacements by appropriate choice of the mutagenesis rate, depending on the concentration of synthetic precursors. The method makes use of two sets of deoxynucleoside-phosphoramidites bearing orthogonal protecting groups [4,4′-dimethoxytrityl (DMT) and 9-fluorenylmethoxycarbonyl (Fmoc)] in the 5′ hydroxyl. These phosphoramidites are divergently combined during automated synthesis in such a way that wild-type codons are assembled with commercial DMT-deoxynucleoside-methyl-phosphoramidites while mutant codons are assembled with Fmoc-deoxynucleoside-methyl-phosphoramidites in an NNG/C fashion in a single synthesis column. This method is easily automated and suitable for low mutagenesis rates and large windows, such as those required for directed evolution and alanine scanning. Through the assembly of three oligonucleotide libraries at different mutagenesis rates, followed by cloning at the polylinker region of plasmid pUC18 and sequencing of 129 clones, we concluded that the method performs essentially as intended.

A positivity result in the theory of Macdonald polynomials

We outline here a proof that a certain rational function Cn(q, t), which has come to be known as the “q, t-Catalan,” is in fact a polynomial with positive integer coefficients. This has been an open problem since 1994. Because Cn(q, t) evaluates to the Catalan number at t = q = 1, it has also been an open problem to find a pair of statistics a, b on the collection

Introduction of asymmetry in the naturally symmetric restriction endonuclease EcoRV to investigate intersubunit communication in the homodimeric protein.

Type II restriction endonucleases are dimers of two identical subunits that together form one binding site for the double-stranded DNA substrate. Cleavage within the palindromic recognition site occurs in the two strands of the duplex in a concerted manner, due to the action of two catalytic centers, one per subunit. To investigate how the two identical subunits of the restriction endonuclease EcoRV cooperate in binding and cleaving their substrate, heterodimeric versions of EcoRV with different amino acid substitutions in the two subunits were constructed. For this purpose, the ecorV gene was fused to the coding region for the glutathione-binding domain of the glutathione S-transferase and a His6-tag, respectively. Upon cotransformation of Escherichia coli cells with both gene fusions stable homo- and heterodimers of the EcoRV variants are produced, which can be separated and purified to homogeneity by affinity chromatography over Ni-nitrilotriacetic acid and glutathione columns. A steady-state kinetic analysis shows that the activity of a heterodimeric variant with one inactive catalytic center is decreased by 2-fold, demonstrating that the two catalytic centers operate independently from each other. In contrast, heterodimeric variants with a defect in one DNA-binding site have a 30- to 50-fold lower activity, indicating that the two subunits of EcoRV cooperate in the recognition of the palindromic DNA sequence. By combining a subunit with an inactive catalytic center with a subunit with a defect in the DNA-binding site, EcoRV heterodimers were produced that only nick DNA specifically within the EcoRV recognition sequence.

Local densities orthogonal to beta-sheet amide planes: patterns of packing in globular proteins.

We have investigated the efficiency of packing by calculating intramolecular packing density above and below peptide planes of internal beta-pleated sheet residues in five globular proteins. The orientation of interest was chosen to allow study of regions that are approximately perpendicular to the faces of beta-pleated sheets. In these locations, nonbonded van der Waals packing interactions predominate over hydrogen bonding and solvent interactions. We observed considerable variability in packing densities within these regions, confirming that the interior packing of a protein does not result in uniform occupation of the available space. Patterns of fluctuation in packing density suggest that the regular backbone-to-backbone network of hydrogen bonds is not likely to be interrupted to maximize van der Waals interactions. However, high-density packing tends to occur toward the ends of beta-structure strands where hydrogen bonds are more likely to involve nonpolar side-chain groups or solvent molecules. These features result in internal protein folding with a central low-density core surrounded by a higher-density subsurface shell, consistent with our previous calculations regarding overall protein packing density.

The protein-folding activity of chaperonins correlates with the symmetric GroEL14(GroES7)2 heterooligomer.

Chaperonins GroEL and GroES form, in the presence of ATP, two types of heterooligomers in solution: an asymmetric GroEL14GroES7 "bullet"-shaped particle and a symmetric GroEL14(GroES7)2 "football"-shaped particle. Under limiting concentrations of ATP or GroES, excess ADP, or in the presence of 5'-adenylyl imidodiphosphate, a correlation is seen between protein folding and the amount of symmetric GroEL14(GroES7)2 particles in a chaperonin solution, as detected by electron microscopy or by chemical crosslinking. Kinetic analysis suggests that protein folding is more efficient when carried out by a chaperonin solution populated with a majority of symmetric GroEL14(GroES7)2 particles than by a majority of asymmetric GroEL14GroES7 particles. The symmetric heterooligomer behaves as a highly efficient intermediate of the chaperonin protein folding cycle in vitro.

Peptide synthesis using unprotected peptides through orthogonal coupling methods.

We describe an approach to the synthesis of peptides from segments bearing no protecting groups through an orthogonal coupling method to capture the acyl segment as a thioester that then undergoes an intramolecular acyl transfer to the amine component with formation of a peptide bond. Two orthogonal coupling methods to give the covalent ester intermediate were achieved by either a thiol-thioester exchange mediated by a trialkylphosphine and an alkylthiol or a thioesterification by C alpha-thiocarboxylic acid reacting with a beta-bromo amino acid. With this approach, unprotected segments ranging from 4 to 37 residues were coupled to aqueous solution to give free peptides up to 54 residues long with high efficiency.

Bidirectional motion observed in the compact symmetric object 1946+708.

We present the first direct measurements of bidirectional motions in an extragalactic radio jet. The radio source 1946+708 is a compact symmetric object with striking S-symmetry identified with a galaxy at a redshift of 0.101. From observations 2 years apart we have determined the velocities of four compact components in the jet, the fastest of which has an apparent velocity of 1.09 h-1c. By pairing up the components, assuming they were simultaneously ejected in opposite directions, we derive a 1 lower limit on the Hubble constant, H0 > 42 km.s-1.Mpc-1.

Robust fitting of Zernike polynomials to noisy point clouds defined over connected domains of arbitrary shape

A new method for fitting a series of Zernike polynomials to point clouds defined over connected domains of arbitrary shape defined within the unit circle is presented in this work. The method is based on the application of machine learning fitting techniques by constructing an extended training set in order to ensure the smooth variation of local curvature over the whole domain. Therefore this technique is best suited for fitting points corresponding to ophthalmic lenses surfaces, particularly progressive power ones, in non-regular domains. We have tested our method by fitting numerical and real surfaces reaching an accuracy of 1 micron in elevation and 0.1 D in local curvature in agreement with the customary tolerances in the ophthalmic manufacturing industry.

E-polynomials of the SL(2, C)-character varieties of surface groups

We compute the E-polynomials of the moduli spaces of representations of the fundamental group of a once-punctured surface of any genus into SL(2, C), for any possible holonomy around the puncture. We follow the geometric technique introduced in [12], based on stratifying the space of representations, and on the analysis of the behavior of the E-polynomial under fibrations.