Structural and functional analysis of two universal stress proteins YdaA and YnaF from Salmonella typhimurium: possible roles in microbial stress tolerance

In many organisms ``Universal Stress Proteins'' CUSPS) are induced in response to a variety of environmental stresses. Here we report the structures of two USPs, YnaF and YdaA from Salmonella typhimurium determined at 1.8 angstrom and 2.4 angstrom resolutions, respectively. YnaF consists of a single USP domain and forms a tetrameric organization stabilized by interactions mediated through chloride ions. YdaA is a larger protein consisting of two tandem USP domains. Two protomers of YdaA associate to form a structure similar to the YnaF tetramer. YdaA showed ATPase activity and an ATP binding motif G-2X-G-9X-G(S/T/N) was found in its C-terminal domain. The residues corresponding to this motif were not conserved in YnaF although YnaF could bind ATP. However, unlike YdaA, YnaF did not hydrolyse ATP in vitro. Disruption of interactions mediated through chloride ions by selected mutations converted YnaF into an ATPase. Residues that might be important for ATP hydrolysis could be identified by comparing the active sites of native and mutant structures. Only the C-terminal domain of YdaA appears to be involved in ATP hydrolysis. The structurally similar N-terminal domain was found to bind a zinc ion near the segment equivalent to the phosphate binding loop of the C-terminal domain. Mass spectrometric analysis showed that YdaA might bind a ligand of approximate molecular weight 800 daltons. Structural comparisons suggest that the ligand, probably related to an intermediate in lipid A biosynthesis, might bind at a site close to the zinc ion. Therefore, the N-terminal domain of YdaA binds zinc and might play a role in lipid metabolism. Thus, USPs appear to perform several distinct functions such as ATP hydrolysis, altering membrane properties and chloride sensing. (C) 2015 Elsevier Inc. All rights reserved.

Rainbow matchings in strongly edge-colored graphs

A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree 3(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f (delta(G)) vertices is guaranteed to contain a rainbow matching of size delta(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k) = 4k - 4, for k >= 4 and f (k) = 4k - 3, for k <= 3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4 delta(G) - 4 vertices. Strong edge-coloring of a graph G is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph Gin terms of delta(G). We show that for a strongly edge-colored graph G, if |V(G)| >= 2 |3 delta(G)/4|, then G has a rainbow matching of size |3 delta(G)/4|, and if |V(G)| < 2 |3 delta(G)/4|, then G has a rainbow matching of size |V(G)|/2] In addition, we prove that if G is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least delta(G). (C) 2015 Elsevier B.V. All rights reserved.

SEPARATION DIMENSION OF BOUNDED DEGREE GRAPHS

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in R-k such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Theta(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 2(9) (log*d)d. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least d/2]

Boxicity and cubicity of product graphs

The boxicity (cubicity) of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in R-k. In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of d, of the boxicity and the cubicity of the dth power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the dth Cartesian power of any given finite graph is, respectively, in O(log d/ log log d) and circle dot(d/ log d). On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products. (C) 2015 Elsevier Ltd. All rights reserved.

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by v(G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be 2v(G)/3]. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least v(G) - 1, if 1 <= v(G) <= 7, and at least 3v(G)/5] + 1 if v(G) >= 8. They conjectured that the tight lower bound would be v(G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if v(G) >= 8, then G contains a heterochromatic path of length at least 120 + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least v(G) - o(v(G)) and if the girth of G is at least 4 log(2)(v(G)) + 2, then it contains a heterochromatic path of length at least v(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of 5v(G)/6] and for bipartite graphs we obtain a lower bound of 6v(G)-3/7]. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least 13v(G)/17)]. This improves the previously known 3v(G)/4] bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least (C) 2015 Elsevier Ltd. All rights reserved.

A Universal Stress Protein (USP) in Mycobacteria Binds cAMP

Mycobacteria are endowed with rich and diverse machinery for the synthesis, utilization, and degradation of cAMP. The actions of cyclic nucleotides are generally mediated by binding of cAMP to conserved and well characterized cyclic nucleotide binding domains or structurally distinct cGMP-specific and -regulated cyclic nucleotide phosphodiesterase, adenylyl cyclase, and E. coli transcription factor FhlA (GAF) domain-containing proteins. Proteins with cyclic nucleotide binding and GAF domains can be identified in the genome of mycobacterial species, and some of them have been characterized. Here, we show that a significant fraction of intracellular cAMP is bound to protein in mycobacterial species, and by using affinity chromatography techniques, we identify specific universal stress proteins (USP) as abundantly expressed cAMP-binding proteins in slow growing as well as fast growing mycobacteria. We have characterized the biochemical and thermodynamic parameters for binding of cAMP, and we show that these USPs bind cAMP with a higher affinity than ATP, an established ligand for other USPs. We determined the structure of the USP MSMEG_3811 bound to cAMP, and we confirmed through structure-guided mutagenesis, the residues important for cAMP binding. This family of USPs is conserved in all mycobacteria, and we suggest that they serve as ``sinks'' for cAMP, making this second messenger available for downstream effectors as and when ATP levels are altered in the cell.

Cross-section fluctuations in open microwave billiards and quantum graphs: The counting-of-maxima method revisited

The fluctuations exhibited by the cross sections generated in a compound-nucleus reaction or, more generally, in a quantum-chaotic scattering process, when varying the excitation energy or another external parameter, are characterized by the width Gamma(corr) of the cross-section correlation function. Brink and Stephen Phys. Lett. 5, 77 (1963)] proposed a method for its determination by simply counting the number of maxima featured by the cross sections as a function of the parameter under consideration. They stated that the product of the average number of maxima per unit energy range and Gamma(corr) is constant in the Ercison region of strongly overlapping resonances. We use the analogy between the scattering formalism for compound-nucleus reactions and for microwave resonators to test this method experimentally with unprecedented accuracy using large data sets and propose an analytical description for the regions of isolated and overlapping resonances.

On Locally Gabriel Geometric Graphs

Let be a set of points in the plane. A geometric graph on is said to be locally Gabriel if for every edge in , the Euclidean disk with the segment joining and as diameter does not contain any points of that are neighbors of or in . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any , there exists LGG with edges. This improves upon the previous best bound of . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any point set, there exists an independent set of size .

Separation index of graphs and stacked 2-spheres

In 1987, Kalai proved that stacked spheres of dimension d >= 3 are characterised by the fact that they attain equality in Barnette's celebrated Lower Bound Theorem. This result does not extend to dimension d = 2. In this article, we give a characterisation of stacked 2-spheres using what we call the separation index. Namely, we show that the separation index of a triangulated 2-sphere is maximal if and only if it is stacked. In addition, we prove that, amongst all n-vertex triangulated 2-spheres, the separation index is minimised by some n-vertex flag sphere for n >= 6. Furthermore, we apply this characterisation of stacked 2-spheres to settle the outstanding 3-dimensional case of the Lutz-Sulanke-Swartz conjecture that ``tight-neighbourly triangulated manifolds are tight''. For dimension d >= 4, the conjecture has already been proved by Effenberger following a result of Novik and Swartz. (C) 2015 Elsevier Inc. All rights reserved.

Universal Hashing for Information-Theoretic Security

The information-theoretic approach to security entails harnessing the correlated randomness available in nature to establish security. It uses tools from information theory and coding and yields provable security, even against an adversary with unbounded computational power. However, the feasibility of this approach in practice depends on the development of efficiently implementable schemes. In this paper, we review a special class of practical schemes for information-theoretic security that are based on 2-universal hash families. Specific cases of secret key agreement and wiretap coding are considered, and general themes are identified. The scheme presented for wiretap coding is modular and can be implemented easily by including an extra preprocessing layer over the existing transmission codes.

Universal buckling kinetics in drying nanoparticle-laden droplets on a hydrophobic substrate

We provide a comprehensive physical description of the vaporization, self-assembly, agglomeration, and buckling kinetics of sessile nanofluid droplets pinned on a hydrophobic substrate. We have deciphered five distinct regimes of the droplet life cycle. Regimes I-III consists of evaporation-induced preferential agglomeration that leads to the formation of a unique dome-shaped inhomogeneous shell with a stratified varying-density liquid core. Regime IV involves capillary-pressure-initiated shell buckling and stress-induced shell rupture. Regime V marks rupture-induced cavity inception and growth. We demonstrate through scaling arguments that the growth of the cavity (which controls the final morphology or structure) can be described by a universal function.

Universal anomalous dimensions at large spin and large twist

In this paper we consider anomalous dimensions of double trace operators at large spin (l) and large twist (tau) in CFTs in arbitrary dimensions (d >= 3). Using analytic conformal bootstrap methods, we show that the anomalous dimensions are universal in the limit l >> tau >> 1. In the course of the derivation, we extract an approximate closed form expression for the conformal blocks arising in the four point function of identical scalars in any dimension. We compare our results with two different calculations in holography and find perfect agreement.

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.