A construction of cylindric and polyadic algebras from atomic relation algebras

Given a simple atomic relation algebra ${\mathcal{A}}$ and a finite n ?? 3, we construct effectively an atomic n-dimensional polyadic equality-type algebra ${\mathcal{P}}$ such that for any subsignature L of the signature of ${\mathcal{P}}$ that contains the boolean operations and cylindrifications, the L-reduct of ${\mathcal{P}}$ is completely representable if and only if ${\mathcal{A}}$ is completely representable. If ${\mathcal{A}}$ is finite then so is ${\mathcal{P}}$ . It follows that there is no algorithm to determine whether a finite n-dimensional cylindric algebra, diagonal-free cylindric algebra, polyadic algebra, or polyadic equality algebra is representable (for diagonal-free algebras this was known). We also obtain a new proof that the classes of completely representable n-dimensional algebras of these types are non-elementary, a result that remains true for infinite dimensions if the diagonals are present, and also for infinite-dimensional diagonal-free cylindric algebras.     

Axiomatizing complex algebras by games

Given a variety , we provide an axiomatization of the class of complex algebras of algebras in . can be obtained effectively from the axiomatization of ; in fact, if this axiomatization is recursively enumerable, then is recursive. Received January 18, 2000; accepted in final form December 18, 2000.     

Specificity and affinity of natural product cyclopentapeptide inhibitors against A. fumigatus, human, and bacterial chitinases

Family 18 chitinases play key roles in organisms ranging from bacteria to man. There is a need for specific, potent inhibitors to probe the function of these chitinases in different organisms. Such molecules could also provide leads for the development of chemotherapeuticals with fungicidal, insecticidal, or anti-inflammatory potential. Recently, two natural product peptides, argifin and argadin, have been characterized, which structurally mimic chitinase-chitooligosaccharide interactions and inhibit a bacterial chitinase in the nM-mM range. Here, we show that these inhibitors also act on human and Aspergillus fumigatus chitinases. The structures of these enzymes in complex with argifin and argadin, together with mutagenesis, fluorescence, and enzymology, reveal that subtle changes in the binding site dramatically affect affinity and selectivity. The data show that it may be possible to develop specific chitinase inhibitors based on the argifin/argadin scaffolds.     

HDX-ESI-MS reveals enhanced conformational dynamics of the amyloidogenic protein β 2-microglobulin upon release from the MHC-1

The light chain of the major histocompatibility complex class 1 (MHC-1), the protein β ₂-microglobulin (β ₂m), has amyloidogenic properties that arise only upon its dissociation from the MHC-1. Here hydrogen/deuterium exchange electrospray ionization mass spectrometry (HDX-ESI-MS) has been used to compare the solution dynamics of β ₂m in its MHC-1 bound state compared with those of β ₂m as a free monomer. The capability of tandem mass spectrometry to dissociate the MHC-1 into its individual constituents in the gas phase following deuterium incorporation in solution has permitted the direct observation of the exchange properties of MHC-1 bound β ₂m for the first time. The HDX-ESI-MS data show clearly that the H→D exchange of MHC-1 bound β ₂m follows EX2 kinetics and that about 20 protons remain protected from exchange after 17 days. Free from the MHC-1, monomeric β ₂m exhibits significantly different HDX behavior, which encompasses both EX1 and EX2 kinetics. The EX2 kinetics indicate a tenfold increase in the rate of exchange compared with MHC-1 bound β ₂m, with just 10 protons remaining protected from EX2 exchange and therefore exchanging only via the EX1 mechanism. The EX1 kinetics observed for unbound β ₂m are consistent with unfolding of its exchange-protected core with a t_1/2 of 68 min (pH 7, 37° C). Thus, upon dissociation from the stabilizing influence of the MHC-1, free β ₂m becomes highly dynamic and undergoes unfolding transitions that result in an aggregation-competent protein.     

Representability is not decidable for finite relation algebras

We prove that there is no algorithm that decides whether a finite relation algebra is representable.

Representability of a finite relation algebra is determined by playing a certain two player game over `atomic -networks'. It can be shown that the second player in this game has a winning strategy if and only if is representable.

Let be a finite set of square tiles, where each edge of each tile has a colour. Suppose includes a special tile whose four edges are all the same colour, a colour not used by any other tile. The tiling problem we use is this: is it the case that for each tile there is a tiling of the plane using only tiles from in which edge colours of adjacent tiles match and with placed at ? It is not hard to show that this problem is undecidable.

From an instance of this tiling problem , we construct a finite relation algebra and show that the second player has a winning strategy in if and only if is a yes-instance. This reduces the tiling problem to the representation problem and proves the latter's undecidability.