Abstract

One important challenge in wireless ad hoc networks is to achieve collision free communication. Many MAC layer protocols have been proposed by considering various communication models of the ad hoc networks. One such protocol is TDMA, which provides for interference free communication while providing some bound on the packet delay. However, most proposed TDMA schemes can perform scheduling transmissions among nodes that are within transmission range. This is due to the simplistic modeling of the underlying network. Recently, more practical network models and overlay construction algorithms have been proposed that consider the interference among nodes as well. Existing TDMA protocols are unsuitable for such models as they will have to consider the interference range of the nodes as well. This requires that the TDMA protocol operate in a global perspective while working as a local-control algorithm. In this work, we describe a novel TDMA protocol that is suitable for such realistic and practical network models. We also extend the TDMA protocol to handle other difficulties such as membership changes within transmission range and interference range. Some networks also have to deal with sleeping nodes that wake up periodically. Our TDMA scheme employs a simple control phase and a data phase to handle such tasks. Some of the benefits of our solution are that no knowledge of the network parameters such as the size or an estimate of the size are used. The overhead of our scheme is also very low and (control) messages exchanged are of small size. Our solution will also be self-stabilizing which is an important property for distributed systems. To the best of our knowledge, our TDMA protocol is the first MAC layer protocol for such realistic network models. Additionally, we report some experimental results of our scheme.

Abstract

Graphics processing units provide a large compu-tational power at a very low price which position them as an ubiquitous accelerator. General purpose programming on the graphics processing units (GPGPU) is best suited for regular data parallel algorithms. They are not directly amenable for algorithms which have irregular data access patterns such as list ranking, and finding the connected components of a graph, and the like. In this work, we present a GPU-optimized implementation for finding the connected components of a given graph. Our implementation tries to minimize the impact of irregularity, both at the data level and functional level. Our implementation achieves a speed up of 9 to 12 times over the best sequential CPU implementation. For instance, our implementation finds connected components of a graph of 10 million nodes and 60 million edges in about 500 milliseconds on a GPU, given a random edge list. We also draw interesting observations on why PRAM algorithms, such as the Shiloach-Vishkin algorithm may not be a good fit for the GPU and how they should be modified.

Abstract

Distance bounding protocols are used by nodes in wireless networks to calculate upper bounds on their distances to other nodes. However, dishonest nodes in the network can turn the calculations both illegitimate and inaccurate when they participate in protocol executions. It is important to analyze protocols for the possibility of such violations. Past efforts to analyze distance bounding protocols have only been manual. However, automated approaches are important since they are quite likely to find flaws that manual approaches cannot, as witnessed in literature for analysis pertaining to key establishment protocols. In this paper, we use the constraint solver tool to automatically analyze distance bounding protocols. We first formulate a new trace property called Secure Distance Bounding (SDB) that protocol executions must satisfy. We then classify the scenarios in which these protocols can operate considering the (dis) honesty of nodes and location of the attacker in the network. Finally, we extend the constraint solver so that it can be used to test protocols for violations of SDB in these scenarios and illustrate our technique on some published protocols.

Abstract

Thermal, chemical and force induced unfolding are three primary experimental approaches that have been successfully used to study protein folding and associated pathways. Recent experimental studies have demonstrated the importance of the use of combination of these techniques to study various aspects of protein folding. We have addressed this issue using two different model systems. The effect of temperature on the mechanical unfolding of titin I27 immunoglobulin domain has been investigated using steered molecular dynamics (MD) simulations performed both at constant velocity and constant force. The maximum force of unfolding decreases with respect to the increase in the temperature, but the extension corresponding to this force remains similar. However, we observed that the maximum probable unfolding force steadily decreases with an increase in temperature (see below). Several computations done on each of the temperatures consistently reproduce these effects. The results will be discussed in light of the available experimental data, and molecular level details on the conformational changes that effect such temperature dependence will be presented. In another study, we have done rigorous free energy calculations on the unfolding of Trp-mini cage protein using umbrella sampling MD simulations. Calculations were done with respect to increase in the temperature, and with respect to the concentration of the urea solution. The change in the free energy profiles, and the effect of external perturbations, and the atomistic details of the unfolding will be discussed. Temperature

Abstract

The enlarging HIV/AIDS pandemic and the virus’ ability to develop resistance to anti-retroviral therapy requires the development of new drugs based on novel targets. Viruses interact extensively with the host at the cellular and molecular levels, which is necessary for the expression of viral proteins and replication of viral genomes. At another level, these interactions also help the virus evade host immune responses. Besides the prototypic retroviral proteins (Gag, Pol and Env), HIV-1 also expresses two regulatory proteins (Tat and Rev) and four accessory proteins (Nef, Vif, Vpr and Vpu). The accessory proteins are not required for viral replication in vitro, but are critical for pathogenesis and disease development in the host. We have focused our efforts on two of these – Nef and Vpu, with an aim to understand their interactions with host proteins and the functional consequences of these interactions for HIV-1 infection and pathogenesis. The Nef protein binds to multiple host proteins to optimize the host cell environment and to enable infected cells to evade the host immune response. A major property of Nef is to downregulate surface expression of the CD4, MHC I and MHC II proteins, by increasing the endocytosis of these molecules. We also discovered that Nef binds to the cytoplasmic domains of the B7 family of costimulatory proteins – CD80 and CD86; this results in their removal from the cell surface and sequestration to the Golgi compartment (1-3). We have now developed an in vitro screen based on purified recombinant Nef proteins and a 20-mer synthetic peptide from the cytoplasmic domain of CD80 and CD86. A chemical library comprising of 1064 compounds was screened and ~7% compounds were obtained as hits, which inhibited the Nef-CD80/CD86 interaction. These compounds are now being evaluated in a cellbased assay and an independent dose dependent response assay. The top hits will be used in a combinatorial chemical approach to synthesize a large array of new molecules for further screening using the in vitro and cell-based screens. The HIV-1 Vpu protein is required for the release of new virions from the surface of infected cells; for this the transmembrane domain of Vpu is critical. Using the Topology Data Bank of Transmembrane Proteins (TOPDB) database we extracted 13 alpha-helical sequences that closely resemble the Vpu-TM domain. We have taken the top two hits and have constructed recombinant Vpu proteins in which the native TM domain was replaced by the identified sequences. These recombinant proteins were successfully expressed in HEK293 cells, and are now being tested for their effects on virion release as well as their ability to inhibit Vpu activity. We describe here two paradigms to screen for anti-HIV activity based on proteinprotein interactions. Results will be presented for both of these.

Abstract

Hyperthermophilic proteins are naturally occurring proteins that are capable of retaining their structure, and performing their normal functions at temperatures above 80º C. Identification of the structural determinants that are crucial for such a remarkable stability is of fundamental importance, and has potential applications in biocatalysis. Molecular dynamics simulations on two such proteins (Sac7d and Sso7d) illustrated the importance of ion pair interactions for achieving thermostability.1 Previous studies have indicated that the formation of ion pair interactions does not contribute to stability due to high desolvation penalty, while others have argued in favor of stabilization. We have performed umbrella sampling simulations on model systems at different temperatures, which showed that with increasing temperature, the stability of the ion pair interactions become highly favorable. Thus, protein folding involving association of an ion pair may lead to stabilization at enhanced temperature close to the growth temperature of the hyperthemophiles. We have also investigated the effect of protein-DNA interactions, and their role in DNA stabilization at these conditions.2 Canonical B- to A-form transitions were observed in the protein-DNA complexes, and the protein-DNA interaction energies are used to explain the sequence nonspecific nature of the binding activity. The crucial nonbonded interactions that facilitate extraordinary thermal stability of proteins and DNAs in thermophiles will be discussed in this presentation.

Abstract

One of the most efficient chemical transformations in the natural product synthesis of steroid like molecules is the synthetic methodology that combines the pericyclic and intramolecular reactions termed as transannular Diels-Alder reaction (TADA). TADA reactions occur in (x+y+2)-membered triene macrocycles, which contain both the diene and the dienophile, to form A.B.C [x.6.y] type tricyclic compounds. Initially, a validation study was carried out to identify an appropriate method for studying this reaction pathway. Several methods including HF, post-HF methods such as Mpx and CC, and density functional B3LYP level were considered, and we found that B3LYP method used along with a reasonably smaller basis set (6-31G(d)) is adequate enough. We have extensively studied the TADA reactions of six possible cis/trans-isomers of 14-membered macrocycles, and correlated their reactivities with experimental data wherever applicable. We also have studied the effect of ring size on the TADA reactivity by performing calculations on 552, 562, 572, 652, 672, 752, 762 and 772 systems using the B3LYP level employing the 6-31G(d) and the cc-pVTZ basis sets. We have shown that the activation energy and the reaction energy decrease with respect to the increase in the ring size. In addition to the activation energies, the conformational preferences of the reactants were suggestd to be crucial for the reaction to take place, and on its stereochemical outcome. We have studied their conformational properties using replica exchange molecular dynamics simulations. Initially, we obtained force field parameters for the macrocyclic trienes based on MP2 calculations on six model systems. The analysis concentrated on the dihedral angle corresponding to the central bond of the diene moiety, and the distance between the reaction centers. The extent of conformational sampling of each of the macrocycles is compared with the reactivities. The presentation will discuss the TADA reactivity in terms of activation energies corresponding to the transition states of the reactions, and also based on the conformational properties of the reactants.

Abstract

Sac7d belongs to a family of chromosomal proteins, which are crucial for thermal stabilization of DNA at higher growth temperatures. It is capable of binding DNA nonspecifically, and is responsible for the increase in the melting temperature of DNA in the bound form up to 85 °C. Molecular dynamics (MD) simulations were performed at different temperatures on two protein-DNA complexes of Sac7d. Various structural and energetic parameters were calculated to examine the DNA stability and to investigate the conformational changes in DNA and the protein-DNA interactions. Room temperature simulations indicated very good agreement with the experimental structures. The protein structure is nearly unchanged at both 300 and 360 K, and only up to five base pairs of the DNA are stabilized by Sac7d at 360 K. However, the MD simulations on DNA alone systems show that they lose their helical structures at 360 K further supporting the role of Sac7d in stabilizing the oligomers. At higher temperatures (420 and 480 K), DNA undergoes denaturation in the presence and the absence of the protein. The DNA molecules were found to undergo B- to A-form transitions consistent with experimental studies, and the extent of these transitions are examined in detail. The extent of sampling B- and A-form regions was found to show temperature and sequence dependence. Multiple MD simulations yielded similar results validating the proposed model. Interaction energy calculations corresponding to protein-DNA binding indicates major contribution due to DNA backbone, explaining the nonspecific interactions of Sac7d.

Abstract

Riboswitches are RNA-based genetic control elements that function via a conformational transition mechanism when a specific target molecule binds to its binding pocket. To facilitate an atomic detail interpretation of experimental investigations on the role of the adenine ligand on the conformational properties and kinetics of folding of the add adenine riboswitch, we performed molecular dynamics simulations in both the presence and the absence of the ligand. In the absence of ligand, structural deviations were observed in the J23 junction and the P1 stem. Destabilization of the P1 stem in the absence of ligand involves the loss of direct stabilizing interactions with the ligand, with additional contributions from the J23 junction region. The J23 junction of the riboswitch is found to be more flexible, and the tertiary contacts among the junction regions are altered in the absence of the adenine ligand; results suggest that the adenine ligand associates and dissociates from the riboswitch in the vicinity of J23. Good agreement was obtained with the experimental data with the results indicating dynamic behavior of the adenine ligand on the nanosecond time scale to be associated with the dynamic behavior of hydrogen bonding with the riboswitch. Results also predict that direct interactions of the adenine ligand with U74 of the riboswitch are not essential for stable binding although it is crucial for its recognition. The possibility of methodological artifacts and force-field inaccuracies impacting the present observations was checked by additional molecular dynamics simulations in the presence of 2,6-diaminopurine and in the crystal environment. Copyright (c) 2010 Elsevier Ltd. All rights reserved.

Abstract

DNA-RNA hybrids are heterogeneous nucleic acid duplexes that contain a DNA strand and a RNA strand. They are identified as key intermediates in transcription, and in other biological processes. These novel molecules have also been recognized as potential candidates in antisense therapy. While DNA exists in B-form, and RNA in A-form, the process of hybridization between these two distinct conformations, and the resultant structural features of the hybrid duplexes are interesting in their own right. It has been suggested that hybrids have unique conformational properties that form the basis of Ribonuclease H (RNase H) activity only on these molecules, and not on pure DNA or RNA. Quantitative examination of the conformational properties of hybrids is very important for understanding the RNase H activity. Several nanosecond long molecular dynamics (MD) simulations were performed on all the available structures in presence of explicit solvent environment. All the MD simulations were performed using the CHARMM27 all atom nucleic acid force field. In addition to the MD simulations on hybrids, control simulations were also performed on pure DNA and RNA duplexes with identical sequences. Several structural, dynamic and energetic properties including deviations, flexibility, intramolecular entropy, helical properties, and backbone conformational preferences were computed. The conformational properties of the sugar puckering angles revealed interesting trends that depend on the sequence of the duplex. RNA strands in all the duplexes sample conformational regions corresponding to a pure-A form nucleic acid. However, the DNA strands adopt mixing of A- and B- type conformations resulting in intermediate structures for the hybrids. The extent of this mixing depends primarily on the relative purine to pyrimidine composition ratio in the DNA strands, and sequence effects. The presentation will focus on the structural and dynamic properties of hybrid duplexes in comparison with those of pure-RNA and DNA duplexes.