Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.

On the Gaussian Many-to-One X Channel

In this paper, the Gaussian many-to-one X channel (XC), which is a special case of general multiuser XC, is studied. In the Gaussian many-to-one XC, communication links exist between all transmitters and one of the receivers, along with a communication link between each transmitter and its corresponding receiver. As per the XC assumption, transmission of messages is allowed on all the links of the channel. This communication model is different from the corresponding manyto- one interference channel (IC). Transmission strategies, which involve using Gaussian codebooks and treating interference from a subset of transmitters as noise, are formulated for the above channel. Sum-rate is used as the criterion of optimality for evaluating the strategies. Initially, a 3 x 3 many-to-one XC is considered and three transmission strategies are analyzed. The first two strategies are shown to achieve sum-rate capacity under certain channel conditions. For the third strategy, a sum-rate outer bound is derived and the gap between the outer bound and the achieved rate is characterized. These results are later extended to the K x K case. Next, a region in which the many-to-one XC can be operated as a many-to-one IC without the loss of sum-rate is identified. Furthermore, in the above region, it is shown that using Gaussian codebooks and treating interference as noise achieve a rate point that is within K/2 -1 bits from the sum-rate capacity. Subsequently, some implications of the above results to the Gaussian many-to-one IC are discussed. Transmission strategies for the many-to-one IC are formulated, and channel conditions under which the strategies achieve sum-rate capacity are obtained. A region where the sum-rate capacity can be characterized to within K/2 -1 bits is also identified. Finally, the regions where the derived channel conditions are satisfied for each strategy are illustrated for a 3 x 3 many-to-one XC and the corresponding many-to-one IC.

PIV study on the dimple mid-plane of a narrow rectangular channel with dimples applied to one wall

This paper presents an investigation of the fluid flow in the fully developed portion of a rectangular channel (Aspect Ratio of 2) with dimples applied to one wall at channel Reynolds numbers of 20,000, 30,000, and 40,000. The dimples are applied in a staggered-row, racetrack configuration. Results for three different dimple geometries are presented: a large dimple, small dimple, and double dimple. Heat transfer and aerodynamic results from preceding works are presented in Nusselt number and friction factor augmentation plots as determined experimentally. Using particle image velocimetry, the region near the dimple feature is studied in detail in the location of the entrainment and ejection of vortical packets into and out of the dimple; the downstream wake region behind each dimple is also studied to examine the effects of the local flow phenomenon that result in improved heat transfer in the areas of the channel wall not occupied by a feature. The focus of the paper is to examine the secondary flows in these dimpled channels in order to support the previously presented heat transfer trends. The flow visualization is also intended to improve the understanding of the flow disturbances in a dimpled channel; a better understanding of these effects would lead the development of more effective channel cooling designs. Copyright © 2011 by ASME.

Physical Layer Network Coding for the K-User Multiple Access Relay Channel

We propose a Physical layer Network Coding (PNC) scheme for the K-user wireless Multiple Access Relay Channel, in which K source nodes want to transmit messages to a destination node D with the help of a relay node R. The proposed scheme involves (i) Phase 1 during which the source nodes alone transmit and (ii) Phase 2 during which the source nodes and the relay node transmit. At the end of Phase 1, the relay node decodes the messages of the source nodes and during Phase 2 transmits a many-to-one function of the decoded messages. To counter the error propagation from the relay node, we propose a novel decoder which takes into account the possibility of error events at R. It is shown that if certain parameters are chosen properly and if the network coding map used at R forms a Latin Hypercube, the proposed decoder offers the maximum diversity order of two. Also, it is shown that for a proper choice of the parameters, the proposed decoder admits fast decoding, with the same decoding complexity order as that of the reference scheme based on Complex Field Network Coding (CFNC). Simulation results indicate that the proposed PNC scheme offers a large gain over the CFNC scheme.

The two-component signalling networks of Mycobacterium tuberculosis display extensive cross-talk in vitro

Two-component systems (TCSs), which contain paired sensor kinase and response regulator proteins, form the primary apparatus for sensing and responding to environmental cues in bacteria. TCSs are thought to be highly specific, displaying minimal cross-talk, primarily due to the co-evolution of the participating proteins. To assess the level of cross-talk between the TCSs of Mycobacterium tuberculosis, we mapped the complete interactome of the M. tuberculosis TCSs using phosphotransfer profiling. Surprisingly, we found extensive crosstalk among the M. tuberculosis TCSs, significantly more than that in the TCSs in Escherichia coli or Caulobacter crescentus, thereby offering an alternate to specificity paradigm in TCS signalling. Nearly half of the interactions we detected were significant novel cross-interactions, unravelling a potentially complex signalling landscape. We classified the TCSs into specific `one-to-one' and promiscuous `one-to-many' and `many-to-one' circuits. Using mathematical modelling, we deduced that the promiscuous signalling observed can explain several currently confounding observations about M. tuberculosis TCSs. Our findings suggest an alternative paradigm of bacterial signalling with significant cross-talk between TCSs yielding potentially complex signalling landscapes.

Basic Needs and Much More With One Kilowatt Per Capita

Conventional thinkin g holds that increased energy consumption is a prerequisite for economic and social development. This belief, together With the prospect of dwindling global petroleum supplies and the high costs of expanding energy supply generally, lead many to believe that it is not feasible to improve living standards substantially in the developing countries. But by shifting to high-quality energy carriers and by exploiting cost-effective opportunities for more efficient energy use, it would be possible to satisfy basic human needs and to provide considerable further improvements in living standards without significantly increasing per-capita energy use above the present level.

Voting Paths

We consider a variant of the popular matching problem here. The input instance is a bipartite graph $G=(\mathcal{A}\cup\mathcal{P},E)$, where vertices in $\mathcal{A}$ are called applicants and vertices in $\mathcal{P}$ are called posts. Each applicant ranks a subset of posts in an order of preference, possibly involving ties. A matching $M$ is popular if there is no other matching $M'$ such that the number of applicants who prefer their partners in $M'$ to $M$ exceeds the number of applicants who prefer their partners in $M$ to $M'$. However, the “more popular than” relation is not transitive; hence this relation is not a partial order, and thus there need not be a maximal element here. Indeed, there are simple instances that do not admit popular matchings. The questions of whether an input instance $G$ admits a popular matching and how to compute one if it exists were studied earlier by Abraham et al. Here we study reachability questions among matchings in $G$, assuming that $G=(\mathcal{A}\cup\mathcal{P},E)$ admits a popular matching. A matching $M_k$ is reachable from $M_0$ if there is a sequence of matchings $\langle M_0,M_1,\dots,M_k\rangle$ such that each matching is more popular than its predecessor. Such a sequence is called a length-$k$ voting path from $M_0$ to $M_k$. We show an interesting property of reachability among matchings in $G$: there is always a voting path of length at most 2 from any matching to some popular matching. Given a bipartite graph $G=(\mathcal{A}\cup\mathcal{P},E)$ with $n$ vertices and $m$ edges and any matching $M_0$ in $G$, we give an $O(m\sqrt{n})$ algorithm to compute a shortest-length voting path from $M_0$ to a popular matching; when preference lists are strictly ordered, we have an $O(m+n)$ algorithm. This problem has applications in dynamic matching markets, where applicants and posts can enter and leave the market, and applicants can also change their preferences arbitrarily. After any change, the current matching may no longer be popular, in which case we are required to update it. However, our model demands that we switch from one matching to another only if there is consensus among the applicants to agree to the switch. Hence we need to update via a voting path that ends in a popular matching. Thus our algorithm has applications here.

The Case for Non-Cooperative Multihoming of Users to Access Points in IEEE 802.11 WLANs

In many cases, a mobile user has the option of connecting to one of several IEEE 802.11 access points (APs),each using an independent channel. User throughput in each AP is determined by the number of other users as well as the frame size and physical rate being used. We consider the scenario where users could multihome, i.e., split their traffic amongst all the available APs, based on the throughput they obtain and the price charged. Thus, they are involved in a non-cooperative game with each other. We convert the problem into a fluid model and show that under a pricing scheme, which we call the cost price mechanism, the total system throughput is maximized,i.e., the system suffers no loss of efficiency due to selfish dynamics. We also study the case where the Internet Service Provider (ISP) could charge prices greater than that of the cost price mechanism. We show that even in this case multihoming outperforms unihoming, both in terms of throughput as well as profit to the ISP.

Effect of shear deformation on interfacial stresses in plated beams subjected to arbitrary loading

Bonding a fibre reinforced polymer (FRP) composite or metallic plate to the soffit of a reinforced concrete (RC), timber or metallic beam can significantly increase its strength and other aspects of structural performance. These hybrid beams are often found to fail due to premature debonding of the plate from the original beam in a brittle manner. This has led to the development of many analytical solutions over the last two decades to quantify the interfacial shear and normal stresses between the adherends. The adherends are subjected to axial, bending and shear deformations. However, most analytical solutions have neglected the influence of shear deformation of the adherends. For the few solutions which consider this effect in an approximate manner, their applicability is limited to one or two specific load cases. This paper presents a general analytical solution for the interfacial stresses in plated beams under an arbitrary loading with the shear deformation of the adherends duly considered. The shear stress distribution is assumed to be parabolic through the depth of the adherends in predicting the interfacial shear stress and Timoshenko's beam theory is adopted in predicting interfacial normal stress to account for the shear deformation. The solution is applicable to a beam of arbitrary prismatic cross-section bonded symmetrically or asymmetrically with a thin or thick plate, both having linear elastic material properties. The effect of shear deformation is illustrated through an example beam. The influence of material and geometric parameters of the adherends and adhesive on the interfacial stress concentrations at the plate end is discussed. (C) 2011 Elsevier Ltd. All rights reserved.

Fluorescence And Nmr-Studies Of The Binding Of Cholinergic Fluorescent-Probes To Horse Serum-Cholinesterase

The interaction of the cholinergic fluorescent probes, 1-(5-dimethyl-aminoaphthalene-1-sulfonamido) ethane-2-trimethylammonium perchlorate, 1-(5-dimethylaminonaphthalene-1-sulfonamido) pentane-5-trimethylammonium tartarate and 1-(5-dimethylaminonaphthalene-1-sulfonamido) decane-10- trimethylammonium tartarate with horse serum cholinesterase has been examined by fluorescence and n.m.r. methods. Fluorescence titrations show binding of the decane derivative to two sites on the protein whereas the lower homologs bind largely to one site. Active site inhibitors like curbamylcholine and decamethonium abolish binding of the decane derivative to the high affinity site. The inhibitors are largely without effect on the binding of the lower homologs. N.m.r. studies clearly establish immobilization of both ends of the molecule on binding in the case of the decane derivative, whereas in the lower homologs the dimethylamino group on the naphthalene ring is significantly more affected in the presence of enzyme. The probes are effective inhibitors of the enzyme with the decane derivative being two orders of magnitude more effective than its lower homologs. Based on the n.m.r., fluorescence and inhibition studies, a model for probe binding to the enzyme is advanced. It appears that the decane derivative binds with high affinity to the catalytic anionic site while the lower affinity site is assigned to a peripheral anionic site. The lower homologs probe only the peripheral site. A comparison of fluorescence, n.m.r. and inhibition studies with acetylcholinesterases from electric eel and bovine erythrocytes is presented.

Complex carbohydrates: 1. Conformational studies on some oligosaccharides related to N-glycosyl proteins which interact with concanavalin A

Empirical potential energy calculations have been carried out to determine the preferred conformations of some oligosaccharides having the trimannosidic core structure (Man3GlcNAc2) and which interact with concanavalin A. In the minimum energy conformations for the trimannosidic core the mannose residue on the Man α(1–6) arm comes close to one of the N-acetylglucosamine residues of the core. The addition of N-acetylglucosamine residues to the terminal mannose residues does not alter the preferred conformation of the trimannosidic core although it alters the relative preference of some of the higher energy conformations. The minimum energy conformation broadly agrees with available X-ray data. The presence of a bisecting N-acetylglucosamine residue on the middle mannose does not push the trimannosidic core to any new conformation but it does alter the relative preference for a particular conformation.

L_{2}- stability of a class of nonstationary feedback systems with dynamical nonlinear subsystems

A class of feedback systems, consisting of dynamical non-linear subsystems which arise in many diverse control applications, is analyzed for L2-stability. It is shown that, although a transformation of these systems to the familiar Lur'e configuration does not seem to be possible, a one-to-one correspondence may be effected between the stability properties of these and the Lur'e systems. Interesting stability criteria are developed by exploiting this characteristic.

Sequence Specific Interaction between Promoter DNA and Escherichia coli RNA Polymerase: Comparative Thermodynamic Analysis with One Immobilized Partner

Sequence specific interaction between DNA and protein molecules has been a subject of active investigation for decades now. Here, we have chosen single promoter containing bacteriophage Delta D-III T7 DNA and Escherichia coli RNA polymerase and followed their recognition at the air-water interface by using the surface plasmon resonance (SPR) technique, where the movement of one of the reacting species is restricted by way of arraying them on an immobilized support. For the Langmuir monolayer studies, we used a RNA polymerase with a histidine tag attached to one of its subunits, thus making it an xcellent substrate for Ni(II) ions, while the SPR Studies were done using biotin-labeled DNA immobilized on a streptavidin-coated chip. Detailed analysis of the thermodynamic parameters as a function of concentration and temperature revealed that the interaction of RNA polymerase with T7 DNA is largely entropy driven (83 (+/- 12) kcal mol(-1)) with a positive enthalpy of 13.6 (+/- 3.6) kcal mol(-1), The free energy of reaction determined by SPR and Langmuir-Blodgett technique was -11 (+/- 2) and -15.6 kcal mol(-1), respectively. The ability of these methods to retain the specificity of the recognition process was also established.

Deuterium-carbon correlation in static oriented systems using DAPT - A windowless multiple pulse sequence

We present a new method for establishing correlation between deuterium and its attached carbon in a deuterated liquid crystal. The method is based on transfer of polarization using the DAPT pulse sequence proposed originally for two spin half nuclei, now extended to a spin-1 and a spin-1/2 nuclei. DAPT utilizes the evolution of magnetization of the spin pair under two blocks of phase shifted BLEW-12 pulses on one of the spins separated by a 90 degree pulse on the other spin. The method is easy to implement and does not need to satisfy matching conditions unlike the Hartmann-Hahn cross-polarization. Experimental results presented demonstrate the efficacy of the method.

Anthranilic acid oxidase system of Tecomastans—III.: Studies on the conversion of o-aminophenol to catechol

The terminal step in the oxidation of anthranilic acid to catechol by anthranilic acid oxidase system from Tecoma stans, which converts o-aminophenol to catechol has been studied in detail. The reaction catalyses the conversion of one molecule of o-aminophenol to one molecule each of ammonia and catechol. The partially purified enzyme has a pH optimum of 6·2 in citrate-phosphate buffer and a temperature optimum of 45°. The metal ions, Mg2+, Co2+ and Fe3+ were inhibitory to the reaction. Metal chelating agents like 8-hydroxyquinoline, o-phenanthroline, and diethyldithiocarbamate, caused a high degree of inhibition. A sulfhydryl requirement for the reaction was inferred from the inhibition of the reaction by p-chloromercuribenzoate and its reversal with GSH. Atebrin inhibition was reversed by addition of FAD to the reaction mixture.