An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

Minimal unsatisfiable sets: Classification and bounds

Proving the unsatisfiability of propositional Boolean formulas has applications in a wide range of fields. Minimal Unsatisfiable Sets (MUS) are signatures of the property of unsatisfiability in formulas and our understanding of these signatures can be very helpful in answering various algorithmic and structural questions relating to unsatisfiability. In this paper, we explore some combinatorial properties of MUS and use them to devise a classification scheme for MUS. We also derive bounds on the sizes of MUS in Horn, 2-SAT and 3-SAT formulas.

Intelligent Approach for Fault Diagnosis in Power Transmission Systems Using Support Vector Machines

This paper presents an approach for identifying the faulted line section and fault location on transmission systems using support vector machines (SVMs) for diagnosis/post-fault analysis purpose. Power system disturbances are often caused by faults on transmission lines. When fault occurs on a transmission system, the protective relay detects the fault and initiates the tripping operation, which isolates the affected part from the rest of the power system. Based on the fault section identified, rapid and corrective restoration procedures can thus be taken to minimize the power interruption and limit the impact of outage on the system. The approach is particularly important for post-fault diagnosis of any mal-operation of relays following a disturbance in the neighboring line connected to the same substation. This may help in improving the fault monitoring/diagnosis process, thus assuring secure operation of the power systems. In this paper we compare SVMs with radial basis function neural networks (RBFNN) in data sets corresponding to different faults on a transmission system. Classification and regression accuracy is reported for both strategies. Studies on a practical 24-Bus equivalent EHV transmission system of the Indian Southern region is presented for indicating the improved generalization with the large margin classifiers in enhancing the efficacy of the chosen model.

Isomeric identification of methylated naphthalenes using gas phase infrared spectroscopy

We report gas phase mid-infrared spectra of 1- and 2- methyl naphthalenes at 0.2 cm(-1) resolution. Assignment of observed bands have been made using scaled quantum mechanical (SQM) calculations where the force fields rather the frequencies are scaled to find a close fit between observed and calculated bands. The structure of the molecules has been optimized using B3LYP level of theory in conjunction with standard 6-311G** basis set to obtain the harmonic frequencies. Using the force constants in Cartesian coordinates from the Gaussian output, scaled force field calculations are carried out using a modified version of the UMAT program in the QCPE package. Potential energy distributions of the normal modes obtained from such calculations helped us assign the observed bands and identify the unique features of the spectra of 1- and 2-MNs which are important for their isomeric identification.

Network properties of protein-decoy structures

Convergence of the vast sequence space of proteins into a highly restricted fold/conformational space suggests a simple yet unique underlying mechanism of protein folding that has been the subject of much debate in the last several decades. One of the major challenges related to the understanding of protein folding or in silico protein structure prediction is the discrimination of non-native structures/decoys from the native structure. Applications of knowledge-based potentials to attain this goal have been extensively reported in the literature. Also, scoring functions based on accessible surface area and amino acid neighbourhood considerations were used in discriminating the decoys from native structures. In this article, we have explored the potential of protein structure network (PSN) parameters to validate the native proteins against a large number of decoy structures generated by diverse methods. We are guided by two principles: (a) the PSNs capture the local properties from a global perspective and (b) inclusion of non-covalent interactions, at all-atom level, including the side-chain atoms, in the network construction accommodates the sequence dependent features. Several network parameters such as the size of the largest cluster, community size, clustering coefficient are evaluated and scored on the basis of the rank of the native structures and the Z-scores. The network analysis of decoy structures highlights the importance of the global properties contributing to the uniqueness of native structures. The analysis also exhibits that the network parameters can be used as metrics to identify the native structures and filter out non-native structures/decoys in a large number of data-sets; thus also has a potential to be used in the protein `structure prediction' problem.

On maximum entropy and minimum KL-divergence optimization by Grobner basis methods

In this paper we study constrained maximum entropy and minimum divergence optimization problems, in the cases where integer valued sufficient statistics exists, using tools from computational commutative algebra. We show that the estimation of parametric statistical models in this case can be transformed to solving a system of polynomial equations. We give an implicit description of maximum entropy models by embedding them in algebraic varieties for which we give a Grobner basis method to compute it. In the cases of minimum KL-divergence models we show that implicitization preserves specialization of prior distribution. This result leads us to a Grobner basis method to embed minimum KL-divergence models in algebraic varieties. (C) 2012 Elsevier Inc. All rights reserved.

Badly approximable numbers and vectors in Cantor-like sets

We show that a large class of Cantor-like sets of R-d, d >= 1, contains uncountably many badly approximable numbers, respectively badly approximable vectors, when d >= 2. An analogous result is also proved for subsets of R-d arising in the study of geodesic flows corresponding to (d+1)-dimensional manifolds of constant negative curvature and finite volume, generalizing the set of badly approximable numbers in R. Furthermore, we describe a condition on sets, which is fulfilled by a large class, ensuring a large intersection with these Cantor-like sets.

Rainbow connection number and connected dominating sets

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree delta, the rainbow connection number is upper bounded by 3n/(delta + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432437), improving the previously best known bound of 20n/delta (J Graph Theory 63 (2010), 185191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(delta + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree d. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by Gc(G) + 2, where Gc(G) is the connected domination number of G. Bounds of the form diameter(G)?rc(G)?diameter(G) + c, 1?c?4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree delta at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)?3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds.

Analysis of the temperature-dependent current-voltage characteristics and the barrier-height inhomogeneities of Au/GaN Schottky diodes

In this report, the currentvoltage (IV) characteristics of Au/GaN Schottky diodes have been carried out in the temperature range of 300510?K. The estimated values of the Schottky-barrier height (SBH) and the ideality factor of the diodes based on the thermionic emission (TE) mechanism were found to be temperature dependent. The barrier height was found to increase and the ideality factor to decrease with increasing temperature. The conventional Richardson plot of ln(Is/T2) versus 1/kT gives the SBH of 0.51?eV and Richardson constant value of 3.23?X?10-5?A?cm-2?K-2 which is much lower than the known value of 26.4?A?cm-2?K-2 for GaN. Such discrepancies of the SBH and Richardson constant value were attributed to the existence of barrier-height inhomogeneities at the Au/GaN interface. The modified Richardson plot of ln(Is/T2)q2 sigma 2/2k2T2 versus q/kT, by assuming a Gaussian distribution of barrier heights at the Au/GaN interface, provided the SBH of 1.47?eV and Richardson constant value of 38.8?A?cm-2?K-2. The temperature dependence of the barrier height is interpreted on the basis of existence of the Gaussian distribution of the barrier heights due to the barrier-height inhomogeneities at the Au/GaN interface.

Two-User Gaussian Interference Channel with Finite Constellation Input and FDMA

In the two-user Gaussian Strong Interference Channel (GSIC) with finite constellation inputs, it is known that relative rotation between the constellations of the two users enlarges the Constellation Constrained (CC) capacity region. In this paper, a metric for finding the approximate angle of rotation to maximally enlarge the CC capacity is presented. It is shown that for some portion of the Strong Interference (SI) regime, with Gaussian input alphabets, the FDMA rate curve touches the capacity curve of the GSIC. Even as the Gaussian alphabet FDMA rate curve touches the capacity curve of the GSIC, at high powers, with both the users using the same finite constellation, we show that the CC FDMA rate curve lies strictly inside the CC capacity curve for the constellations BPSK, QPSK, 8-PSK, 16-QAM and 64-QAM. It is known that, with Gaussian input alphabets, the FDMA inner-bound at the optimum sum-rate point is always better than the simultaneous-decoding inner-bound throughout the Weak Interference (WI) regime. For a portion of the WI regime, it is shown that, with identical finite constellation inputs for both the users, the simultaneous-decoding inner-bound enlarged by relative rotation between the constellations can be strictly better than the FDMA inner-bound.

Nonlinear dynamic state estimation in instrumented structures with conditionally linear Gaussian substructures

Many problems of state estimation in structural dynamics permit a partitioning of system states into nonlinear and conditionally linear substructures. This enables a part of the problem to be solved exactly, using the Kalman filter, and the remainder using Monte Carlo simulations. The present study develops an algorithm that combines sequential importance sampling based particle filtering with Kalman filtering to a fairly general form of process equations and demonstrates the application of a substructuring scheme to problems of hidden state estimation in structures with local nonlinearities, response sensitivity model updating in nonlinear systems, and characterization of residual displacements in instrumented inelastic structures. The paper also theoretically demonstrates that the sampling variance associated with the substructuring scheme used does not exceed the sampling variance corresponding to the Monte Carlo filtering without substructuring. (C) 2012 Elsevier Ltd. All rights reserved.

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

Sequence and structural basis for chromosomal fragility during translocations in cancer

Chromosomal aberration is considered to be one of the major characteristic features in many cancers. Chromosomal translocation, one type of genomic abnormality, can lead to deregulation of critical genes involved in regulating important physiological functions such as cell proliferation and DNA repair. Although chromosomal translocations were thought to be random events, recent findings suggest that certain regions in the human genome are more susceptible to breakage than others. The possibility of deviation from the usual B-DNA conformation in such fragile regions has been an active area of investigation. This review summarizes the factors that contribute towards the fragility of these regions in the chromosomes, such as DNA sequences and the role of different forms of DNA structures. Proteins responsible for chromosomal fragility, and their mechanism of action are also discussed. The effect of positioning of chromosomes within the nucleus favoring chromosomal translocations and the role of repair mechanisms are also addressed.

A numerical approach to determine the sufficiency of given boundary data sets for uniquely estimating interior elastic properties

We consider an inverse elasticity problem in which forces and displacements are known on the boundary and the material property distribution inside the body is to be found. In other words, we need to estimate the distribution of constitutive properties using the finite boundary data sets. Uniqueness of the solution to this problem is proved in the literature only under certain assumptions for a given complete Dirichlet-to-Neumann map. Another complication in the numerical solution of this problem is that the number of boundary data sets needed to establish uniqueness is not known even under the restricted cases where uniqueness is proved theoretically. In this paper, we present a numerical technique that can assess the sufficiency of given boundary data sets by computing the rank of a sensitivity matrix that arises in the Gauss-Newton method used to solve the problem. Numerical experiments are presented to illustrate the method.

Structural and molecular basis of interaction of HCV non-structural protein 5A with human casein kinase 1 alpha and PKR

Background: Interaction of non-structural protein 5A (NS5A) of Hepatitis C virus (HCV) with human kinases namely, casein kinase 1 alpha (ck1 alpha) and protein kinase R (PKR) have different functional implications such as regulation of viral replication and evasion of interferon induced immune response respectively. Understanding the structural and molecular basis of interactions of the viral protein with two different human kinases can be useful in developing strategies for treatment against HCV. Results: Serine 232 of NS5A is known to be phosphorylated by human ck1 alpha. A structural model of NS5A peptide containing phosphoacceptor residue Serine 232 bound to ck1 alpha has been generated using the known 3-D structures of kinase-peptide complexes. The substrate interacting residues in ck1 alpha has been identified from the model and these are found to be conserved well in the ck1 family. ck1 alpha - substrate peptide complex has also been used to understand the structural basis of association between ck1 alpha and its other viral stress induced substrate, tumour suppressor p53 transactivation domain which has a crystal structure available. Interaction of NS5A with another human kinase PKR is primarily genotype specific. NS5A from genotype 1b has been shown to interact and inhibit PKR whereas NS5A from genotype 2a/3a are unable to bind and inhibit PKR efficiently. This is one of the main reasons for the varied response to interferon therapy in HCV patients across different genotypes. Using PKR crystal structure, sequence alignment and evolutionary trace analysis some of the critical residues responsible for the interaction of NS5A 1b with PKR have been identified. Conclusions: The substrate interacting residues in ck1 alpha have been identified using the structural model of kinase substrate peptide. The PKR interacting NS5A 1b residues have also been predicted using PKR crystal structure, NS5A sequence analysis along with known experimental results. Functional significance and nature of interaction of interferon sensitivity determining region and variable region 3 of NS5A in different genotypes with PKR which was experimentally shown are also supported by the findings of evolutionary trace analysis. Designing inhibitors to prevent this interaction could enable the HCV genotype 1 infected patients respond well to interferon therapy.