Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). A k-dimensional box is a Cartesian product of closed intervals a(1), b(1)] x a(2), b(2)] x ... x a(k), b(k)]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). Let P-c be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P-c) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension. In the other direction, using the already known bounds for partial order dimension we get the following: (I) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta) which is an improvement over the best known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0, unless NP=ZPP.

Diversity in Functional Organization of Class I and Class II Biotin Protein Ligase

The cell envelope of Mycobacterium tuberculosis (M. tuberculosis) is composed of a variety of lipids including mycolic acids, sulpholipids, lipoarabinomannans, etc., which impart rigidity crucial for its survival and pathogenesis. Acyl CoA carboxylase (ACC) provides malonyl-CoA and methylmalonyl-CoA, committed precursors for fatty acid and essential for mycolic acid synthesis respectively. Biotin Protein Ligase (BPL/BirA) activates apo-biotin carboxyl carrier protein (BCCP) by biotinylating it to an active holo-BCCP. A minimal peptide (Schatz), an efficient substrate for Escherichia coli BirA, failed to serve as substrate for M. tuberculosis Biotin Protein Ligase (MtBPL). MtBPL specifically biotinylates homologous BCCP domain, MtBCCP87, but not EcBCCP87. This is a unique feature of MtBPL as EcBirA lacks such a stringent substrate specificity. This feature is also reflected in the lack of self/promiscuous biotinylation by MtBPL. The N-terminus/HTH domain of EcBirA has the selfbiotinable lysine residue that is inhibited in the presence of Schatz peptide, a peptide designed to act as a universal acceptor for EcBirA. This suggests that when biotin is limiting, EcBirA preferentially catalyzes, biotinylation of BCCP over selfbiotinylation. R118G mutant of EcBirA showed enhanced self and promiscuous biotinylation but its homologue, R69A MtBPL did not exhibit these properties. The catalytic domain of MtBPL was characterized further by limited proteolysis. Holo-MtBPL is protected from proteolysis by biotinyl-59 AMP, an intermediate of MtBPL catalyzed reaction. In contrast, apo-MtBPL is completely digested by trypsin within 20 min of co-incubation. Substrate selectivity and inability to promote self biotinylation are exquisite features of MtBPL and are a consequence of the unique molecular mechanism of an enzyme adapted for the high turnover of fatty acid biosynthesis.

Memory Bandwidth and Power Reduction Using Lossy Reference Frame Compression in Video Encoding

Large external memory bandwidth requirement leads to increased system power dissipation and cost in video coding application. Majority of the external memory traffic in video encoder is due to reference data accesses. We describe a lossy reference frame compression technique that can be used in video coding with minimal impact on quality while significantly reducing power and bandwidth requirement. The low cost transformless compression technique uses lossy reference for motion estimation to reduce memory traffic, and lossless reference for motion compensation (MC) to avoid drift. Thus, it is compatible with all existing video standards. We calculate the quantization error bound and show that by storing quantization error separately, bandwidth overhead due to MC can be reduced significantly. The technique meets key requirements specific to the video encode application. 24-39% reduction in peak bandwidth and 23-31% reduction in total average power consumption are observed for IBBP sequences.

Goal Seeking for Robots in Unknown Environments

We consider the problem of goal seeking by robots in unknown environments. We present a frontier based algorithm for finding a route to a goal in a fully unknown environment, where information about the goal region (GR), the region where the goal is most likely to be located, is available. Our algorithm efficiently chooses the best candidate frontier cell, which is on the boundary between explored space and unexplored space, having the maximum ``goal seeking index'', to reach the goal in minimal number of moves. Modification of the algorithm is also proposed to further reduce the number of moves toward the goal. The algorithm has been tested extensively in simulation runs and results demonstrate that the algorithm effectively directs the robot to the goal and completes the search task in minimal number of moves in bounded as well as unbounded environments. The algorithm is shown to perform as well as a state of the art agent centered search algorithm RTAA*, in cluttered environments if exact location of the goal is known at the beginning of the mission and is shown to perform better in uncluttered environments.

Design of logical topologies for wavelength-routed optical networks

his paper studies the problem of designing a logical topology over a wavelength-routed all-optical network (AON) physical topology, The physical topology consists of the nodes and fiber links in the network, On an AON physical topology, we can set up lightpaths between pairs of nodes, where a lightpath represents a direct optical connection without any intermediate electronics, The set of lightpaths along with the nodes constitutes the logical topology, For a given network physical topology and traffic pattern (relative traffic distribution among the source-destination pairs), our objective is to design the logical topology and the routing algorithm on that topology so as to minimize the network congestion while constraining the average delay seen by a source-destination pair and the amount of processing required at the nodes (degree of the logical topology), We will see that ignoring the delay constraints can result in fairly convoluted logical topologies with very long delays, On the other hand, in all our examples, imposing it results in a minimal increase in congestion, While the number of wavelengths required to imbed the resulting logical topology on the physical all optical topology is also a constraint in general, we find that in many cases of interest this number can be quite small, We formulate the combined logical topology design and routing problem described above (ignoring the constraint on the number of available wavelengths) as a mixed integer linear programming problem which we then solve for a number of cases of a six-node network, Since this programming problem is computationally intractable for larger networks, we split it into two subproblems: logical topology design, which is computationally hard and will probably require heuristic algorithms, and routing, which can be solved by a linear program, We then compare the performance of several heuristic topology design algorithms (that do take wavelength assignment constraints into account) against that of randomly generated topologies, as well as lower bounds derived in the paper.

Electron transfer reaction in the marcus inverted region: role of high frequency vibrational modes

A theoretical study of the dynamics of photo-electron transfer reactions in the Marcus inverted regime is presented. This study is motivated partly by the recent proposal of Barbara et al. (J. Phys. Chem. 96, 3728, 1991) that a minimal model of an electron transfer reaction should consist of a polar solvent mode (X), a low frequency vibrational mode (Q) and one high frequency mode (q). Interplay between these modes may be responsible for the crossover observed in the dynamics from a solvent controlled to a vibrational controlled electron transfer. The following results have been obtained. (i) In the case of slowly relaxing solvents, the proximity of the point of excitation to an effective sink on the excited surface is critical in determining the decay of the reactant population. This is because the Franck-Condon overlap between the reactant ground and the product excited states decreases rapidly with increase in the quantum number of the product vibrational state. (ii) Non-exponential solvation dynamics has an important effect in determining the rates of electron transfer. Especially, a biphasic solvation and a large coupling between the reactant and the product states both may be needed to explain the experimental results. ©1996 American Institute of Physics

Lossless and lossy image compression using Boolean function minimization

A novel approach for lossless as well as lossy compression of monochrome images using Boolean minimization is proposed. The image is split into bit planes. Each bit plane is divided into windows or blocks of variable size. Each block is transformed into a Boolean switching function in cubical form, treating the pixel values as output of the function. Compression is performed by minimizing these switching functions using ESPRESSO, a cube based two level function minimizer. The minimized cubes are encoded using a code set which satisfies the prefix property. Our technique of lossless compression involves linear prediction as a preprocessing step and has compression ratio comparable to that of JPEG lossless compression technique. Our lossy compression technique involves reducing the number of bit planes as a preprocessing step which incurs minimal loss in the information of the image. The bit planes that remain after preprocessing are compressed using our lossless compression technique based on Boolean minimization. Qualitatively one cannot visually distinguish between the original image and the lossy image and the value of mean square error is kept low. For mean square error value close to that of JPEG lossy compression technique, our method gives better compression ratio. The compression scheme is relatively slower while the decompression time is comparable to that of JPEG.

Structure-potential relationship and nature of disorder in liquids and glassy solids

A method based on the minimal-spanning tree is extended to a collection of points in three dimensions. Two parameters, the average edge length and its standard deviation characterize the disorder. The structural phase diagram for a monatomic system of particles and the characteristic values for the uniform random distribution of points have been obtained. The method is applied to hard spheres and Lennard-Jones systems. These systems occupy distinct regions in the structural phase diagram. The structure of the Lennard-Jones system approaches that of the defective close-packed arrangements at low temperatures whereas in the liquid regime, it deviates from the close-packed configuration.

A novel zinc bis(thiosemicarbazone) complex for live cell imaging

Fluorescent zinc complexes have recently attracted a lot of interest owing to their vast applications in cellular imaging. We report the synthesis as well as physical, chemical and biological studies of a novel zinc glyoxalbis(4-methyl-4-phenyl-3-thiosemicarbazone), Zn (GTSC)](3), complex. As compared with the well-studied zinc biacetylbis(4-methyl-3-thiosemicarbazone), Zn(ATSM), complex, which was used as a reference, Zn(GTSC)](3) had 2.5-fold higher fluorescence. When cellular fluorescence was measured using flow cytometry, we observed that Zn(GTSC)](3) had 3.4-fold to 12-fold higher fluorescence than Zn(ATSM) in various cell lines (n = 9) of different tissue origin. Confocal fluorescence microscopy results showed that Zn(GTSC)](3) appeared to have a nuclear localization within 30 mm of addition to MCF7 cells. Moreover, Zn(GTSC)](3) showed minimal cytotoxicity compared with Zn(ATSM), suggesting that Zn(GTSC)](3) may be less deleterious to cells when used as an imaging agent. Our data suggest that the novel Zn(GTSC)](3) complex can potentially serve as a biocompatible fluorescent imaging agent for live cells.

Electrical and Optical Properties of Diketopyrrolopyrrole-Based Copolymer Interfaces in Thin Film Devices

Two donor acceptor diketopyrrolopyrrole (DPP)-based copolymers (PDPP-BBT and TDPP-BBT) have been synthesized for their application in organic devices such as metal-insulator semiconductor (MIS) diodes and field-effect transistors (FETs). The semiconductor-dielectric interface was characterized by capacitance-voltage and conductance-voltage methods. These measurements yield an interface trap density of 4.2 x 10(12) eV(-1) cm(-2) in TDPP-BBT and 3.5 x 10(12) eV(-1) cm(-2) in PDPP-BBT at the flat-band voltage. The FETs based on these spincoated DPP copolymers display p-channel behavior with hole mobilities of the order 10(-3) cm(2)/(V s). Light scattering studies from PDPP-BBT FETs show almost no change in the Raman spectrum after the devices are allowed to operate at a gate voltage, indicating that the FETs suffer minimal damage due to the metal-polymer contact or the application of an electric field. As a comparison Raman intensity profile from the channel-Au contact layer in pentacene FETs are presented, which show a distinct change before and after biasing.

Triply-periodic balance surfaces

The list of possible G-H symmetries for triply-periodic balance surfaces, given by Koch and Fischer, is studied with a view to finding new types. It is found that balance surfaces exist for all the cases that were labelled as undecided in the work of Koch and Fischer. For some of these, new minimal surfaces have been found, with the aid of Brakke's 'Surface Evolver'. (C) 1997 Elsevier Science B.V.

Quantum clustering and network analysis of MD simulation trajectories to probe the conformational ensembles of protein-ligand interactions

In this article, we present a novel application of a quantum clustering (QC) technique to objectively cluster the conformations, sampled by molecular dynamics simulations performed on different ligand bound structures of the protein. We further portray each conformational population in terms of dynamically stable network parameters which beautifully capture the ligand induced variations in the ensemble in atomistic detail. The conformational populations thus identified by the QC method and verified by network parameters are evaluated for different ligand bound states of the protein pyrrolysyl-tRNA synthetase (DhPylRS) from D. hafniense. The ligand/environment induced re-distribution of protein conformational ensembles forms the basis for understanding several important biological phenomena such as allostery and enzyme catalysis. The atomistic level characterization of each population in the conformational ensemble in terms of the re-orchestrated networks of amino acids is a challenging problem, especially when the changes are minimal at the backbone level. Here we demonstrate that the QC method is sensitive to such subtle changes and is able to cluster MD snapshots which are similar at the side-chain interaction level. Although we have applied these methods on simulation trajectories of a modest time scale (20 ns each), we emphasize that our methodology provides a general approach towards an objective clustering of large-scale MD simulation data and may be applied to probe multistate equilibria at higher time scales, and to problems related to protein folding for any protein or protein-protein/RNA/DNA complex of interest with a known structure.

Throughput Maximization of Delay-Constrained Traffic in Wireless Energy Harvesting Sensors

A wireless Energy Harvesting Sensor (EHS) needs to send data packets arriving in its queue over a fading channel at maximum possible throughput while ensuring acceptable packet delays. At the same time, it needs to ensure that energy neutrality is satisfied, i.e., the average energy drawn from a battery should equal the amount of energy deposited in it minus the energy lost due to the inefficiency of the battery. In this work, a framework is developed under which a system designer can optimize the performance of the EHS node using power control based on the current channel state information, when the EHS node employs a single modulation and coding scheme and the channel is Rayleigh fading. Optimal system parameters for throughput optimal, delay optimal and delay-constrained throughput optimal policies that ensure energy neutrality are derived. It is seen that a throughput optimal (maximal) policy is packet delay-unbounded and an average delay optimal (minimal) policy achieves negligibly small throughput. Finally, the influence of the harvested energy profile on the performance of the EHS is illustrated through the example of solar energy harvesting.

Common mode DC bus filter for Active Front-End converter

Active Front-End (AFE) converter operation produces electrically noisy DC bus on common mode basis. This results in higher ground current as compared to three phase diode bridge rectifier. Filter topologies for DC bus have to deal problems with switching frequency and harmonic currents. The proposed filter approach reduces common mode voltage and circulates third harmonic current within the system, resulting in minimal ground current injection. The filtering technique, its constrains and design to attenuate common mode voltage and eliminate lower order harmonics injection to ground is discussed. The experimental results for operation of the converter with both SPWM and CSVPWM are presented.

Diperoxovanadate can substitute for H(2)O(2) at much lower concentration in inducing features of premature cellular senescence in mouse fibroblasts (NIH3T3)

Stress induced premature senescence (SIPS) in mammalian cells is an accelerated ageing response and experimentally obtained on treatment of cells with high concentrations of H(2)O(2), albeit at sub-lethal doses, because H(2)O(2) gets depleted by abundant cellular catalase. In the present study diperoxovanadate (DPV) was used as it is known to be stable at physiological pH, to be catalase-resistant and to substitute for H(2)O(2) in its activities at concentrations order of magnitudes lower. On treating NIH3T3 cells with DPV, SIPS-like morphology was observed along with an immediate response of rounding of the cells by disruption of actin cytoskeleton and transient G2/M arrest. DPV could bring about growth arrest and senescence associated features at 25 mu M dose, which were not seen with similar doses of either H(2)O(2) or vanadate. A minimal dose of 150 mu M of H(2)O(2) was required to induce similar affects as 25 mu M DPV. Increase in senescent associated markers such as p21, HMGA2 and PAI-1 was more prominent in DPV treated cells compared to similar dose of H(2)O(2). DPV-treated cells showed marked relocalization of Cyclin D1 from nucleus to cytoplasm. These results indicate that DPV, stable inorganic peroxide, is more efficient in inducing SIPS at lower concentrations compared to H(2)O(2). (C) 2011 Elsevier Ireland Ltd. All rights reserved.