Geometric representations of graphs in low dimension

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $\Delta$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.

Evolving Random Geometric Graph Models for Mobile Wireless Networks

We consider evolving exponential RGGs in one dimension and characterize the time dependent behavior of some of their topological properties. We consider two evolution models and study one of them detail while providing a summary of the results for the other. In the first model, the inter-nodal gaps evolve according to an exponential AR(1) process that makes the stationary distribution of the node locations exponential. For this model we obtain the one-step conditional connectivity probabilities and extend it to the k-step case. Finite and asymptotic analysis are given. We then obtain the k-step connectivity probability conditioned on the network being disconnected. We also derive the pmf of the first passage time for a connected network to become disconnected. We then describe a random birth-death model where at each instant, the node locations evolve according to an AR(1) process. In addition, a random node is allowed to die while giving birth to a node at another location. We derive properties similar to those above.

Docking and free energy simulations to predict conformational domains involved in hCG-LH receptor interactions using recombinant antibodies

Single chain fragment variables (ScFvs) have been extensively employed in studying the protein-protein interactions. ScFvs derived from phage display libraries have an additional advantage of being generated against a native antigen, circumventing loss of information on conformational epitopes. In the present study, an attempt has been made to elucidate human chorionic gonadotropin (hCG)-luteinizing hormone (LH) receptor interactions by using a neutral and two inhibitory ScFvs against hCG. The objective was to dock a computationally derived model of these ScFvs onto the crystal structure of hCG and understand the differential roles of the mapped epitopes in hCG-LH receptor interactions. An anti-hCG ScFv, whose epitope was mapped previously using biochemical tools, served as the positive control for assessing the quality of docking analysis. To evaluate the role of specific side chains at the hCG-ScFv interface, binding free energy as well as residue interaction energies of complexes in solution were calculated using molecular mechanics Poisson-Boltzmann/surface area method after performing the molecular dynamic simulations on the selected hCG-ScFv models and validated using biochemical and SPR analysis. The robustness of these calculations was demonstrated by comparing the theoretically determined binding energies with the experimentally obtained kinetic parameters for hCG-ScFv complexes. Superimposition of hCG-ScFv model onto a model of hCG complexed with the 51-266 residues of LH receptor revealed importance of the residues previously thought to be unimportant for hormone binding and response. This analysis provides an alternate tool for understanding the structure-function analysis of ligand-receptor interactions. Proteins 2011;79:3108-3122. (C) 2011 Wiley-Liss, Inc.

Design, synthesis and docking studies of new quinoline-3-carbohydrazide derivatives as antitubercular agents

Three new series of 4-hydroxy-8-trifluoromethyl-quinoline derivatives were synthesized through multi step reactions. All the newly synthesized compounds were characterized by spectral and elemental analyses. The structure of 5j was evidenced by X-ray crystallographic study. The newly synthesized title compounds were evaluated for their antimicrobial activities including antimycobacterial activity. Amongst the tested compounds, 5b, 5e, 5h, 5j, 6c and 7c displayed promising antimicrobial activity. The mode of action of these active compounds was carried out by docking of receptor enoyl-ACP reductase with newly synthesized candidate ligands, 5b, 5e, 5h, 5j and 6c. (C) 2011 Elsevier Masson SAS. All rights reserved.

Binding of BIS like and other ligands with the GSK-3 beta kinase: a combined docking and MM-PBSA study

Binding of several bisindolylmaleimide (BIS) like (BIS-3, BIS-8 and UCN1) and other ligands (H89, SB203580 and Y27632) with the glycogen synthase kinase-3 (GSK-3 beta) has been studied using combined docking, molecular dynamics and Poisson-Boltzmann surface area analysis approaches. The study generated novel binding modes of these ligands that can rationalize why some ligands inhibit GSK-3 beta while others do not. The relative binding free energies associated with these binding modes are in agreement with the corresponding measured specificities. This study further provides useful insight regarding possible existence of multiple conformations of some ligands like H89 and BIS-8. It is also found that binding modes of BIS-3, BIS-8 and UCN1 with GSK-3 beta and PDK1 kinases are similar. These new insights are expected to be useful for future rational design of novel, more potent GSK-3 beta-specific inhibitors as promising therapeutics.

Geometric Decision Tree

In this paper, we present a new algorithm for learning oblique decision trees. Most of the current decision tree algorithms rely on impurity measures to assess the goodness of hyperplanes at each node while learning a decision tree in top-down fashion. These impurity measures do not properly capture the geometric structures in the data. Motivated by this, our algorithm uses a strategy for assessing the hyperplanes in such a way that the geometric structure in the data is taken into account. At each node of the decision tree, we find the clustering hyperplanes for both the classes and use their angle bisectors as the split rule at that node. We show through empirical studies that this idea leads to small decision trees and better performance. We also present some analysis to show that the angle bisectors of clustering hyperplanes that we use as the split rules at each node are solutions of an interesting optimization problem and hence argue that this is a principled method of learning a decision tree.

Percolation and connectivity in AB random geometric graphs

Given two independent Poisson point processes Phi((1)), Phi((2)) in R-d, the AB Poisson Boolean model is the graph with the points of Phi((1)) as vertices and with edges between any pair of points for which the intersection of balls of radius 2r centered at these points contains at least one point of Phi((2)). This is a generalization of the AB percolation model on discrete lattices. We show the existence of percolation for all d >= 2 and derive bounds fora critical intensity. We also provide a characterization for this critical intensity when d = 2. To study the connectivity problem, we consider independent Poisson point processes of intensities n and tau n in the unit cube. The AB random geometric graph is defined as above but with balls of radius r. We derive a weak law result for the largest nearest-neighbor distance and almost-sure asymptotic bounds for the connectivity threshold.

Molecular Docking Studies of Novel Palmitoyl-ligands for Cyclooxygenase-2

An in silico approach was adopted to identify potential cyclooxygenase-2 inhibitors through molecular docking studies. The in vivo studies indicated that synthetic palmitoyl derivatives of salicylic acid, para amino phenol, para amino benzoic acid, and anthranilic acid possessed significant pharmacological activities like anti-inflammatory, analgesic, and antipyretic activities. None of the tested substances produced any significant gastric lesions in experimental animals. In an attempt to understand the ligandprotein interactions in terms of the binding affinity, the above synthetic molecules were subjected to docking analysis using AutoDock. The palmitoyl derivatives palmitoyl anthranilic acid, palmitoyl para amino benzoic acid, palmitoyl para amino phenol, and palmitoyl salicylic acid showed better binding energy than the known inhibitor diclofenac bound to 1PXX. All the palmitoyl derivatives made similar interactions with the binding site residues of cyclooxygenase-2 as compared to that of the known inhibitor. Thus, structure-based drug discovery approach was successfully employed to identify some promising pro-drugs for the treatment of pain and inflammation.

Theory and Algorithms for Hop-Count-Based Localization with Random Geometric Graph Models of Dense Sensor Networks

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization. Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h. This approximation is shown, through simulation, to very closely match the true density function. Localization algorithms that draw upon the preceding analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation-based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.

Nonuniform random geometric graphs with location-dependent radii

We propose a distribution-free approach to the study of random geometric graphs. The distribution of vertices follows a Poisson point process with intensity function n f(center dot), where n is an element of N, and f is a probability density function on R-d. A vertex located at x connects via directed edges to other vertices that are within a cut-off distance r(n)(x). We prove strong law results for (i) the critical cut-off function so that almost surely, the graph does not contain any node with out-degree zero for sufficiently large n and (ii) the maximum and minimum vertex degrees. We also provide a characterization of the cut-off function for which the number of nodes with out-degree zero converges in distribution to a Poisson random variable. We illustrate this result for a class of densities with compact support that have at most polynomial rates of decay to zero. Finally, we state a sufficient condition for an enhanced version of the above graph to be almost surely connected eventually.

Functional characterization, homology modeling and docking studies of beta-glucosidase responsible for bioactivation of cyanogenic hydroxynitrile glucosides from Leucaena leucocephala (subabul)

Glycosyl hydrolase family 1 beta-glucosidases are important enzymes that serve many diverse functions in plants including defense, whereby hydrolyzing the defensive compounds such as hydroxynitrile glucosides. A hydroxynitrile glucoside cleaving beta-glucosidase gene (Llbglu1) was isolated from Leucaena leucocephala, cloned into pET-28a (+) and expressed in E. coli BL21 (DE3) cells. The recombinant enzyme was purified by Ni-NTA affinity chromatography. The optimal temperature and pH for this beta-glucosidase were found to be 45 A degrees C and 4.8, respectively. The purified Llbglu1 enzyme hydrolyzed the synthetic glycosides, pNPGlucoside (pNPGlc) and pNPGalactoside (pNPGal). Also, the enzyme hydrolyzed amygdalin, a hydroxynitrile glycoside and a few of the tested flavonoid and isoflavonoid glucosides. The kinetic parameters K (m) and V (max) were found to be 38.59 mu M and 0.8237 mu M/mg/min for pNPGlc, whereas for pNPGal the values were observed as 1845 mu M and 0.1037 mu M/mg/min. In the present study, a three dimensional (3D) model of the Llbglu1 was built by MODELLER software to find out the substrate binding sites and the quality of the model was examined using the program PROCHEK. Docking studies indicated that conserved active site residues are Glu 199, Glu 413, His 153, Asn 198, Val 270, Asn 340, and Trp 462. Docking of rhodiocyanoside A with the modeled Llbglu1 resulted in a binding with free energy change (Delta G) of -5.52 kcal/mol on which basis rhodiocyanoside A could be considered as a potential substrate.

Further results on geometric properties of a family of relative entropies

This paper extends some geometric properties of a one-parameter family of relative entropies. These arise as redundancies when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the Kullback-Leibler divergence. They satisfy the Pythagorean property and behave like squared distances. This property, which was known for finite alphabet spaces, is now extended for general measure spaces. Existence of projections onto convex and certain closed sets is also established. Our results may have applications in the Rényi entropy maximization rule of statistical physics.

New Insights into Electronic and Geometric Effects in the Enhanced Photoelectrooxidation of Ethanol Using ZnO Nanorod/Ultrathin Au Nanowire Hybrids

Oxidation of small organic molecules in a fuel cell is a viable method for energy production. However, the key issue is the development of suitable catalysts that exhibit high efficiencies and remain stable during operation. Here, we demonstrate that amine-modified ZnO nanorods on which ultrathin Au nanowires are grown act as an excellent catalyst for the oxidation of ethanol. We show that the modification of the ZnO nanorods with oleylamine not only modifies the electronic structure favorably but also serves to anchor the Au nanowires on the nanorods. The adsorption of OH- species on the Au nanowires that is essential for ethanol oxidation is facilitated at much lower potentials as compared to bare Au nanowires leading to high activity. While ZnO shows negligible electrocatalytic activity under normal conditions, there is significant enhancement in the activity under light irradiation. We demonstrate a synergistic enhancement in the photoelectrocatalytic activity of the ZnO/Au nanowire hybrid and provide mechanistic explanation for this enhancement based on both electronic as well as geometric effects. The principles developed are applicable for tuning the properties of other metal/semiconductor hybrids with potentially interesting applications beyond the fuel cell application demonstrated here.