An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

DNA Clasping by Mycobacterial HU: The C-Terminal Region of HupB Mediates Increased Specificity of DNA Binding

Background: HU a small, basic, histone like protein is a major component of the bacterial nucleoid. E. coli has two subunits of HU coded by hupA and hupB genes whereas Mycobacterium tuberculosis (Mtb) has only one subunit of HU coded by ORF Rv2986c (hupB gene). One noticeable feature regarding Mtb HupB, based on sequence alignment of HU orthologs from different bacteria, was that HupB(Mtb) bears at its C-terminal end, a highly basic extension and this prompted an examination of its role in Mtb HupB function. Methodology/Principal Findings: With this objective two clones of Mtb HupB were generated; one expressing full length HupB protein (HupB(Mtb)) and another which expresses only the N terminal region (first 95 amino acid) of hupB (HupB(MtbN)). Gel retardation assays revealed that HupBMtbN is almost like E. coli HU (heat stable nucleoid protein) in terms of its DNA binding, with a binding constant (K-d) for linear dsDNA greater than 1000 nM, a value comparable to that obtained for the HU alpha alpha and HU alpha beta forms. However CTR (C-terminal Region) of HupB(Mtb) imparts greater specificity in DNA binding. HupB(Mtb) protein binds more strongly to supercoiled plasmid DNA than to linear DNA, also this binding is very stable as it provides DNase I protection even up to 5 minutes. Similar results were obtained when the abilities of both proteins to mediate protection against DNA strand cleavage by hydroxyl radicals generated by the Fenton's reaction, were compared. It was also observed that both the proteins have DNA binding preference for A: T rich DNA which may occur at the regulatory regions of ORFs and the oriC region of Mtb. Conclusions/Significance: These data thus point that HupB(Mtb) may participate in chromosome organization in-vivo, it may also play a passive, possibly an architectural role.

An O(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn).All the algorithms currently known for constructing a Gomory-Hu tree [8,9] use n-1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest Õ(n20/9) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n20/9n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs.We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

Targeting Mycobacterium tuberculosis nucleoid-associated protein HU with structure-based inhibitors

The nucleoid-associated protein HU plays an important role in maintenance of chromosomal architecture and in global regulation of DNA transactions in bacteria. Although HU is essential for growth in Mycobacterium tuberculosis (Mtb), there have been no reported attempts to perturb HU function with small molecules. Here we report the crystal structure of the N-terminal domain of HU from Mtb. We identify a core region within the HU-DNA interface that can be targeted using stilbene derivatives. These small molecules specifically inhibit HU-DNA binding, disrupt nucleoid architecture and reduce Mtb growth. The stilbene inhibitors induce gene expression changes in Mtb that resemble those induced by HU deficiency. Our results indicate that HU is a potential target for the development of therapies against tuberculosis.

Size-dependent elasticity of nanocrystalline titania

Synchrotron-based high-pressure x-ray diffraction measurements indicate that compressibility, a fundamental materials property, can have a size-specific minimum value. The bulk modulus of nanocrystalline titania has a maximum at particle size of 15 nm. This can be explained by dislocation behavior because very high dislocation contents can be achieved when shear stress induced within nanoparticles counters the repulsion between dislocations. As particle size decreases, compression increasingly generates dislocation networks hardened by overlap of strain fields that shield intervening regions from external pressure. However, when particles become too small to sustain high dislocation concentrations, elastic stiffening declines. The compressibility has a minimum at intermediate sizes.

Effectiveness factor for zeroth-order catalytic reactions with volume change and nonuniform catalyst activity profiles

Analytical solutions are presented for the effectiveness factor of a zeroth-order reaction with volume change and nonuniform catalyst activity profile in slab, cylinder and spherical pellets. The possibility of shape normalization is considered for a variety of activity profiles and pellet shapes. When the catalyst activity at the external surface of the pellet is non-zero, shape normalization is obtained, which makes the asymptotic behavior of the effectiveness factor identical for small and large values of Thiele modulus, however, the normalization can lead to significant errors, particularly for the case of activity profiles decreasing towards the outer surface of the catalyst.

Homologous pairing between nucleosome cores on a linear duplex DNA and nucleoprotein filaments of RecA protein-single stranded DNA

The ability of E coli recA protein to promote homologous pairing with linear duplex DNA bound to HU protein (Nucleosome cores) was found to be differentially affected. The formation of paranemic joint molecules was not affected whereas the formation of plectomic joint molecules was inhibited from the start of the reaction. The formation of paranemic joint molecules between nucleoprotein filaments of recA protein-circular single stranded DNA and closed circular duplex DNA is believed to generate positive supercoiling in the duplex DNA. We found that the positively superhelical duplex DNA was inert in the formation of joint molecules but could be converted into an active substrate, in situ, by the action of wheat germ topoisomerase I. These observations initiate an understanding of the structural features of E coli chromosome such as DNA supercoiling and nucleosome-like structures in homologous recombination.

Isoperimetric Problem and Meta-fibonacci Sequences

Let G = (V,E) be a simple, finite, undirected graph. For S ⊆ V, let $\delta(S,G) = \{ (u,v) \in E : u \in S \mbox { and } v \in V-S \}$ and $\phi(S,G) = \{ v \in V -S: \exists u \in S$ , such that (u,v) ∈ E} be the edge and vertex boundary of S, respectively. Given an integer i, 1 ≤ i ≤ ∣ V ∣, the edge and vertex isoperimetric value at i is defined as b e (i,G) =  min S ⊆ V; |S| = i |δ(S,G)| and b v (i,G) =  min S ⊆ V; |S| = i |φ(S,G)|, respectively. The edge (vertex) isoperimetric problem is to determine the value of b e (i, G) (b v (i, G)) for each i, 1 ≤ i ≤ |V|. If we have the further restriction that the set S should induce a connected subgraph of G, then the corresponding variation of the isoperimetric problem is known as the connected isoperimetric problem. The connected edge (vertex) isoperimetric values are defined in a corresponding way. It turns out that the connected edge isoperimetric and the connected vertex isoperimetric values are equal at each i, 1 ≤ i ≤ |V|, if G is a tree. Therefore we use the notation b c (i, T) to denote the connected edge (vertex) isoperimetric value of T at i. Hofstadter had introduced the interesting concept of meta-fibonacci sequences in his famous book “Gödel, Escher, Bach. An Eternal Golden Braid”. The sequence he introduced is known as the Hofstadter sequences and most of the problems he raised regarding this sequence is still open. Since then mathematicians studied many other closely related meta-fibonacci sequences such as Tanny sequences, Conway sequences, Conolly sequences etc. Let T 2 be an infinite complete binary tree. In this paper we related the connected isoperimetric problem on T 2 with the Tanny sequences which is defined by the recurrence relation a(i) = a(i − 1 − a(i − 1)) + a(i − 2 − a(i − 2)), a(0) = a(1) = a(2) = 1. In particular, we show that b c (i, T 2) = i + 2 − 2a(i), for each i ≥ 1. We also propose efficient polynomial time algorithms to find vertex isoperimetric values at i of bounded pathwidth and bounded treewidth graphs.

Design of plane sand-bed channels affected by seepage

The importance of seepage in the design of channels is discussed. Experimental investigations reveal that seepage, either in the downward direction (suction) or in the upward direction (injection), can significantly change the resistance as well as the mobility of the sand-bed particles. A resistance equation relating 'particle Reynolds number' and 'shear Reynolds number' under seepage conditions is developed for plane sediment beds. Finally, a detailed design procedure of the plane sediment beds affected by seepage is presented.

On a Special Co-cycle Basis of Graphs

In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.

The partition of unity finite element method for elastic wave propagation in Reissner-Mindlin plates

This paper reports a numerical method for modelling the elastic wave propagation in plates. The method is based on the partition of unity approach, in which the approximate spectral properties of the infinite dimensional system are embedded within the space of a conventional finite element method through a consistent technique of waveform enrichment. The technique is general, such that it can be applied to the Lagrangian family of finite elements with specific waveform enrichment schemes, depending on the dominant modes of wave propagation in the physical system. A four-noded element for the Reissner-indlin plate is derived in this paper, which is free of shear locking. Such a locking-free property is achieved by removing the transverse displacement degrees of freedom from the element nodal variables and by recovering the same through a line integral and a weak constraint in the frequency domain. As a result, the frequency-dependent stiffness matrix and the mass matrix are obtained, which capture the higher frequency response with even coarse meshes, accurately. The steps involved in the numerical implementation of such element are discussed in details. Numerical studies on the performance of the proposed element are reported by considering a number of cases, which show very good accuracy and low computational cost. Copyright (C)006 John Wiley & Sons, Ltd.

Self-interrupted regenerative turning

A preliminary study of self-interrupted regenerative turning is performed in this paper. To facilitate the analysis, a new approach is proposed to model the regenerative effect in metal cutting. This model automatically incorporates the multiple-regenerative effects accompanying self-interrupted cutting. Some lower dimensional ODE approximations are obtained for this model using Galerkin projections. Using these ODE approximations, a bifurcation diagram of the regenerative turning process is obtained. It is found that the unstable branch resulting from the subcritical Hopf bifurcation meets the stable branch resulting from the self-interrupted dynamics in a turning point bifurcation. Using a rough analytical estimate of the turning point tool displacement, we can identify regions in the cutting parameter space where loss of stability leads to much greater amplitude self-interrupted motions than in some other regions.