Optimal popular matchings

In this paper we consider the problem of computing an “optimal” popular matching. We assume that our input instance View the MathML source admits a popular matching and here we are asked to return not any popular matching but an optimal popular matching, where the definition of optimality is given as a part of the problem statement; for instance, optimality could be fairness in which case we are required to return a fair popular matching. We show an O(n2+m) algorithm for this problem, assuming that the preference lists are strict, where m is the number of edges in G and n is the number of applicants.

Sterochemical studies on cyclic peptides-VIII. Conformational analysis of hydrogen bonded cyclohexaglycyl molecule with a centre of inversion symmetry

A study on the conformational aspects of cyclo-hexaglycyl having inversion symmetry has been made. The cyclic backbone has been assumed to have two internal 4→1 types of NH... O hydrogen bonds. This molecule has been found to take up two types of conformations designated asA* andB* having nearly the same energy values. The theoretical conformations have been compared with the conformations of cyclohexaglycyl hemihydrate observed in the crystal structure. Two molecules with an approximate inversion symmetry are close to the conformation of the typeB* and two other molecules with exact inversino symmetry correspond nearly to the typesB* andA*. comparison with the theoretically possible conformations of cyclohexaglycyl molecule with 2-fold symmetry has been made. The preference of inversion symmetry and preferred ranges ofψ for glycyl molecules is discussed.

Spatiotemporal Organization of AT- and GC-rich DNA and Their Association With Transition Proteins TP1 and TP2 in Rat Condensing Spermatids

Transition protein 1 (TP1) and TP2 replace histones during midspermiogenesis (stages 12-15) and are finally replaced by protamines. TPs play a predominant role in DNA condensation and chromatin remodeling during mammalian spermiogenesis. TP2 is a zinc metalloprotein with two novel zinc finger modules that condenses DNA in vitro in a GC-preference manner. TP2 also localizes to the nucleolus in transfected HeLa and Cos-7 cells, suggesting a GC-rich preference, even in vivo. We have now studied the localization pattern of TP2 in the rat spermatid nucleus. Colocalization studies using GC-selective DNA-binding dyes chromomycin A3 and 7-amino actinomycin D and an AT-selective dye, 4',6-diamidino-2-phenylindole, indicate that TP2 is preferentially localized to GC-rich sequences. Interestingly, as spermatids mature, TP2 and GC-rich DNA moves toward the nuclear periphery, and in the late stages of spermatid maturation, TP2 is predominantly localized at the nuclear periphery. Another interesting observation is the mutually exclusive localization of GC- and AT-rich DNA in the elongating and elongated spermatids. A combined immunofluorescence experiment with anti-TP2 and anti-TP1 antibodies revealed several foci of overlapping localization, indicating that TP1 and TP2 may have concerted functional roles during chromatin remodeling in mammalian spermiogenesis.

The hydrogen bond: a molecular beam microwave spectroscopist's view with a universal appeal

In this manuscript, we propose a criterion for a weakly bound complex formed in a supersonic beam to be characterized as a `hydrogen bonded complex'. For a `hydrogen bonded complex', the zero point energy along any large amplitude vibrational coordinate that destroys the orientational preference for the hydrogen bond should be significantly below the barrier along that coordinate so that there is at least one bound level. These are vibrational modes that do not lead to the breakdown of the complex as a whole. If the zero point level is higher than the barrier, the `hydrogen bond' would not be able to stabilize the orientation which favors it and it is no longer sensible to characterize a complex as hydrogen bonded. Four complexes, Ar-2-H2O, Ar-2-H2S, C2H4-H2O and C2H4-H2S, were chosen for investigations. Zero point energies and barriers for large amplitude motions were calculated at a reasonable level of calculation, MP2(full)/aug-cc-pVTZ, for all these complexes. Atoms in molecules (AIM) theoretical analyses of these complexes were carried out as well. All these complexes would be considered hydrogen bonded according to the AIM theoretical criteria suggested by Koch and Popelier for C-H center dot center dot center dot O hydrogen bonds (U. Koch and P. L. A. Popelier, J. Phys. Chem., 1995, 99, 9747), which has been widely and, at times, incorrectly used for all types of contacts involving H. It is shown that, according to the criterion proposed here, the Ar-2-H2O/H2S complexes are not hydrogen bonded even at zero kelvin and C2H4-H2O/H2S complexes are. This analysis can naturally be extended to all temperatures. It can explain the recent experimental observations on crystal structures of H2S at various conditions and the crossed beam scattering studies on rare gases with H2O and H2S.

Theoretical calculations of base-base interactions in nucleic acids: II Stacking interactions in polynucleotides

Base-base interactions were computed for single- and double- stranded polynucleotides, for all possible base sequences. In each case, both right and left stacking arrangements are energetically possible. The preference of one over the other depends upon the base-sequence and the orientation of the bases with respect to helix-axis. Inverted stacking arrangement is also energetically possible for both single- and double-stranded polynucleotides. Finally, interaction energies of a regular duplex and the alternative structures3 were compared. It was found that the type II model3 is energetically more favourable than the rest.

Popular Mixed Matchings

We study the problem of matching applicants to jobs under one-sided preferences: that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching M is said to be rnore popular than T if the applicants that prefer M to T outnumber those that prefer T to M. A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching M is popular if phi(M,T) >= phi(T, M) for all matchings T, where phi(X, Y) is the number of applicants that prefer X to Y. Previously studied solution concepts based oil the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distributions over matchings in the input graph. The function phi that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching P is popular if phi(P,Q) >= phi(Q,P) for all mixed matchings Q. We show that popular mixed matchings always exist. and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem.

Which One Is Preferred: Myers-Saito Cyclization of Ene-Yne-Allene or Garratt-Braverman Cyclization of Conjugated Bisallenic Sulfone? A Theoretical and Experimental Study

A competitive scenario between Myers-Saito (MS) and Garraff-Braverman (GB) cyclization has been created in a molecule. High-level computations indicate a preference for GB over MS cyclization. The activation energies for the rate-determining steps of the GB and MS cyclizations were found to be the same (24.4 kcal/mol) at the B3LYP/6-31G* level of theory; thus, from the kinetic point of view, both reactions are feasible. However, the main biradical intermediate GB2 of the GB reaction is 6.2 kcal/mol lower in energy than the biradical MS2, which is the main intermediate of MS reaction, so GB cyclization is thermodynamically favored over MS cyclization. To verify the prediction by computational techniques, bisenediynyl sulfones 1-4 and bisenediynyl sulfoxide 17 were synthesized. Under basic conditions, these molecules isomerized to a system possessing both the ene-yne-allene and the bisallenic sulfone. The isolation of only one product, identified as the corresponding naphthalene- or benzene-fused sulfone 8-11, indicated the occurrence of GB cyclization as the sole reaction pathway. No product corresponding to the MS cyclization pathway could be isolated. Though the theoretical prediction showed a preference for the GB pathway over the MS pathway, the exclusive preference for GB over MS cyclization is very striking. Further analysis showed that the intramolecular self-quenching nature of the GB pathway may play an important role in the complete preference for this reaction. Apart from the mechanistic studies, these sulfones showed DNA cleavage activity that had an inverse relation with the reactivity order. Our findings are important for the design of artificial DNA-cleaving agents.

Pi-turns in proteins and peptides: Classification, conformation, occurrence, hydration and sequence.

The i + 5-->i hydrogen bonded turn conformation (pi-turn) with the fifth residue adopting alpha L conformation is frequently found at the C-terminus of helices in proteins and hence is speculated to be a "helix termination signal." An analysis of the occurrence of i + 5-->i hydrogen bonded turn conformation at any general position in proteins (not specifically at the helix C-terminus), using coordinates of 228 protein crystal structures determined by X-ray crystallography to better than 2.5 A resolution is reported in this paper. Of 486 detected pi-turn conformations, 367 have the (i + 4)th residue in alpha L conformation, generally occurring at the C-terminus of alpha-helices, consistent with previous observations. However, a significant number (111) of pi-turn conformations occur with (i + 4)th residue in alpha R conformation also, generally occurring in alpha-helices as distortions either at the terminii or at the middle, a novel finding. These two sets of pi-turn conformations are referred to by the names pi alpha L and pi alpha R-turns, respectively, depending upon whether the (i + 4)th residue adopts alpha L or alpha R conformations. Four pi-turns, named pi alpha L'-turns, were noticed to be mirror images of pi alpha L-turns, and four more pi-turns, which have the (i + 4)th residue in beta conformation and denoted as pi beta-turns, occur as a part of hairpin bend connecting twisted beta-strands. Consecutive pi-turns occur, but only with pi alpha R-turns. The preference for amino acid residues is different in pi alpha L and pi alpha R-turns. However, both show a preference for Pro after the C-termini. Hydrophilic residues are preferred at positions i + 1, i + 2, and i + 3 of pi alpha L-turns, whereas positions i and i + 5 prefer hydrophobic residues. Residue i + 4 in pi alpha L-turns is mainly Gly and less often Asn. Although pi alpha R-turns generally occur as distortions in helices, their amino acid preference is different from that of helices. Poor helix formers, such as His, Tyr, and Asn, also were found to be preferred for pi alpha R-turns, whereas good helix former Ala is not preferred. pi-Turns in peptides provide a picture of the pi-turn at atomic resolution. Only nine peptide-based pi-turns are reported so far, and all of them belong to pi alpha L-turn type with an achiral residue in position i + 4. The results are of importance for structure prediction, modeling, and de novo design of proteins.

Processing of SeMV polyproteins revisited

Processing of Sesbania mosaic virus (SeMV) polyprotein 2a and 2ab was reanalyzed in the view of the new genome organization of sobemoviruses. Polyprotein 2a when expressed in E coli, from the new cDNA clone, got cleaved at the earlier identified sites E325-T326, E402-T403 and E498-S499 to release protease, VPg, P10 and P8, respectively. Additionally, a novel cleavage was identified within the protease domain at position E132-S133, which was found to be essential for efficient polyprotein processing. Products, corresponding to cleavages identified in E. coli, were also detected in infected Sesbania leaves. Interestingly, though the sites are exactly the same in polyprotein 2ab, it got cleaved between Protease-VPg but not between VPg-RdRp. This indicates to a differential cleavage preference, governed probably by the conformation of 2ab. Also, the studies revealed that, in SeMV, processing is regulated by mode of cleavage and context of the cleavage site.

The virial expansion of a classical interacting system

We consider N particles interacting pairwise by an inverse square potential in one dimension (Calogero-Sutherland-Moser model). For a system placed in a harmonic trap, its classical partition function for the repulsive regime is recognised in the literature. We start by presenting a concise re-derivation of this result. The equation of state is then calculated both for the trapped and the homogeneous gas. Finally, the classical limit of Wu's distribution function for fractional exclusion statistics is obtained and we re-derive the classical virial expansion of the homogeneous gas using this distribution function.

Modulating the preferred O-H center dot center dot center dot O hydrogen-bonding motif in a conformationally constrained environment through hydroxy-group derivatization

The crystal structures of three conformationally locked esters, namely the centrosymmetric tetrabenzoate of all-axial per-hydronaphthalene- 2,3,4a, 6,7,8a-hexaol, viz. trans-4a, 8a-dihydroxyperhydronaphthalene-2,3,6,7-tetrayl tetrabenzoate, C38H34O10, and the diacetate and dibenzoate of all-axial perhydronaphthalene-2,3,4a, 8a-tetraol, viz. (2R*,3R*,4aS*,8aS*)-4a, 8a-dihydroxyperhydronaphthalene-2,3-diyl diacetate, C-14-H22O6, and (2R*, 3R*, 4aS*, 8aS*)-4a, 8a-dihydroxyperhydronaphthalene- 2,3-diyl dibenzoate, C24H26O6, have been analyzed in order to examine the preference of their supramolecular assemblies towards competing inter-and intramolecular O-H center dot center dot center dot O hydrogen bonds. It was anticipated that the supramolecular assembly of the esters under study would adopt two principal hydrogen-bonding modes, namely one that employs intermolecular O-H center dot center dot center dot O hydrogen bonds (mode 1) and another that sacrifices those for intramolecular O-H center dot center dot center dot O hydrogen bonds and settles for a crystal packing dictated by weak intermolecular interactions alone (mode 2). Thus, while the molecular assembly of the two crystalline diacyl derivatives conformed to a combination of hydrogen-bonding modes 1 and 2, the crystal packing in the tetrabenzoate preferred to follow mode 2 exclusively.

Analyzing information flow in brain networks with nonparametric Granger causality

Multielectrode neurophysiological recording and high-resolution neuroimaging generate multivariate data that are the basis for understanding the patterns of neural interactions. How to extract directions of information flow in brain networks from these data remains a key challenge. Research over the last few years has identified Granger causality as a statistically principled technique to furnish this capability. The estimation of Granger causality currently requires autoregressive modeling of neural data. Here, we propose a nonparametric approach based on widely used Fourier and wavelet transforms to estimate both pairwise and conditional measures of Granger causality, eliminating the need of explicit autoregressive data modeling. We demonstrate the effectiveness of this approach by applying it to synthetic data generated by network models with known connectivity and to local field potentials recorded from monkeys performing a sensorimotor task.

Binding of nucleobases with single-walled carbon nanotubes: Theory and experiment

We report the binding energy of various nucleobases (guanine (G), adenine (A), thymine (T) and cytosine (C)) with (5,5) single-walled carbon nanotube (SWNT) calculated using first-principle Hartre–Fock method (HF) together with classical force field. The binding energy without including the solvation effects of water decreases in the order G>A>T>C. The inclusion of solvation energy changes the order of binding preference to be G>T>A>C. Using isothermal titration (micro) calorimetry experiments, we also show the relative binding affinity to be T>A>C, in agreement with our calculations.

Inter-helical Interactions in Membrane Proteins: Analysis Based on the Local Backbone Geometry and the Side Chain Interactions

The availability of a significant number of the Structures of helical membrane proteins has prompted us to investigate the mode of helix-helix packing. In the present study, we have considered a dataset of alpha-helical membrane proteins representing Structures solved from all the known superfamilies. We have described the geometry of all the helical residues in terms of local coordinate axis at the backbone level. Significant inter-helical interactions have been considered as contacts by weighing the number of atom-atom contacts, including all the side-chain atoms. Such a definition of local axis and the contact criterion has allowed us to investigate the inter-helical interaction in a systematic and quantitative manner. We show that a single parameter (designated as alpha), which is derived from the parameters representing the Mutual orientation of local axes, is able to accurately Capture the details of helix-helix interaction. The analysis has been carried Out by dividing the dataset into parallel, anti-parallel, and perpendicular orientation of helices. The study indicates that a specific range of alpha value is preferred for interactions among the anti-parallel helices. Such a preference is also seen among interacting residues of parallel helices, however to a lesser extent. No such preference is seen in the case of perpendicular helices, the contacts that arise mainly due to the interaction Of Surface helices with the end of the trans-membrane helices. The Study Supports the prevailing view that the anti-parallel helices are well packed. However, the interactions between helices of parallel orientation are non-trivial. The packing in alpha-helical membrane proteins, which is systematically and rigorously investigated in this study, may prove to be useful in modeling of helical membrane proteins.

Structure and Bonding in Cyclic Isomers of B2AlHnm (n = 3−6, m = −2 to +1): A Comparative Study with B3Hnm, BAl2Hnm and Al3Hnm†

The structure, bonding and energetics of B2AlHnm (n = 3−6, m = −2 to +1) are compared with corresponding homocyclic boron, aluminum analogues and BAl2Hnm using density functional theory (DFT). Divalent to hexacoordinated boron and aluminum atoms are found in these species. The geometrical and bonding pattern in B2AlH4− is similar to that for B2SiH4. Species with lone pairs on the divalent boron and aluminum atoms are found to be minima on the potential energy surface of B2AlH32−. A dramatic structural diversity is observed in going from B3Hnm to B2AlHnm, BAl2Hnm and Al3Hnm and this is attributable to the preference of lower coordination on aluminum, higher coordination on boron and the higher multicenter bonding capability of boron. The most stable structures of B3H6+, B2AlH5 and BAl2H4− and the trihydrogen bridged structure of Al3H32− show an isostructural relationship, indicating the isolobal analogy between trivalent boron and divalent aluminum anion.