Maximum induced subgraph of a recursive circulant

The recursive circulant RC(2(n), 4) enjoys several attractive topological properties. Let max_epsilon(G) (m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that max_epsilon(RC(2n,4))(m) = Sigma(i)(r)=(0)(p(i)/2 + i)2(Pi), where p(0) > p(1) > ... > p(r) are nonnegative integers defined by m = Sigma(i)(r)=(0)2(Pi). We then apply this formula to find the bisection width of RC(2(n), 4). The conclusion shows that, as n-dimensional cube, RC(2(n), 4) enjoys a linear bisection width. (c) 2005 Elsevier B.V. All rights reserved.

Structural matching of 2D electrophoresis gels using deformed graphs

2D electrophoresis is a well-known method for protein separation which is extremely useful in the field of proteomics. Each spot in the image represents a protein accumulation and the goal is to perform a differential analysis between pairs of images to study changes in protein content. It is thus necessary to register two images by finding spot correspondences. Although it may seem a simple task, generally, the manual processing of this kind of images is very cumbersome, especially when strong variations between corresponding sets of spots are expected (e.g. strong non-linear deformations and outliers). In order to solve this problem, this paper proposes a new quadratic assignment formulation together with a correspondence estimation algorithm based on graph matching which takes into account the structural information between the detected spots. Each image is represented by a graph and the task is to find a maximum common subgraph. Successful experimental results using real data are presented, including an extensive comparative performance evaluation with ground-truth data. (C) 2010 Elsevier B.V. All rights reserved.

An integer linear programming approach for approximate string comparison

We introduce a problem called maximum common characters in blocks (MCCB), which arises in applications of approximate string comparison, particularly in the unification of possibly erroneous textual data coming from different sources. We show that this problem is NP-complete, but can nevertheless be solved satisfactorily using integer linear programming for instances of practical interest. Two integer linear formulations are proposed and compared in terms of their linear relaxations. We also compare the results of the approximate matching with other known measures such as the Levenshtein (edit) distance. (C) 2008 Elsevier B.V. All rights reserved.

On Optimizing Compatible Security Policies in Wireless Networks

This paper deals with finding the maximum number of security policies without conflicts. By doing so we can remove security loophole that causes security violation. We present the problem of maximum compatible security policy and its relationship to the problem of maximum acyclic subgraph, which is proved to be NP-hard. Then we present a polynomial-time approximation algorithm and show that our result has approximation ratio for any integer with complexity .

Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.

The common p450 oxidoreductase variant A503V is not a modifier gene for 21-hydroxylase deficiency

Context: 21-hydroxylase deficiency (21OHD) is a common genetic disorder caused by mutations in the CYP21A2 gene, which encodes the adrenal 21-hydroxylase, microsomal P450c21. CYP21A2 gene mutations generally correlate well with impaired P450c21 enzymatic activity and the clinical findings in 21OHD, but occasional discrepancies between genotype and phenotype suggest the effects of modifier genes. Mutations in P450 oxidoreductase (POR), the protein that transfers electrons from reduced nicotinamide adenine dinucleotide phosphate to all microsomal P450s, can ameliorate the 21OHD phenotype and, therefore, could be a modifier gene. Objectives: We sought to identify POR variants in patients with 21OHD having discordant phenotype and genotype, and to evaluate their effect on 21-hydroxylase activity. Patients and Methods: We determined the CYP21A2 genotypes of 313 Brazilian patients with 21OHD and correlated the genotype and phenotype. The POR gene was sequenced in 17 patients with discordant genotype and phenotype. Wild-type and A503V POR, and P450c21 were expressed in bacteria and reconstituted in vitro. Activities were assayed by conversion of [C-14] progesterone to deoxycorticosterone and [H-3]17-hydroxyprogesterone to 11-deoxycortisol, and assessed by thin layer chromatography and phosphorimaging. Results: The A503V POR variant was found in 10 of 30 alleles, the same ratio as in the normal population. There were no significant differences in Michaelis constant, maximum velocity and maximum velocity/Michaelis constant of 21-hydroxylase activity supported by wild-type and A503V POR. Conclusion: The only POR missense polymorphism found in atypical 21OHD patients was A503V. Although A503V reduces P450c17 enzymatic activity, it does not influence P450c21 activity, indicating that POR A503V does not modify the 21OHD phenotype.

Maximum Likelihood Estimation of Mixture Densities for Binned and Truncated Multivariate Data

Binning and truncation of data are common in data analysis and machine learning. This paper addresses the problem of fitting mixture densities to multivariate binned and truncated data. The EM approach proposed by McLachlan and Jones (Biometrics, 44: 2, 571-578, 1988) for the univariate case is generalized to multivariate measurements. The multivariate solution requires the evaluation of multidimensional integrals over each bin at each iteration of the EM procedure. Naive implementation of the procedure can lead to computationally inefficient results. To reduce the computational cost a number of straightforward numerical techniques are proposed. Results on simulated data indicate that the proposed methods can achieve significant computational gains with no loss in the accuracy of the final parameter estimates. Furthermore, experimental results suggest that with a sufficient number of bins and data points it is possible to estimate the true underlying density almost as well as if the data were not binned. The paper concludes with a brief description of an application of this approach to diagnosis of iron deficiency anemia, in the context of binned and truncated bivariate measurements of volume and hemoglobin concentration from an individual's red blood cells.

A comparative study of alternative approaches for common factors identification

Preliminary version

Using neural networks and support vector regression to relate marchetti dilatometer test parameters and maximum shear modulus

In the last two decades, small strain shear modulus became one of the most important geotechnical parameters to characterize soil stiffness. Finite element analysis have shown that in-situ stiffness of soils and rocks is much higher than what was previously thought and that stress-strain behaviour of these materials is non-linear in most cases with small strain levels, especially in the ground around retaining walls, foundations and tunnels, typically in the order of 10−2 to 10−4 of strain. Although the best approach to estimate shear modulus seems to be based in measuring seismic wave velocities, deriving the parameter through correlations with in-situ tests is usually considered very useful for design practice.The use of Neural Networks for modeling systems has been widespread, in particular within areas where the great amount of available data and the complexity of the systems keeps the problem very unfriendly to treat following traditional data analysis methodologies. In this work, the use of Neural Networks and Support Vector Regression is proposed to estimate small strain shear modulus for sedimentary soils from the basic or intermediate parameters derived from Marchetti Dilatometer Test. The results are discussed and compared with some of the most common available methodologies for this evaluation.

Using neural networks and support vector regression to relate marchetti dilatometer test parameters and maximum shear modulus

In the last two decades, small strain shear modulus became one of the most important geotechnical parameters to characterize soil stiffness. Finite element analysis have shown that in-situ stiffness of soils and rocks is much higher than what was previously thought and that stress-strain behaviour of these materials is non-linear in most cases with small strain levels, especially in the ground around retaining walls, foundations and tunnels, typically in the order of 10−2 to 10−4 of strain. Although the best approach to estimate shear modulus seems to be based in measuring seismic wave velocities, deriving the parameter through correlations with in-situ tests is usually considered very useful for design practice.The use of Neural Networks for modeling systems has been widespread, in particular within areas where the great amount of available data and the complexity of the systems keeps the problem very unfriendly to treat following traditional data analysis methodologies. In this work, the use of Neural Networks and Support Vector Regression is proposed to estimate small strain shear modulus for sedimentary soils from the basic or intermediate parameters derived from Marchetti Dilatometer Test. The results are discussed and compared with some of the most common available methodologies for this evaluation.

Effect of day time on foliar spraying of several levels of nitrogen fertilizer, NPKS solutions and its components, on common bean leaves

An experiment was carried out in order to determine the effect of day time of foliar spraying of several levels of nitrogen fertilizers, N-P-K-S station, and its components on common bean leaves. Results, based on the visual observations, indicated the maximum levels of each fertilizer that did not cause injuries and showed that the foliar spraying early in the morning is the best day time.

Histopathological examination of nerve samples from pure neural leprosy patients: obtaining maximum information to improve diagnostic efficiency

Nerve biopsy examination is an important auxiliary procedure for diagnosing pure neural leprosy (PNL). When acid-fast bacilli (AFB) are not detected in the nerve sample, the value of other nonspecific histological alterations should be considered along with pertinent clinical, electroneuromyographical and laboratory data (the detection of Mycobacterium leprae DNA with polymerase chain reaction and the detection of serum anti-phenolic glycolipid 1 antibodies) to support a possible or probable PNL diagnosis. Three hundred forty nerve samples [144 from PNL patients and 196 from patients with non-leprosy peripheral neuropathies (NLN)] were examined. Both AFB-negative and AFB-positive PNL samples had more frequent histopathological alterations (epithelioid granulomas, mononuclear infiltrates, fibrosis, perineurial and subperineurial oedema and decreased numbers of myelinated fibres) than the NLN group. Multivariate analysis revealed that independently, mononuclear infiltrate and perineurial fibrosis were more common in the PNL group and were able to correctly classify AFB-negative PNL samples. These results indicate that even in the absence of AFB, these histopathological nerve alterations may justify a PNL diagnosis when observed in conjunction with pertinent clinical, epidemiological and laboratory data.

Time consistent Pareto solutions in common access resource gameswith asymmetric players

In the analysis of equilibrium policies in a di erential game, if agents have different time preference rates, the cooperative (Pareto optimum) solution obtained by applying the Pontryagin's Maximum Principle becomes time inconsistent. In this work we derive a set of dynamic programming equations (in discrete and continuous time) whose solutions are time consistent equilibrium rules for N-player cooperative di erential games in which agents di er in their instantaneous utility functions and also in their discount rates of time preference. The results are applied to the study of a cake-eating problem describing the management of a common property exhaustible natural resource. The extension of the results to a simple common property renewable natural resource model in in nite horizon is also discussed.