An analytical approach to the study of cooperation in wireless ad hoc networks

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete noncooperation) are inimical to the interests of a user. In this paper, we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e., their actions are strictly determined by self interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we are able to determine the optimal share of service that each node should receive. We define this to be the rational Pareto optimal operating point. We then propose a distributed and scalable acceptance algorithm called Generous TIT-FOR-TAT (GTFT). The acceptance algorithm is used by the nodes to decide whether to accept or reject a relay request. We show that GTFT results in a Nash equilibrium and prove that the system converges to the rational and optimal operating point.

Modeling the role of competition and cooperation in the evolution of katydid acoustic synchrony

The precise timing of individual signals in response to those of signaling neighbors is seen in many animal species. Synchrony is the most striking of the resultant timing patterns. One of the best examples of acoustic synchrony is in katydid choruses where males produce chirps with a high degree of temporal overlap. Cooperative hypotheses that speculate on the evolutionary origins of acousti synchrony include the preservation of the species-specific call pattern, reduced predation risks, and increased call intensity. An alternative suggestion is that synchrony evolved as an epiphenomenon of competition between males in response to a female preference for chirps that lead other chirps. Previous models investigating the evolutionary origins of synchrony focused only on intrasexual competitive interactions. We investigated both competitive and cooperative hypotheses for the evolution of synchrony in the katydid Mecopoda ``Chirper'' using physiologically and ecologically realistic simulation models incorporating the natural variation in call features, ecology, female preferences, and spacing patterns, specifically aggregation. We found that although a female preference for leading chirps enables synchronous males to have some selective advantage, it is the female preference for the increased intensity of aggregations of synchronous males that enables synchrony to evolve as an evolutionarily stable strategy.

Chemistry and biology of DNA methyltransferases

Recognition of a specific DNA sequence by a protein is probably the best example of macromolecular interactions leading to various events. It is a prerequisite to understanding the basis of protein-DNA interactions to obtain a better insight into fundamental processes such as transcription, replication, repair, and recombination. DNA methyltransferases with varying sequence specificities provide an excellent model system for understanding the molecular mechanism of specific DNA recognition. Sequence comparison of cloned genes, along with mutational analyses and recent crystallographic studies, have clearly defined the functions of various conserved motifs. These enzymes access their target base in an elegant manner by flipping it out of the DNA double helix. The drastic protein-induced DNA distortion, first reported for HhaI DNA methyltransferase, appears to be a common mechanism employed by various proteins that need to act on bases. A remarkable feature of the catalytic mechanism of DNA (cytosine-5) methyltransferases is the ability of these enzymes to induce deamination of the target cytosine in the absence of S-adenosyl-L-methionine or its analogs. The enzyme-catalyzed deamination reaction is postulated to be the major cause of mutational hotspots at CpG islands responsible for various human genetic disorders. Methylation of adenine residues in Escherichia coli is known to regulate various processes such as transcription, replication, repair, recombination, transposition, and phage packaging.

Inhibition of a Protein Tyrosine Phosphatase Using Mesoporous Oxides

The feasibility of utilizing mesoporous matrices of alumina and silica for the inhibition of enzymatic activity is presented here. These studies were performed on a protein tyrosine phosphatase by the name chick retinal tyrosine phosphotase-2 (CRYP-2), a protein that is identical in sequence to the human glomerular epithelial protein-1 and involved in hepatic carcinoma. The inhibition of CRYP-2 is of tremendous therapeutic importance. Inhibition of catalytic activity was examined using the Sustained delivery of p-nitrocatechol sulfate (pNCS) from bare and amine functionalized mesoporous silica (MCM-48) and mesoporous alumina (Al2O3). Among the various mesoporous matrices employed, amine functionalized MCM-48 exhibited the best release of pNCS and also inhibition of CRYP-2. The maximum speed of reaction nu(max) (= 160 +/- 10 mu mol/mnt/mg) and inhibition constant K-i (=85.0 +/- 5.0 mu mol) estimated using a competitive inhibition model were Found to be very similar to inhibition activities of protein tyrosine phosphatases using other methods.

New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.