Faster algorithms for all-pairs small stretch distances in weighted graphs

Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick [14] showed that for any fixed ε> 0, stretch 1 1 + ε distances between all pairs of vertices in a weighted directed graph on n vertices can be computed in Õ(n ω) time, where ω < 2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. It is also known that all-pairs stretch 3 distances can be computed in Õ(n 2) time and all-pairs stretch 7/3 distances can be computed in Õ(n 7/3) time. Here we consider efficient algorithms for the problem of computing all-pairs stretch (2+ε) distances in G, for any 0 < ε < 1. We show that all pairs stretch (2 + ε) distances for any fixed ε> 0 in G can be computed in expected time O(n 9/4 logn). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n 9/4) for computing all-pairs stretch 5/2 distances in G. 1

Ferrocene-based Lewis acids and Lewis pairs: Synthesis and structural characterization

Optically active Lewis acids and Lewis pairs were synthesized and characterized by multinuclear NMR, UV/Vis spectroscopy and elemental analysis. Optical rotation measurements were carried out and the absolute configuration of the new chiral molecules confirmed by single crystal X-ray diffraction.

Improved LSB stegananalysis based on analysis of adjacent pixel pairs

We propose a simple, reliable method based on probability of transitions and distribution of adjacent pixel pairs for steganalysis on digital images in spatial domain subjected to Least Significant Bit replacement steganography. Our method is sensitive to the statistics of underlying cover image and is a variant of Sample Pair Method. We use the new method to estimate length of hidden message reliably. The novelty of our method is that it detects from the statistics of the underlying image, which is invariant with embedding, whether the results it calculate are reliable or not. To our knowledge, no steganalytic method so far predicts from the properties of the stego image, whether its results are accurate or not.

Assignment of the C-13 NMR spectrum by correlation to dipolar coupled proton-pairs and estimation of order parameters of a thiophene based liquid crystal

Materials with widely varying molecular topologies and exhibiting liquid crystalline properties have attracted considerable attention in recent years. C-13 NMR spectroscopy is a convenient method for studying such novel systems. In this approach the assignment of the spectrum is the first step which is a non-trivial problem. Towards this end, we propose here a method that enables the carbon skeleton of the different sub-units of the molecule to be traced unambiguously. The proposed method uses a heteronuclear correlation experiment to detect pairs of nearby carbons with attached protons in the liquid crystalline core through correlation of the carbon chemical shifts to the double-quantum coherences of protons generated through the dipolar coupling between them. Supplemented by experiments that identify non-protonated carbons, the method leads to a complete assignment of the spectrum. We initially apply this method for assigning the C-13 spectrum of the liquid crystal 4-n-pentyl-4'-cyanobiphenyl oriented in the magnetic field. We then utilize the method to assign the aromatic carbon signals of a thiophene based liquid crystal thereby enabling the local order-parameters of the molecule to be estimated and the mutual orientation of the different sub-units to be obtained.

Frustrated Lewis pairs: Design and reactivity

The interaction of a Lewis acid with a Lewis base results in the formation of a Lewis acid base adduct. Understanding Lewis acids and bases is central to conceptualizing chemical interactions and constitutes a major portion of metal ligand chemistry. Sterically encumbered/constrained Lewis pairs cannot form acid-base adducts, but such `Frustrated Lewis Pairs' (FLPs), with their unquenched electronic demands can be elegantly used to simultaneously react with a third species, resulting in unusual reactivity of small molecules. Such unusual reactions, explored only in the last few years, have found several applications, e.g., heterolytic splitting of H-2, activation of small molecules (CO2, N2O, etc.). FLPs have opened new opportunities in synthetic chemistry, covering organic, main group as well as transition metal chemistry. The design strategies adopted for FLP systems and their unique reactivity are discussed here.

Characterization of friction at three contact pairs by photoelastic Isotropic point (IP)

Friction coefficient between a circular-disk periphery and V-block surface was determined by introducing the concept of isotropic point (IP) in isochromatic field of the disk under three-point symmetric loading. IP position on the symmetry axis depends on active coefficient of friction during experiment. We extend this work to asymmetric loading of circular disk in which case two frictional contact pairs out of three loading contacts, independently control the unconstrained IP location. Photoelastic experiment is conducted on particular case of asymmetric three-point loading of circular disk. Basics of digital image processing are used to extract few essential parameters from experimental image, particularly IP location. Analytical solution by Flamant for half plane with a concentrated load, is utilized to derive stress components for required loading configurations of the disk. IP is observed, in analytical simulations of three-point asymmetric normal loading, to move from vertical axis to the boundary along an ellipse-like curve. When friction is included in the analysis, IP approaches the center with increase in loading friction and it goes away with increase in support friction. With all these insights, using experimental IP information, friction angles at three contact pairs of circular disk under asymmetric loading, are determined.

Counting zero kernel pairs over a finite field

Helmke et al. have recently given a formula for the number of reachable pairs of matrices over a finite field. We give a new and elementary proof of the same formula by solving the equivalent problem of determining the number of so called zero kernel pairs over a finite field. We show that the problem is, equivalent to certain other enumeration problems and outline a connection with some recent results of Guo and Yang on the natural density of rectangular unimodular matrices over F-qx]. We also propose a new conjecture on the density of unimodular matrix polynomials. (C) 2016 Elsevier Inc. All rights reserved.

Binding of DNA Nucleobases and Nucleosides with Graphene

Interaction of two different samples of graphene with DNA nucleobases and nucleosides is investigated by isothermal titration calorimetry. The relative interaction energies of the nucleobases decrease in the order guanine (G) > adenine (A) > cytosine (C) > thy mine (T) in aqueous solutions, although the positions of C and T seem to be interchangeable. The same trend is found with the nucleosides. Interaction energies of the A-T and G-C pairs are somewhere between those of the constituent bases. Theoretical calculations including van der Wools interaction and solvation energies give the trend G > A similar to T > C. The magnitudes of the interaction energies of the nucleobases with graphene are similar to those found with single-walled carbon nonotubes.

X-ray Structure of Gelonin at 1.8 Å Resolution

Gelonin is a single chain ribosome inactivating protein (RIP) with potential application in the treatment of cancer and AIDS. Diffraction quality crystals grown using PEG3350, belong to the space group P2(1), with it a = 49.4 Angstrom b = 44.9 Angstrom, c = 137.4 Angstrom and beta = 98.4 degrees, and contain two molecules in the asymmetric unit. Diffraction data collected to 1.8 Angstrom resolution has a R(m) value of 7.3%. Structure of gelonin has been solved by the molecular replacement method, using ricin A chain as the search model. Crystallographic refinement using X-PLOR resulted in a model for which the r.m.s deviations from ideal bond lengths and bond angles are 0.012 Angstrom and 2.7 degrees, respectively The final R-factor is 18.4% for 39,806 reflections for which I > 1.0 sigma(I).The C-alpha atoms of the two molecules in the asymmetric unit superpose to within 0.38 Angstrom for 247 atom pairs. The overall fold of gelonin is similar to that of other RIPs such as ricin A chain and alpha-momorcharin, the r.m.s.d. for C-alpha superpositions being 1.3 and 1.4 Angstrom, respectively The-catalytic residues (Glu166, Arg169 and Tyr113) in the active site form a hydrogen bond scheme similar to that observed in other RIPs. The conformation of Tyr74 in the active site, however, is significantly different from that in alpha-momorcharin. Three well defined water molecules are located in the active site cavity and one of them, X319, superposes to within 0.2 Angstrom of a corresponding water molecule in the structure of alpha-momorcharin. Any of the three could be the substrate water molecule in the hydrolysis reaction catalysed by gelonin.Difference electron density for a N-linked sugar moiety has been observed near only one of the two potential glycosylation sites in the sequence. The amino acid at position 239 has been established as Lys by calculation of omit electron density maps.The two cysteine residues in the sequence, Cys44 and Cys50, form a disulphide bond, and are therefore not available for disulphide conjugation with antibodies. Based on the structure, the region of the molecule that is involved in intradimer interactions is suggested to be suitable for introducing a Cys residue for purposes of conjugation with an antibody to produce useful immunotoxins.

Some remarks on the symplectic pairing on the moduli space of representations of the fundamental group of surfaces

This work grew out of an attempt to understand a conjectural remark made by Professor Kyoji Saito to the author about a possible link between the Fox-calculus description of the symplectic structure on the moduli space of representations of the fundamental group of surfaces into a Lie group and pairs of mutually dual sets of generators of the fundamental group. In fact in his paper [3] , Prof. Kyoji Saito gives an explicit description of the system of dual generators of the fundamental group.

Spin populations in one-dimensional alternant spin systems: A theoretical approach

Spin-density maps, deduced from polarized neutron diffraction experiments, for both the pair and chain compounds of the system Mn2+Cu2+ have been reported recently. These results have motivated us to investigate theoretically the spin populations in such alternant mixed-spin systems. In this paper, we report our studies on the one-dimensional ferrimagnetic systems (S-A,S-B)(N) where hi is the number of AB pairs. We have considered all cases in which the spin Sri takes on allowed values in the range I to 7/2 while the spin S-B is held fixed at 1/2. The theoretical studies have been carried out on the isotropic Heisenberg model, using the density matrix renormalization group method. The effect of the magnitude of the larger spin SA On the quantum fluctuations in both A and B sublattices has been studied as a function of the system size N. We have investigated systems with both periodic and open boundary conditions, the latter with a view to understanding end-of-chain effects. The spin populations have been followed as a function of temperature as well as an applied magnetic field. High-magnetic fields are found to lead to interesting re-entrant behavior. The ratio of spin populations P-A-P-B is not sensitive to temperature at low temperatures.

Analysis on conservation of disulphide bonds and their structural features in homologous protein domain families

Background: Disulphide bridges are well known to play key roles in stability, folding and functions of proteins. Introduction or deletion of disulphides by site-directed mutagenesis have produced varying effects on stability and folding depending upon the protein and location of disulphide in the 3-D structure. Given the lack of complete understanding it is worthwhile to learn from an analysis of extent of conservation of disulphides in homologous proteins. We have also addressed the question of what structural interactions replaces a disulphide in a homologue in another homologue. Results: Using a dataset involving 34,752 pairwise comparisons of homologous protein domains corresponding to 300 protein domain families of known 3-D structures, we provide a comprehensive analysis of extent of conservation of disulphide bridges and their structural features. We report that only 54% of all the disulphide bonds compared between the homologous pairs are conserved, even if, a small fraction of the non-conserved disulphides do include cytoplasmic proteins. Also, only about one fourth of the distinct disulphides are conserved in all the members in protein families. We note that while conservation of disulphide is common in many families, disulphide bond mutations are quite prevalent. Interestingly, we note that there is no clear relationship between sequence identity between two homologous proteins and disulphide bond conservation. Our analysis on structural features at the sites where cysteines forming disulphide in one homologue are replaced by non-Cys residues show that the elimination of a disulphide in a homologue need not always result in stabilizing interactions between equivalent residues. Conclusion: We observe that in the homologous proteins, disulphide bonds are conserved only to a modest extent. Very interestingly, we note that extent of conservation of disulphide in homologous proteins is unrelated to the overall sequence identity between homologues. The non-conserved disulphides are often associated with variable structural features that were recruited to be associated with differentiation or specialisation of protein function.

Free energy landscape of a dense hard-sphere system

The topography of the free energy landscape in phase space of a dense hard-sphere system characterized by a discretized free energy functional of the Ramakishnan-Yussouff form is investigated numerically using a specially devised Monte Carlo procedure. We locate a considerable number of glassy local minima of the free energy and analyze the distributions of the free energy at a minimum and an appropriately defined phase-space "distance" between different minima. We find evidence for the existence of pairs of closely related glassy minima("two-level systems"). We also investigate the way the system makes transitions as it moves from the basin of attraction of a minimum to that of another one after a start under nonequilibrium conditions. This allows us to determine the effective height of free energy barriers that separate a glassy minimum from the others. The dependence of the height of free energy barriers on the density is investigated in detail. The general appearance of the free energy landscape resembles that of a putting green: relatively deep minima separated by a fairly flat structure. We discuss the connection of our results with the Vogel-Fulcher law and relate our observations to other work on the glass transition.

PocketMatch: A new algorithm to compare binding sites in protein structures

Recognizing similarities and deriving relationships among protein molecules is a fundamental requirement in present-day biology. Similarities can be present at various levels which can be detected through comparison of protein sequences or their structural folds. In some cases similarities obscure at these levels could be present merely in the substructures at their binding sites. Inferring functional similarities between protein molecules by comparing their binding sites is still largely exploratory and not as yet a routine protocol. One of the main reasons for this is the limitation in the choice of appropriate analytical tools that can compare binding sites with high sensitivity. To benefit from the enormous amount of structural data that is being rapidly accumulated, it is essential to have high throughput tools that enable large scale binding site comparison. Results: Here we present a new algorithm PocketMatch for comparison of binding sites in a frame invariant manner. Each binding site is represented by 90 lists of sorted distances capturing shape and chemical nature of the site. The sorted arrays are then aligned using an incremental alignment method and scored to obtain PMScores for pairs of sites. A comprehensive sensitivity analysis and an extensive validation of the algorithm have been carried out. A comparison with other site matching algorithms is also presented. Perturbation studies where the geometry of a given site was retained but the residue types were changed randomly, indicated that chance similarities were virtually non-existent. Our analysis also demonstrates that shape information alone is insufficient to discriminate between diverse binding sites, unless combined with chemical nature of amino acids. Conclusion: A new algorithm has been developed to compare binding sites in accurate, efficient and high-throughput manner. Though the representation used is conceptually simplistic, we demonstrate that along with the new alignment strategy used, it is sufficient to enable binding comparison with high sensitivity. Novel methodology has also been presented for validating the algorithm for accuracy and sensitivity with respect to geometry and chemical nature of the site. The method is also fast and takes about 1/250(th) second for one comparison on a single processor. A parallel version on BlueGene has also been implemented.

Synthesis, structure and spectroscopic studies on hydroxo-bridged heterotrinuclear complexes of cobalt(m) with ethane-l,2-diamine and ammonia as terminal ligands

Hydroxo-bridged homo- and hetero-trinuclear cobalt(III) complexes of the type [MII(H2O)2{(OH)2CoIII(N4)}2]X2·nH2O [MII= a divalent metal ion such as CoII, NiII or ZnII; N4=(en)2(en = ethane-1,2-diamine) or (NH3)4; X = SO4 or (ClO4)2; n= 3 or 5] have been prepared and spectroscopically characterized. The structure of [Cu{(OH)2Co(en)2}2][SO4]2·2H2O 1 has been determined. The geometry around copper atom is a pseudo-square-based pyramid, with the basal sites occupied by four bridging hydroxide oxygens and the apical site is occupied by a weakly co-ordinated sulfate anion [Cu–O 2.516(4)Å]. The hydroxo groups bridge pairs of cobalt(III) ions which are in near-octahedral environments. The ethylenediamine chelate rings have the twist conformation. In the crystal structure of [Cu{(OH)2Co(en)2}2][ClO4]4·2H2O 2 the perchlorate ion is not co-ordinated and the en ligands have envelope conformations. The sulfate ion in [Cu{(OH)2Co(NH3)4}2][SO4]2·4H2O 3 is not co-ordinated to the central copper ion. Electronic, infrared and variable-temperature EPR spectral data are discussed.