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.

Deformed Gaussian-orthogonal-ensemble description of small-world networks

The study of spectral behavior of networks has gained enthusiasm over the last few years. In particular, random matrix theory (RMT) concepts have proven to be useful. In discussing transition from regular behavior to fully chaotic behavior it has been found that an extrapolation formula of the Brody type can be used. In the present paper we analyze the regular to chaotic behavior of small world (SW) networks using an extension of the Gaussian orthogonal ensemble. This RMT ensemble, coined the deformed Gaussian orthogonal ensemble (DGOE), supplies a natural foundation of the Brody formula. SW networks follow GOE statistics until a certain range of eigenvalue correlations depending upon the strength of random connections. We show that for these regimes of SW networks where spectral correlations do not follow GOE beyond a certain range, DGOE statistics models the correlations very well. The analysis performed in this paper proves the utility of the DGOE in network physics, as much as it has been useful in other physical systems.

Numerical evidence against a conjecture on the cover time of planar graphs

We investigate a conjecture on the cover times of planar graphs by means of large Monte Carlo simulations. The conjecture states that the cover time tau (G(N)) of a planar graph G(N) of N vertices and maximal degree d is lower bounded by tau (G(N)) >= C(d)N(lnN)(2) with C(d) = (d/4 pi) tan(pi/d), with equality holding for some geometries. We tested this conjecture on the regular honeycomb (d = 3), regular square (d = 4), regular elongated triangular (d = 5), and regular triangular (d = 6) lattices, as well as on the nonregular Union Jack lattice (d(min) = 4, d(max) = 8). Indeed, the Monte Carlo data suggest that the rigorous lower bound may hold as an equality for most of these lattices, with an interesting issue in the case of the Union Jack lattice. The data for the honeycomb lattice, however, violate the bound with the conjectured constant. The empirical probability distribution function of the cover time for the square lattice is also briefly presented, since very little is known about cover time probability distribution functions in general.

On the k-restricted structure ratio in planar and outerplanar graphs

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

On the resilience of long cycles in random graphs

In this paper we determine the local and global resilience of random graphs G(n,p) (p >> n(-1)) with respect to the property of containing a cycle of length at least (1 - alpha)n. Roughly speaking, given alpha > 0, we determine the smallest r(g) (G, alpha) with the property that almost surely every subgraph of G = G(n,p) having more than r(g) (G, alpha)vertical bar E(G)vertical bar edges contains a cycle of length at least (1 - alpha)n (global resilience). We also obtain, for alpha < 1/2, the smallest r(l) (G, alpha) such that any H subset of G having deg(H) (v) larger than r(l) (G, alpha) deg(G) (v) for all v is an element of V(G) contains a cycle of length at least (1 - alpha)n (local resilience). The results above are in fact proved in the more general setting of pseudorandom graphs.

Gibbs random graphs on point processes

Consider a discrete locally finite subset Gamma of R(d) and the cornplete graph (Gamma, E), with vertices Gamma and edges E. We consider Gibbs measures on the set of sub-graphs with vertices Gamma and edges E` subset of E. The Gibbs interaction acts between open edges having a vertex in common. We study percolation properties of the Gibbs distribution of the graph ensemble. The main results concern percolation properties of the open edges in two cases: (a) when Gamma is sampled from a homogeneous Poisson process; and (b) for a fixed Gamma with sufficiently sparse points. (c) 2010 American Institute of Physics. [doi:10.1063/1.3514605]

EBSD characterization of an ECAP deformed Nb single crystal

A niobium single crystal was subjected to equal channel angular pressing (ECAP) at room temperature after orienting the crystal such that [1 -1 -1] ayen ND, [0 1 -1] ayen ED, and [-2 -1 -1] ayen TD. Electron backscatter diffraction (EBSD) was used to characterize the microstructures both on the transverse and the longitudinal sections of the deformed sample. After one pass of ECAP the single crystal exhibits a group of homogeneously distributed large misorientation sheets and a well formed cell structure in the matrix. The traces of the large misorientation sheets match very well with the most favorably oriented slip plane and one of the slip directions is macroscopically aligned with the simple shear plane. The lattice rotation during deformation was quantitatively estimated through comparison of the orientations parallel to three macroscopic axes before and after deformation. An effort has been made to link the microstructure with the initial crystal orientation. Collinear slip systems are believed to be activated during deformation. The full constraints Taylor model was used to simulate the orientation evolution during ECAP. The result matched only partially with the experimental observation.

An In-Depth Study of the Barkhausen Emission Signal Properties of the Plastically Deformed Fe-2%Si Alloy

This paper presents the results of the in-depth study of the Barkhausen effect signal properties for the plastically deformed Fe-2%Si samples. The investigated samples have been deformed by cold rolling up to plastic strain epsilon(p) = 8%. The first approach consisted of time-domain-resolved pulse and frequency analysis of the Barkhausen noise signals whereas the complementary study consisted of the time-resolved pulse count analysis as well as a total pulse count. The latter included determination of time distribution of pulses for different threshold voltage levels as well as the total pulse count as a function of both the amplitude and the duration time of the pulses. The obtained results suggest that the observed increase in the Barkhausen noise signal intensity as a function of deformation level is mainly due to the increase in the number of bigger pulses.

Characterization of electrical penetration graphs of the Asian citrus psyllid, Diaphorina citri, in sweet orange seedlings

Detailed information on probing behavior of the Asian citrus psyllid, Diaphorina citri Kuwayama (Hemiptera: Psyllidae), is critical for understanding the transmission process of phloem-limited bacteria (Candidatus Liberibacter spp.) associated with citrus `huanglongbing` by this vector. In this study, we investigated stylet penetration activities of D. citri on seedlings of Citrus sinensis (L.) Osbeck cv. Pera (Rutaceae) by using the electrical penetration graph (EPG-DC system) technique. EPG waveforms were described based on amplitude, frequency, voltage level, and electrical origin of the observed traces during stylet penetration into plant tissues. The main waveforms were correlated with histological observations of salivary sheath termini in plant tissues, to determine the putative location of stylet tips. The behavioral activities were also inferred based on waveform similarities in relation to other Sternorrhyncha, particularly aphids and whiteflies. In addition, we correlated the occurrence of specific waveforms with the acquisition of the phloem-limited bacterium Ca. Liberibacter asiaticus by D. citri. The occurrence of a G-like xylem sap ingestion waveform in starved and unstarved psyllids was also compared. By analyzing 8-h EPGs of adult females, five waveforms were described: (C) salivary sheath secretion and other stylet pathway activities; (D) first contact with phloem (distinct from other waveforms reported for Sternorrhyncha); (E1) putative salivation in phloem sieve tubes; (E2) phloem sap ingestion; and (G) probably xylem sap ingestion. Diaphorina citri initiates a probe with stylet pathway through epidermis and parenchyma (C). Interestingly, no potential drops were observed during the stylet pathway phase, as are usually recorded in aphids and other Sternorrhyncha. Once in C, D. citri shows a higher propensity to return to non-probing than to start a phloem or xylem phase. Several probes are usually observed before the phloem phase; waveform D is observed upon phloem contact, always immediately followed by E1. After E1, D. citri either returns to pathway activity (C) or starts phloem sap ingestion, which was the longest activity observed.

Characterization of electrical penetration graphs of Bucephalogonia xanthophis, a vector of Xylella fastidiosa in citrus

The sharpshooter Bucephalogonia xanthophis (Berg) (Homoptera: Cicadellidae) is a vector of the xylem-limited bacterium, Xylella fastidiosa (Wells, Raju, Hung, Weisburg, Mandelco-Paul, and Brenner), which causes citrus variegated chlorosis. Despite the importance of citrus variegated chlorosis, the probing behavior of vectors on citrus and its implications for transmission of X. fastidiosa have not been studied. Here we studied electrical penetration graph (EPG-DC system) waveforms produced by B. xanthophis on Citrus sinensis (L.) Osbeck (Rutaceae), and their relationships with stylet activities and xylem ingestion. Electrical penetration graph waveforms were described based on amplitude, frequency, voltage level, and electrical origin of the observed traces during stylet penetration on plant tissues. The main waveforms were correlated with histological observations of salivary sheaths in plant tissues and excretion analysis, in order to determine stylet activities and their precise position. Six waveforms and associated activities are described: (S) secretion of salivary sheath and intracellular stylet pathway, (R) resting during stylet pathway, (Xc) contact of stylets with xylem vessels, (Xi) active xylem ingestion, (N) interruption within the xylem phase (during Xc or Xi), and (W) withdrawal of stylet from the plant. The sharpshooter spent 91.8% of its probing time with its stylet in the xylem, where the main activity was ingestion (Xi: 97.5%). During a probe, the most likely sequence of events is secretion of salivary sheath and pathway (S) through epidermal and parenchyma cells (all individuals), followed by contact with xylem (Xc) (67.6% of all individuals) and ingestion (Xi) (88.3% of those that exhibit waveform Xc). The mean time to contact the xylem (Xc) and initiate ingestion (Xi) after onset of the first probe was 27.8 and 34.2 min, respectively. However, sustained xylem ingestion (Xi > 5 min) was established after 39.8 min, on average. This information is basic for future studies on the transmission mechanisms of X. fastidiosa and in order to establish control strategies aimed at interfering with this process.

Trades and Graphs

The trade spectrum of a simple graph G is defined to be the set of all t for which it is possible to assemble together t copies of G into a simple graph H, and then disassemble H into t entirely different copies of G. Trade spectra of graphs have applications to intersection problems, and defining sets, of G-designs. In this investigation, we give several constructions, both for specific families of graphs, and for graphs in general.

Packing complete multipartite graphs with 4-cycles

In this paper we completely solve the problem of finding a maximum packing of any complete multipartite graph with edge-disjoint 4-cycles, and the minimum leaves are explicitly given.

Decomposition of complete tripartite graphs into gregarious 4-cycles

A 4-cycle in a tripartite graph with vertex partition {V-1, V-2, V-3} is said to be gregarious if it has at least one vertex in each V-i, 1 less than or equal to i less than or equal to 3. In this paper, necessary and sufficient conditions are given for the existence of an edge-disjoint decomposition of any complete tripartite graph into gregarious 4-cycles.

Common multiples of complete graphs

A graph H is said to divide a graph G if there exists a set S of subgraphs of G, all isomorphic to H, such that the edge set of G is partitioned by the edge sets of the subgraphs in S. Thus, a graph G is a common multiple of two graphs if each of the two graphs divides G.

Integrable open-boundary conditions for the q-deformed supersymmetric U model of strongly correlated electrons

A general graded reflection equation algebra is proposed and the corresponding boundary quantum inverse scattering method is formulated. The formalism is applicable to all boundary lattice systems where an invertible R-matrix exists. As an application, the integrable open-boundary conditions for the q-deformed supersymmetric U model of strongly correlated electrons are investigated. The diagonal boundary K-matrices are found and a class of integrable boundary terms are determined. The boundary system is solved by means of the coordinate space Bethe ansatz technique and the Bethe ansatz equations are derived. As a sideline, it is shown that all R-matrices associated with a quantum affine superalgebra enjoy the crossing-unitarity property. (C) 1998 Elsevier Science B.V.