Conflict-Free Coloring for Rectangle Ranges Using O(n.382) Colors

Given a set of points P ⊆ R2, a conflict-free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each nonempty axisparallel rectangle T in the plane contains a point whose color is distinct from all other points in P ∩ T . This notion has been the subject of recent interest and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to base stations (points) such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R2 can be conflict-free colored with O(nβ∗+o(1)) colors in expected polynomial time, where β∗ = 3−√5 2 < 0.382.

Determination of C-13 Chemical Shift Anisotropy Tensors and Molecular Order of 4-Hexyloxybenzoic Acid

4-Alkoxy benzoic acids belong to an important class of thermotropic liquid crystals that are structurally simple and often used as starting materials for many novel mesogens. 4-Hexyloxybenzoic acid (HBA) is a homologue of the same series and exhibits an enantiotropic nematic phase. As this molecule could serve as an ideal model compound, high resolution C-13 NMR studies of HEA in solution, solid, and liquid crystalline phases have been undertaken. In the solid state, two-dimensional separation of undistorted powder patterns by effortless recoupling (2D SUPER) experiments have been carried out to estimate the magnitude of the components of the chemical shift anisotropy (GSA) tensor of all the aromatic carbons. These values have been used subsequently for calculating the orientational order parameters in the liquid crystalline phase. The GSA values computed by density functional theory (DFT) calculations showed good agreement with the 2D SUPER values. Additionally, C-13-H-1 dipolar couplings in the nematic phase have been determined by separated local field (SLF) spectroscopy at various temperatures and were used for computing the order parameters, which compared well with those calculated by using the chemical shifts. It is anticipated that the CSA values determined for MBA would be useful for the assignment of carbon chemical shifts and for the study of order and dynamics of structurally similar novel mesogens in their nematic phases.

Phonon anomalies and structural transition in spin ice Dy2Ti2O7: a simultaneous pressure-dependent and temperature-dependent Raman study

We revisit the assignment of Raman phonons of rare-earth titanates by performing Raman measurements on single crystals of O18 isotope-rich spin ice Dy2Ti2O718 and nonmagnetic Lu2Ti2O718 pyrochlores and compare the results with their O16 counterparts. We show that the low-wavenumber Raman modes below 250 cm-1 are not due to oxygen vibrations. A mode near 200 cm-1, commonly assigned as F2g phonon, which shows highly anomalous temperature dependence, is now assigned to a disorder-induced Raman active mode involving Ti4+ vibrations. Moreover, we address here the origin of the new Raman mode, observed below TC similar to 110 K in Dy2Ti2O7, through a simultaneous pressure-dependent and temperature-dependent Raman study. Our study confirms the new mode to be a phonon mode. We find that dTC/dP = + 5.9 K/GPa. Temperature dependence of other phonons has also been studied at various pressures up to similar to 8 GPa. We find that pressure suppresses the anomalous temperature dependence. The role of the inherent vacant sites present in the pyrochlore structure in the anomalous temperature dependence is also discussed. Copyright (c) 2012 John Wiley & Sons, Ltd.

NMR Analysis of Cross Strand Aromatic Interactions in an 8 Residue Hairpin and a 14 Residue Three Stranded beta-Sheet Peptide

Cross strand aromatic interactions between a facing pair of phenylalanine residues in antiparallel beta-sheet structures have been probed using two structurally defined model peptides. The octapeptide Boc-(LFVPPLFV)-P-D-P-L-OMe (peptide 1) favors the beta-hairpin conformation nucleated by the type II' beta-turn formed by the (D)Pro-(L)Pro segment, placing Phe2 and Phe7 side chains in proximity. Two centrally positioned (D)Pro-(L)Pro segments facilitate the three stranded beta-sheet formation in the 14 residue peptide Boc-LFV(D)P(L)PLFVA(D)P(L)PLFV-OMe (peptide 2) in which the Phe2/Phe7 orientations are similar to that in the octapeptide. The anticipated folded conformations of peptides 1 and 2 are established by the delineation of intramolecularly hydrogen bonded NH groups and by the observation of specific cross strand NOEs. The observation of ring current shifted aromatic protons is a diagnostic of close approach of the Phe2 and Phe7 side chains. Specific assignment of aromatic proton resonances using HSQC and HSQC-TOCSY methods allow an analysis of interproton NOEs between the spatially proximate aromatic rings. This approach facilitates specific assignments in systems containing multiple aromatic rings in spectra at natural abundance. Evidence is presented for a dynamic process which invokes a correlated conformational change about the C-alpha-C-beta(chi(1)) bond for the pair of interacting Phe residues. NMR results suggest that aromatic ring orientations observed in crystals are maintained in solution. Anomalous temperature dependence of ring current induced proton chemical shifts suggests that solvophobic effects may facilitate aromatic ring clustering in apolar solvents.

Intermolecular charge transfer and vibrational analysis of hydrogen bonding in acetazolamide

In the present work the structural and spectral characteristics of acetazolamide have been studied by methods of infrared, Raman spectroscopy and quantum chemistry. Electrostatic potential surface, optimized geometry, harmonic vibrational frequencies, infrared intensities and activities of Raman scattering were calculated by density functional theory (DFT) employing B3LYP with complete relaxation in the potential energy surface using 6-311++G(d,p) basis set. Based on these results, we have discussed the correlation between the vibrational modes and the structure of the dimers of acetazolamide. The calculated vibrational spectra of three dimers of acetazolamide have been compared with observed spectra, and the assignment of observed bands was carried out using potential energy distribution. The observed spectra agree well with the values computed from the OFT. A comparison of observed and calculated vibrational spectra clearly shows the effect of hydrogen bonding. The frequency shifts observed for the different dimers are in accord with the hydrogen bonding in acetazolamide. Natural bond orbital (NBO) analyses reflect the charge transfer interaction in the individual hydrogen bond units and the stability of different dimers of acetazolamide. (C) 2012 Elsevier B.V. All rights reserved.

Chiral discrimination and the measurement of enantiomeric excess from a severely overcrowded NMR spectrum

NMR spectroscopic chiral visualization, unambiguous assignment of peaks pertaining to R and S enantiomers and the subsequent measurement of enantiomeric composition demands a highly resolved spectrum. The method fails when the spectrum is severely overcrowded or highly complex, thereby hampering the determination of enantiomeric excess. In order to circumvent such problems we propose the utility of pure shift spectrum obtained by resolving the chemical shift and coupling information in two orthogonal dimensions. The skew projected spectrum yields singlet's at the respective chemical shift positions, permitting the unravelling of the superimposed spectral transitions for each enantiomer and measurement of enantiomeric composition. (C) 2012 Elsevier B. V. All rights reserved.

Dynamic mechanism design for markets with strategic resources

The assignment of tasks to multiple resources becomes an interesting game theoretic problem, when both the task owner and the resources are strategic. In the classical, nonstrategic setting, where the states of the tasks and resources are observable by the controller, this problem is that of finding an optimal policy for a Markov decision process (MDP). When the states are held by strategic agents, the problem of an efficient task allocation extends beyond that of solving an MDP and becomes that of designing a mechanism. Motivated by this fact, we propose a general mechanism which decides on an allocation rule for the tasks and resources and a payment rule to incentivize agents' participation and truthful reports. In contrast to related dynamic strategic control problems studied in recent literature, the problem studied here has interdependent values: the benefit of an allocation to the task owner is not simply a function of the characteristics of the task itself and the allocation, but also of the state of the resources. We introduce a dynamic extension of Mezzetti's two phase mechanism for interdependent valuations. In this changed setting, the proposed dynamic mechanism is efficient, within period ex-post incentive compatible, and within period ex-post individually rational.

Rapid mass spectrometric determination of disulfide connectivity in peptides and proteins

Disulfide crosslinks are ubiquitous in natural peptides and proteins, providing rigidity to polypeptide scaffolds. The assignment of disulfide connectivity in multiple crosslinked systems is often difficult to achieve. Here, we show that rapid unambiguous characterisation of disulfide connectivity can be achieved through direct mass spectrometric CID fragmentation of the disulfide intact polypeptides. The method requires a direct mass spectrometric fragmentation of the native disulfide bonded polypeptides and subsequent analysis using a newly developed program, DisConnect. Technical difficulties involving direct fragmentation of proteins are surmounted by an initial proteolytic nick and subsequent determination of the structures of these proteolytic peptides through DisConnect. While the connectivity in proteolytic fragments containing one cystine is evident from the MS profile alone, those with multiple cystines are subjected to subsequent mass spectrometric fragmentation. The wide applicability of this method is illustrated using examples of peptide hormones, peptide toxins, proteins, and disulfide foldamers of a synthetic analogue of a marine peptide toxin. The method, coupled with DisConnect, provides an unambiguous, straightforward approach, especially useful for the rapid screening of the disulfide crosslink fidelity in recombinant proteins, determination of disulfide linkages in natural peptide toxins and characterization of folding intermediates encountered in oxidative folding pathways.

En Masse relay selection algorithms for multi-source, multi-relay, decode-and-forward cooperative systems

Opportunistic relay selection in a multiple source-destination (MSD) cooperative system requires quickly allocating to each source-destination (SD) pair a suitable relay based on channel gains. Since the channel knowledge is available only locally at a relay and not globally, efficient relay selection algorithms are needed. For an MSD system, in which the SD pairs communicate in a time-orthogonal manner with the help of decode-and-forward relays, we propose three novel relay selection algorithms, namely, contention-free en masse assignment (CFEA), contention-based en masse assignment (CBEA), and a hybrid algorithm that combines the best features of CFEA and CBEA. En masse assignment exploits the fact that a relay can often aid not one but multiple SD pairs, and, therefore, can be assigned to multiple SD pairs. This drastically reduces the average time required to allocate an SD pair when compared to allocating the SD pairs one by one. We show that the algorithms are much faster than other selection schemes proposed in the literature and yield significantly higher net system throughputs. Interestingly, CFEA is as effective as CBEA over a wider range of system parameters than in single SD pair systems.

Solving MIN ONES 2-SAT as fast as VERTEX COVER

The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from MIN ONES 2-SAT to VERTEX COVER without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k - c logk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the MIN ONES 2-SAT and that of the corresponding VERTEX COVER are the same. This implies that the (recent) results of VERTEX COVER version parameterized above the optimum value of the LP relaxation of VERTEX COVER carry over to the MIN ONES 2-SAT version parameterized above the optimum of the LP relaxation of MIN ONES 2-SAT. (C) 2013 Elsevier B.V. All rights reserved.

A Secure and Efficient Authentication Protocol (SEAP) for MANETs with Membership Revocation

In this paper, we propose a novel authentication protocol for MANETs requiring stronger security. The protocol works on a two-tier network architecture with client nodes and authentication server nodes, and supports dynamic membership. We use an external membership granting server (MGS) to provide stronger security with dynamic membership. However, the external MGS in our protocol is semi-online instead of being online, i.e., the MGS cannot initiate a connection with a network node but any network node can communicate with the MGS whenever required. To ensure efficiency, the protocol uses symmetric key cryptography to implement the authentication service. However, to achieve storage scalability, the protocol uses a pseudo random function (PRF) to bind the secret key of a client to its identity using the secret key of its server. In addition, the protocol possesses an efficient server revocation mechanism along with an efficient server re-assignment mechanism, which makes the protocol robust against server node compromise.

RES-TOCSY: a simple approach to resolve overlapped H-1 NMR spectra of enantiomers

Chiral auxiliaries are used for the NMR spectroscopic study of enantiomers. Often the presence of impurities, overlap of peaks, line broadening and the multiplicity pattern restrict the chiral analysis in the 1D H-1 NMR spectrum. The present study introduces a simple 2D H-1 NMR experiment to unravel the overlapped spectrum. The experiment separates the spectra of enantiomers, thereby allowing the unambiguous assignment of all the coupled peaks and the measurement of enantiomeric excess (ee) from a single experiment even in combinatorial mixtures.

The relationship between classification of multi-domain proteins using an alignment-free approach and their functions: a case study with immunoglobulins

Establishing functional relationships between multi-domain protein sequences is a non-trivial task. Traditionally, delineating functional assignment and relationships of proteins requires domain assignments as a prerequisite. This process is sensitive to alignment quality and domain definitions. In multi-domain proteins due to multiple reasons, the quality of alignments is poor. We report the correspondence between the classification of proteins represented as full-length gene products and their functions. Our approach differs fundamentally from traditional methods in not performing the classification at the level of domains. Our method is based on an alignment free local matching scores (LMS) computation at the amino-acid sequence level followed by hierarchical clustering. As there are no gold standards for full-length protein sequence classification, we resorted to Gene Ontology and domain-architecture based similarity measures to assess our classification. The final clusters obtained using LMS show high functional and domain architectural similarities. Comparison of the current method with alignment based approaches at both domain and full-length protein showed superiority of the LMS scores. Using this method we have recreated objective relationships among different protein kinase sub-families and also classified immunoglobulin containing proteins where sub-family definitions do not exist currently. This method can be applied to any set of protein sequences and hence will be instrumental in analysis of large numbers of full-length protein sequences.

DEFINING alpha-HELIX GEOMETRY BY C-alpha ATOM TRACE vs (phi-psi) TORSION ANGLES: A COMPARATIVE ANALYSIS

A regular secondary structure is described by a well defined set of values for the backbone dihedral angles (phi,psi and omega) in a polypeptide chain. However in real protein structures small local variations give rise to distortions from the ideal structures, which can lead to considerable variation in higher order organization. Protein structure analysis and accurate assignment of various structural elements, especially their terminii, are important first step in protein structure prediction and design. Various algorithms are available for assigning secondary structure elements in proteins but some lacunae still exist. In this study, results of a recently developed in-house program ASSP have been compared with those from STRIDE, in identification of alpha-helical regions in both globular and membrane proteins. It is found that, while a combination of hydrogen bond patterns and backbone torsional angles (phi-psi) are generally used to define secondary structure elements, the geometry of the C-alpha atom trace by itself is sufficient to define the parameters of helical structures in proteins. It is also possible to differentiate the various helical structures by their C-alpha trace and identify the deviations occurring both at mid-positions as well as at the terminii of alpha-helices, which often lead to occurrence of 3(10) and pi-helical fragments in both globular and membrane proteins.

On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q >= 2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q >= 2, and has been well-studied from the point of view of approximation. Our main focus is the case when q = 2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.