REPRESENTING A CUBIC GRAPH AS THE INTERSECTION GRAPH OF AXIS-PARALLEL BOXES IN THREE DIMENSIONS

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes touch just at their boundaries.

BELIEF PROPAGATION FOR OPTIMAL EDGE COVER IN THE RANDOM COMPLETE GRAPH

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the (2) limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

Fixed-orientation equilateral triangle matching of point sets

Given a point set P and a class C of geometric objects, G(C)(P) is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C is an element of C containing both p and q but no other points from P. We study G(del)(P) graphs where del is the class of downward equilateral triangles (i.e., equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Theta(6) graphs and TD-Delaunay graphs. The main result in our paper is that for point sets P in general position, G(del)(P) always contains a matching of size at least vertical bar P vertical bar-1/3] and this bound is tight. We also give some structural properties of G(star)(P) graphs, where is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of G(star)(P) is simply a path. Through the equivalence of G(star)(P) graphs with Theta(6) graphs, we also derive that any Theta(6) graph can have at most 5n-11 edges, for point sets in general position. (C) 2013 Elsevier B.V. All rights reserved.

Ligand 5,10,15,20-Tetra(N-methyl-4-pyridyl)porphine (TMPyP4) Prefers the Parallel Propeller-Type Human Telomeric G-Quadruplex DNA over Its Other Polymorphs

The binding of ligand 5,10,15,20-tetra(N-methyl-4-pyridyl)porphine (TMPyP4) with telomeric and genomic G-quadruplex DNA has been extensively studied. However, a comparative study of interactions of TMPyP4 with different conformations of human telomeric G-quadruplex DNA, namely, parallel propeller-type (PP), antiparallel basket-type (AB), and mixed hybrid-type (MH) G-quadruplex DNA, has not been done. We considered all the possible binding sites in each of the G-quadruplex DNA structures and docked TMPyP4 to each one of them. The resultant most potent sites for binding were analyzed from the mean binding free energy of the complexes. Molecular dynamics simulations were then carried out, and analysis of the binding free energy of the TMPyP4-G-quadruplex complex showed that the binding of TMPyP4 with parallel propeller-type G-quadruplex DNA is preferred over the other two G-quadruplex DNA conformations. The results obtained from the change in solvent excluded surface area (SESA) and solvent accessible surface area (SASA) also support the more pronounced binding of the ligand with the parallel propeller-type G-quadruplex DNA.

Genome-wide methylation profiling identifies an essential role of reactive oxygen species in pediatric glioblastoma multiforme and validates a methylome specific for H3 histone family 3A with absence of G-CIMP/isocitrate dehydrogenase 1 mutation

Background. Pediatric glioblastoma multiforme (GBM) is rare, and there is a single study, a seminal discovery showing association of histone H3.3 and isocitrate dehydrogenase (IDH) 1 mutation with a DNA methylation signature. The present study aims to validate these findings in an independent cohort of pediatric GBM, compare it with adult GBM, and evaluate the involvement of important functionally altered pathways. Methods. Genome-wide methylation profiling of 21 pediatric GBM cases was done and compared with adult GBM data (GSE22867). We performed gene mutation analysis of IDH1 and H3 histone family 3A (H3F3A), status evaluation of glioma cytosine-phosphate-guanine island methylator phenotype (G-CIMP), and Gene Ontology analysis. Experimental evaluation of reactive oxygen species (ROS) association was also done. Results. Distinct differences were noted between methylomes of pediatric and adult GBM. Pediatric GBM was characterized by 94 hypermethylated and 1206 hypomethylated cytosine-phosphate-guanine (CpG) islands, with 3 distinct clusters, having a trend to prognostic correlation. Interestingly, none of the pediatric GBM cases showed G-CIMP/IDH1 mutation. Gene Ontology analysis identified ROS association in pediatric GBM, which was experimentally validated. H3F3A mutants (36.4%; all K27M) harbored distinct methylomes and showed enrichment of processes related to neuronal development, differentiation, and cell-fate commitment. Conclusions. Our study confirms that pediatric GBM has a distinct methylome compared with that of adults. Presence of distinct clusters and an H3F3A mutation-specific methylome indicate existence of epigenetic subgroups within pediatric GBM. Absence of IDH1/G-CIMP status further indicates that findings in adult GBM cannot be simply extrapolated to pediatric GBM and that there is a strong need for identification of separate prognostic markers. A possible role of ROS in pediatric GBM pathogenesis is demonstrated for the first time and needs further evaluation.

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.

Detection of G-Quadruplex DNA Using Primer Extension as a Tool

DNA sequence and structure play a key role in imparting fragility to different regions of the genome. Recent studies have shown that non-B DNA structures play a key role in causing genomic instability, apart from their physiological roles at telomeres and promoters. Structures such as G-quadruplexes, cruciforms, and triplexes have been implicated in making DNA susceptible to breakage, resulting in genomic rearrangements. Hence, techniques that aid in the easy identification of such non-B DNA motifs will prove to be very useful in determining factors responsible for genomic instability. In this study, we provide evidence for the use of primer extension as a sensitive and specific tool to detect such altered DNA structures. We have used the G-quadruplex motif, recently characterized at the BCL2 major breakpoint region as a proof of principle to demonstrate the advantages of the technique. Our results show that pause sites corresponding to the non-B DNA are specific, since they are absent when the G-quadruplex motif is mutated and their positions change in tandem with that of the primers. The efficiency of primer extension pause sites varied according to the concentration of monovalant cations tested, which support G-quadruplex formation. Overall, our results demonstrate that primer extension is a strong in vitro tool to detect non-B DNA structures such as G-quadruplex on a plasmid DNA, which can be further adapted to identify non-B DNA structures, even at the genomic level.

PERCOLATION ON THE INFORMATION-THEORETICALLY SECURE SIGNAL TO INTERFERENCE RATIO GRAPH

We consider a continuum percolation model consisting of two types of nodes, namely legitimate and eavesdropper nodes, distributed according to independent Poisson point processes in R-2 of intensities lambda and lambda(E), respectively. A directed edge from one legitimate node A to another legitimate node B exists provided that the strength of the signal transmitted from node A that is received at node B is higher than that received at any eavesdropper node. The strength of the signal received at a node from a legitimate node depends not only on the distance between these nodes, but also on the location of the other legitimate nodes and an interference suppression parameter gamma. The graph is said to percolate when there exists an infinitely connected component. We show that for any finite intensity lambda(E) of eavesdropper nodes, there exists a critical intensity lambda(c) < infinity such that for all lambda > lambda(c) the graph percolates for sufficiently small values of the interference parameter. Furthermore, for the subcritical regime, we show that there exists a lambda(0) such that for all lambda < lambda(0) <= lambda(c) a suitable graph defined over eavesdropper node connections percolates that precludes percolation in the graphs formed by the legitimate nodes.

New dimeric carbazole-benzimidazole mixed ligands for the stabilization of human telomeric G-quadruplex DNA and as telomerase inhibitors. A remarkable influence of the spacer

for selectively targeting cancer cells. Herein, we report the design and evolution of a new kind of carbazole-based benzimidazole dimers for their efficient telomerase inhibition activity. Spectroscopic titrations reveal the ligands high affinity toward the G4 DNA with significantly higher selectivity over duplex-DNA. The electrophoretic mobility shift assay shows that the ligands efficiently promote the formation of 04 DNA even at a lower concentration of the stabilizing K+ ions. The TRAP-LIG assay demonstrates the ligand's potential telomerase inhibition activity and also establishes that the activity proceeds via G4 DNA stabilization. An efficient nuclear internalization of the ligands in several common cancer cells (HeLa, HT1080, and A549) also enabled differentiation between normal HFF cells in co-cultures of cancer and normal ones. The ligands induce significant apoptotic response and antiproliferative activity toward cancer cells selectively when compared to the normal cells.

High T-g fluoranthene-based electron transport materials for organic light-emitting diodes

In this study, fluoranthene-based derivatives with a high thermal stability were synthesized for applications in organic electroluminescent devices. The two derivatives synthesized in this study, bis(4-(7,9,10-triphenylfluoranthen-8-yl)phenyl)sulfane (TPFDPS) and 2,8-bis(7,9,10-triphenylfluoranthen-8-yl)dibenzob,d]thiophene (TPFDBT), were characterized by cyclic voltammetry, differential scanning calorimetry (DSC) and thermogravimetric analysis (TGA). TPFDPS exhibits a high T-g of 210 degrees C while TPFDBT is crystalline in nature. Both the derivatives are thermally stable up to 500 degrees C. The charge transport studies reveal predominant electron transport properties. Subsequently, we fabricated blue OLEDs with 2-tert-butyl-9,10-bis-(beta-naphthyl)-anthracene (TBADN) as the emitting layer to demonstrate the applications of these molecules as an electron transporting layer.

Divide and Conquer: Efficient Large-Scale Structure from Motion Using Graph Partitioning

Despite significant advances in recent years, structure-from-motion (SfM) pipelines suffer from two important drawbacks. Apart from requiring significant computational power to solve the large-scale computations involved, such pipelines sometimes fail to correctly reconstruct when the accumulated error in incremental reconstruction is large or when the number of 3D to 2D correspondences are insufficient. In this paper we present a novel approach to mitigate the above-mentioned drawbacks. Using an image match graph based on matching features we partition the image data set into smaller sets or components which are reconstructed independently. Following such reconstructions we utilise the available epipolar relationships that connect images across components to correctly align the individual reconstructions in a global frame of reference. This results in both a significant speed up of at least one order of magnitude and also mitigates the problems of reconstruction failures with a marginal loss in accuracy. The effectiveness of our approach is demonstrated on some large-scale real world data sets.

Graph Modification Problems: A Modern Perspective

We give an overview of recent results and techniques in parameterized algorithms for graph modification problems.

Query Click and Text Similarity Graph for Query Suggestions

Query suggestion is an important feature of the search engine with the explosive and diverse growth of web contents. Different kind of suggestions like query, image, movies, music and book etc. are used every day. Various types of data sources are used for the suggestions. If we model the data into various kinds of graphs then we can build a general method for any suggestions. In this paper, we have proposed a general method for query suggestion by combining two graphs: (1) query click graph which captures the relationship between queries frequently clicked on common URLs and (2) query text similarity graph which finds the similarity between two queries using Jaccard similarity. The proposed method provides literally as well as semantically relevant queries for users' need. Simulation results show that the proposed algorithm outperforms heat diffusion method by providing more number of relevant queries. It can be used for recommendation tasks like query, image, and product suggestion.

Kinematics and dynamics of Jansen leg mechanism: A bond graph approach

The Jansen mechanism is a one degree-of-freedom, planar, 12-link, leg mechanism that can be used in mobile robotic applications and in gait analysis. This paper presents the kinematics and dynamics of the Jansen leg mechanism. The forward kinematics, accomplished using circle intersection method, determines the trajectories of various points on the mechanism in the chassis (stationary link) reference frame. From the foot point trajectory, the step length is shown to vary linearly while step height varies non-linearly with change in crank radius. A dynamic model for the Jansen leg mechanism is proposed using bond graph approach with modulated multiport transformers. For given ground reaction force pattern and crank angular speed, this model helps determine the motor torque profile as well as the link and joint stresses. The model can therefore be used to rate the actuator torque and in design of the hardware and controller for such a system. The kinematics of the mechanism can also be obtained from this dynamic model. The proposed model is thus a useful tool for analysis and design of systems based on the Jansen leg mechanism. (C) 2015 Elsevier B.V. All rights reserved.

Falcon: A Graph Manipulation Language for Heterogeneous Systems

Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy-even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.