Scan cell reordering to minimize peak power during test cycle: A graph theoretic approach

Scan circuit is widely practiced DFT technology. The scan testing procedure consist of state initialization, test application, response capture and observation process. During the state initialization process the scan vectors are shifted into the scan cells and simultaneously the responses captured in last cycle are shifted out. During this shift operation the transitions that arise in the scan cells are propagated to the combinational circuit, which inturn create many more toggling activities in the combinational block and hence increases the dynamic power consumption. The dynamic power consumed during scan shift operation is much more higher than that of normal mode operation.

Faster algorithms for all-pairs small stretch distances in weighted graphs

Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick [14] showed that for any fixed ε> 0, stretch 1 1 + ε distances between all pairs of vertices in a weighted directed graph on n vertices can be computed in Õ(n ω) time, where ω < 2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. It is also known that all-pairs stretch 3 distances can be computed in Õ(n 2) time and all-pairs stretch 7/3 distances can be computed in Õ(n 7/3) time. Here we consider efficient algorithms for the problem of computing all-pairs stretch (2+ε) distances in G, for any 0 < ε < 1. We show that all pairs stretch (2 + ε) distances for any fixed ε> 0 in G can be computed in expected time O(n 9/4 logn). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n 9/4) for computing all-pairs stretch 5/2 distances in G. 1

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.

Interaction of G-Quadruplexes with Nonintercalating Duplex-DNA Minor Groove Binding Ligands

The enzyme telomerase synthesizes the G-rich DNA strands of the telomere and its activity is often associated with cancer. The telomerase may be therefore responsible for the ability of a cancer cell-to escape apoptosis. The G-rich DNA sequences often adopt tetra-stranded structure, known as the G-quadruplex DNA (G4-DNA). The stabilization of the telomeric DNA into the G4-DNA structures by small molecules has been the focus of many researchers for the design and development of new anticancer agents. The compounds which stabilize the G-quadruplex in the telomere inhibit the telomerase activity. Besides telomeres, the G4-DNA forming sequences are present in the genomic regions of biological significance including the transcriptional regulatory and promoter regions of several oncogenes. Inducing a G-quadruplex structure within the G-rich promoter sequences is a potential way of achieving selective gene regulation. Several G-quadruplex stabilizing ligands are known. Minor groove binding ligands (MGBLs) interact with the double-helical DNA through the minor grooves sequence-specifically and interfere with several DNA associated processes. These MGBLs when suitably modified switch their preference sometimes from the duplex DNA to G4-DNA and stabilize the G4-DNA as well. Herein, we focus on the recent advances in understanding the G-quadruplex structures, particularly made by the human telomeric ends, and review the results of various investigations of the interaction of designed organic ligands with the G-quadruplex DNA while highlighting the importance of MGBL-G-quadruplex interactions.

Acyclic edge coloring of 2-degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly contains seriesparallel graphs, outerplanar graphs, non - regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G)<=Delta + 2, where Delta = Delta(G) denotes the maximum degree of the graph. We prove the conjecture for 2-degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2-degenerate graph with maximum degree ?, then a'(G)<=Delta + 1. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68:1-27, 2011

Dimeric 1,3-Phenylene-bis(piperazinyl benzimidazole)s: Synthesis and Structure-Activity Investigations on their Binding with Human Telomeric G-Quadruplex DNA and Telomerase Inhibition Properties

Ligand-induced stabilization of G-quadruplex structures formed by the human telomeric DNA is an active area of research. The compounds which stabilize the G-quadruplexes often lead to telomerase inhibition. Herein we present the results of interaction of new monomeric and dimeric ligands having 1,3-phenylene-bis(piperazinyl benzimidazole) unit with G-quadruplex DNA (G4DNA) formed by human telomeric repeat d(G(3)T(2)A)(3)G(3)]. These ligands efficiently stabilize the preformed G4DNA in the presence of 100 mM monovalent alkali metal ions. Also, the G4DNA formed in the presence of low concentrations of ligands in 100 mM K+ adopts a highly stable parallel-stranded conformation. The G-quadruplexes formed in the presence of the dimeric compound are more stable than that induced by the corresponding monomeric counterpart. The dimeric ligands having oligo-oxyethylene spacers provide much higher stability to the preformed G4DNA and also exert significantly higher telomerase inhibition activity. Computational aspects have also been discussed.

Use of Vertex Index in Structure-Activity Analysis and Design of Molecules

The last few decades have witnessed application of graph theory and topological indices derived from molecular graph in structure-activity analysis. Such applications are based on regression and various multivariate analyses. Most of the topological indices are computed for the whole molecule and used as descriptors for explaining properties/activities of chemical compounds. However, some substructural descriptors in the form of topological distance based vertex indices have been found to be useful in identifying activity related substructures and in predicting pharmacological and toxicological activities of bioactive compounds. Another important aspect of drug discovery e. g. designing novel pharmaceutical candidates could also be done from the distance distribution associated with such vertex indices. In this article, we will review the development and applications of this approach both in activity prediction as well as in designing novel compounds.

Recent Developments in the Chemistry and Biology of G-Quadruplexes with Reference to the DNA Groove Binders

DNA is the chemotherapeutic target for treating diseases of genetic origin. Besides well-known double-helical structures (A, B, Z, parallel stranded-DNA etc.), DNA is capable of forming several multi-stranded structures (triplex, tetraplex, i-motif etc.) which have unique biological significance. The G-rich 3'-ends of chromosomes, called telomeres, are synthesized by telomerase, a ribonucleoprotein, and over-expression of telomerase is associated with cancer. The activity of telomerase is suppressed if the G-rich region is folded into the four stranded structures, called G-quadruplexes (G4-DNAs) using small synthetic ligands. Thus design and synthesis of new G4-DNA ligands is an attractive strategy to combat cancer. G4-DNA forming sequences are also prevalent in other genomic regions of biological significance including promoter regions of several oncogenes. Effective gene regulation may be achieved by inducing a G4-DNA structure within the G-rich promoter sequences. To date, several G4-DNA stabilizing ligands are known. DNA groove binders interact with the duplex B-DNA through the grooves (major and minor groove) in a sequence-specific manner. Some of the groove binders are known to stabilize the G4-DNA. However, this is a relatively under explored field of research. In this review, we focus on the recent advances in the understanding of the G4-DNA structures, particularly made from the human telomeric DNA stretches. We summarize the results of various investigations of the interaction of various organic ligands with the G4-DNA while highlighting the importance of groove binder-G4-DNA interactions.

Binding of Gemini Bisbenzimidazole Drugs with Human Telomeric G-Quadruplex Dimers: Effect of the Spacer in the Design of Potent Telomerase Inhibitors

The study of anticancer agents that act via stabilization of telomeric G-quadruplex DNA (G4DNA) is important because such agents often inhibit telomerase activity. Several types of G4DNA binding ligands are known. In these studies, the target structures often involve a single G4 DNA unit formed by short DNA telomeric sequences. However, the 3'-terminal single-stranded human telomeric DNA can form higher-order structures by clustering consecutive quadruplex units (dimers or nmers). Herein, we present new synthetic gemini (twin) bisbenzimidazole ligands, in which the oligo-oxyethylene spacers join the two bisbenzimidazole units for the recognition of both monomeric and dimeric G4DNA, derived from d(T2AG3)4 and d(T2AG3) 8 human telomeric DNA, respectively. The spacer between the two bisbenzimidazoles in the geminis plays a critical role in the G4DNA stability. We report here (i) synthesis of new effective gemini anticancer agents that are selectively more toxic towards the cancer cells than the corresponding normal cells; (ii) formation and characterization of G4DNA dimers in solution as well as computational construction of the dimeric G4DNA structures. The gemini ligands direct the folding of the single-stranded DNA into an unusually stable parallel-stranded G4DNA when it was formed in presence of the ligands in KCl solution and the gemini ligands show spacer length dependent potent telomerase inhibition properties.

Potential G-quadruplex formation at breakpoint regions of chromosomal translocations in cancer may explain their fragility

Genetic alterations like point mutations, insertions, deletions, inversions and translocations are frequently found in cancers. Chromosomal translocations are one of the most common genomic aberrations associated with nearly all types of cancers especially leukemia and lymphoma. Recent studies have shown the role of non-B DNA structures in generation of translocations. In the present study, using various bioinformatic tools, we show the propensity of formation of different types of altered DNA structures near translocation breakpoint regions. In particular, we find close association between occurrence of G-quadruplex forming motifs and fragile regions in almost 70% of genes involved in rearrangements in lymphoid cancers. However, such an analysis did not provide any evidence for the occurrence of G-quadruplexes at the close vicinity of translocation breakpoint regions in nonlymphoid cancers. Overall, this study will help in the identification of novel non-B DNA targets that may be responsible for generation of chromosomal translocations in cancer. (C) 2012 Elsevier Inc. All rights reserved.

Bond Graph Modeling for Energy-Harvesting Wireless Sensor Networks

Researchers can use bond graph modeling, a tool that takes into account the energy conservation principle, to accurately assess the dynamic behavior of wireless sensor networks on a continuous basis.