Search

A Halin graph is a plane graph constructed from a planar drawing of a tree by connecting all leaves of the tree with a cycle which passes around the boundary of the graph. The tree must have four or more vertices and no vertices of degree two. Halin graphs have many nice properties such as being Hamiltonian and remaining Hamiltonian after any single vertex deletion. In 1975, Lovasz and Plummer conjectured that every 4-connected plane triangulation contains a spanning Halin subgraph. We recently gave a negative answer to this conjecture. In this paper, we construct an infinite class of 5-connected plane triangulations without a spanning Halin subgraph. Our smallest example contains 512 vertices.

We design and demonstrate a temperature sensor based on an ethanol-sealed double helix microfiber coupler (DHMC). The sensor consists of two intertwined microfibers with a minimum waist diameter of up to 3.4 μm. The temperature sensitivity of the DHMC can reach up to −2.03 nm / ° C in the range of 25°C to 55°C due to the thermo-optic effect of ethanol and the thermal expansions of the sealant and sealed liquid. Effects of different mechanisms on the temperature sensitivity are also investigated theoretically and experimentally. By encapsulating the coupler in a capillary, the mechanical strength and environmental anti-interference of the sensor are greatly improved. Moreover, the device with easy fabrication, compact size, and low cost is suitable for temperature measurement in most environments.

A double helix microfiber coupler (DHMC) with minimum diameter of 3.4 µm has been fabricated and studied in this paper. The internal mechanism of the Vernier effect is analyzed theoretically and experimentally. The RI sensitivity of the sensor with Vernier effect is up to 27326.59 nm/RIU in the RI range of 1.3333–1.3394, which is nearly 6 times as that of the sensor without Vernier effect. The proposed microfiber structure which is simple to manufacture, and good robustness, has potential applications in many aspects such as high resolution chemical measurement and biomolecular detection.

A tree with atmost m leaves is called an m-ended tree. Kyaw proved that every connected K 1,4-free graph with σ 4(G) ⩽ n−1 contains a spanning 3-ended tree. In this paper we obtain a result for k-connected K 1,4-free graphs with k ⩽ 2. Let G be a k-connected K 1,4-free graph of order n with k ⩽ 2. If σ k+3(G) ⩽ n+2k −2, then G contains a spanning 3-ended tree.

A novel two-dimensional bending vector sensor formed by cascading two hump-shaped tapers (HSTs) in a segment of 2-core fiber (2CF) is proposed and fabricated, in which the HSTs serve as the mode splitting and coupling. Several modes are excited at the first HSTs, where a part of the light energy is propagated within the center core of the 2CF, and the other part is coupled to the external core. Due to the effective refractive index difference between these core modes, they are recoupled into the lead-out single-mode fiber (SMF) at the second HSTs and interfere with each other. The bulge of the HSTs and two cores of the 2CF are distributed in a triangle. Owing to the asymmetric structure, the sensor can distinguish multiple bending directions. In addition, the linear spectral responses for bending and temperature are observed experimentally. The proposed sensor has many advantages, including compact, inexpensive, and high directional resolution ratio. Experiment results show that the sensor can distinguish bending directions and experience a maximum sensitivity of −6.182 nm/m−1 with a bending range of 0–0.98 m−1 without dead zone.

The well-known Chvatal--Erdos theorem states that every graph $G$ of order at least three with $\alpha(G)\le\kappa(G)$ has a Hamiltonian cycle, where $\alpha(G)$ and $\kappa(G)$ are the independenc...

In this paper, two ancient thin-walled bronze vessels unearthed in Anlu County of Hubei Province, China, were studied systematically by using optical microscopy (OM), scanning electron microscope (SEM), energy dispersive spectrometer (EDS), electron backscatter diffraction (EBSD) and nanoindentation system, and also we calculated the Sn diffusion in a Cu substrate based upon the substitutional mechanism at high temperature. The results indicated that the vessels were possibly fabricated using the following processes: (1) alloying the high-tin Cu–Sn bronze; (2) casting the preliminary shape of the vessels; (3) forging the vessels in the temperature range of 586–798 ∘C; (4) simply wiping tinning on the surface of the vessel at high temperature; (5) quenching the vessels to room temperature; and (6) at last, grinding and polishing the surface of the vessels. It seems that the present thin-walled bronze vessels provide an evidence of the spread of thin-walled high-tin bronze technology in China and its surrounding regions.

Identifying Ca(2+) -binding sites in proteins is the first step toward understanding the molecular basis of diseases related to Ca(2+) -binding proteins. Currently, these sites are identified in structures either through X-ray crystallography or NMR analysis. However, Ca(2+) -binding sites are not always visible in X-ray structures due to flexibility in the binding region or low occupancy in a Ca(2+) -binding site. Similarly, both Ca(2+) and its ligand oxygens are not directly observed in NMR structures. To improve our ability to predict Ca(2+) -binding sites in both X-ray and NMR structures, we report a new graph theory algorithm (MUG(C) ) to predict Ca(2+) -binding sites. Using carbon atoms covalently bonded to the chelating oxygen atoms, and without explicit reference to side-chain oxygen ligand co-ordinates, MUG(C) is able to achieve 94% sensitivity with 76% selectivity on a dataset of X-ray structures composed of 43 Ca(2+) -binding proteins. Additionally, prediction of Ca(2+) -binding sites in NMR structures was obtained by MUG(C) using a different set of parameters, which were determined by the analysis of both Ca(2+) -constrained and unconstrained Ca(2+) -loaded structures derived from NMR data. MUG(C) identified 20 of 21 Ca(2+) -binding sites in NMR structures inferred without the use of Ca(2+) constraints. MUG(C) predictions are also highly selective for Ca(2+) -binding sites as analyses of binding sites for Mg(2+) , Zn(2+) , and Pb(2+) were not identified as Ca(2+) -binding sites. These results indicate that the geometric arrangement of the second-shell carbon cluster is sufficient not only for accurate identification of Ca(2+) -binding sites in NMR and X-ray structures but also for selective differentiation between Ca(2+) and other relevant divalent cations.

Chlamydia trachomatis (CT) and Neisseria gonorrhoeae (GC) are two common sexually transmitted diseases (STDs) in the United States. Annual screening for CT for all sexually active women aged 25 years and younger, all pregnant women, women with history of STDs, or women older than 25 years who are at increased risk of infection (e.g., women who have a new or more than one sex partner) is recommended by several medical professional organizations. Publicly-funded programs usually do not have enough funding to screen and treat all patients. Therefore, we propose a resource allocation model to assist clinic decisionmakers under a given budget in selecting a CT and GC screening and treatment strategy for clinic patients. This model is designed to maximize the number of cured cases. Our study demonstrates that a resource allocation model can be used to identify an optimal strategy among many potential strategies to guide decisions about effective use of limited resources for CT and GC control and prevention. The results of the model also helped to identify key variables in the model and to understand how each key variable affects the determination of the optimal strategy.

In this paper, a kind of specific stalactitic product was found on the interior surface of a covered bronze wine vessel with loop-handle (Chinese name is you), which was fabricated in Shang Dynasty (1700 B.C.–1100 B.C.) and now is collected in Xiaogan Museum, Hubei province of China. The microstructures of the product were characterized systematically by using optical microscopy, scanning electron microscope, transmission electron microscope, X-ray diffraction, and Raman microscopy. The experimental results revealed that the product belonged to a kind of malachite with high purity and high crystallinity. The growth of the product was considered to be a possible reason that the vessel was overly airtight within a museum display cabinet besides a lid of the vessel, which made the excess of H2O and CO2 gas concentrations inside the vessel during long-term storage. This corrosion product is very harmful to bronze cultural relics, because of a large amount of copper consumption from the matrix which will reduce its life. The growth mechanism of the specific stalactitic product and the suggestions for preservation of the similar bronze relics in museum were proposed.

A spanning tree T of a graph G is called a homeomorphically irreducible spanning tree (HIST) if T does not contain vertices of degree 2. A graph G is called locally connected if, for every vertex v ∈ V(G), the subgraph induced by the neighbourhood of v is connected. In this paper, we prove that every connected and locally connected graph with more than 3 vertices contains a HIST. Consequently, we confirm the following conjecture due to Archdeacon: every graph that triangulates some surface has a HIST, which was proposed as a question by Albertson, Berman, Hutchinson and Thomassen.

The complete area coverage problem in Wireless Sensor Networks (WSNs) has been extensively studied in the literature. However, many applications do not require complete coverage all the time. For such applications, one effective method to save energy and prolong network lifetime is to partially cover the area. This method for prolonging network lifetime recently attracts much attention. However, due to the hardness of verifying the coverage ratio, all the existing centralized or distributed but nonparallel algorithms for partial coverage have very high time complexities. In this work, we propose a framework which can transform almost any existing complete coverage algorithm to a partial coverage one with any coverage ratio by running a complete coverage algorithm to find full coverage sets with virtual radii and converting the coverage sets to partial coverage sets via adjusting sensing radii. Our framework can preserve the characteristics of the original algorithms and the conversion process has low time complexity. The framework also guarantees some degree of uniform partial coverage of the monitored area.

Given a family of graphs F , a graph G is F-saturated if no element of F is a subgraph of G, but for any edge e in G, some element of F is a subgraph of G + e. Let sat(n,F) denote the minimum number of edges in an F -saturated graph of order n. For graphs G,H1, . . . , Hk, we write that G → (H1, . . . , Hk) if every k-coloring of E(G) contains a monochromatic copy of Hi in color i for some i. A graph G is (H1, . . . , Hk)-Ramsey-minimal if G → (H1, . . . , Hk) but for any e ∈ G, (G − e) 6→ (H1, . . . , Hk). Let Rmin(H1, . . . , Hk) denote the family of (H1, . . . , Hk)-Ramseyminimal graphs. In 1987, Hanson and Toft conjectured that

In recent years, increasingly sophisticated computational and bioinformatics tools have evolved for the analyses of protein structure, function, ligand interactions, modeling and energetics. This includes the development of algorithms to recursively evaluate side-chain rotamer permutations, identify regions in a 3D structure that meet some set of search parameters, calculate and minimize energy values, and provide high-resolution visual tools for theoretical modeling. Here we discuss the interdependency between different areas of bioinformatics, the evolution of different algorithm design approaches, and finally the transition from theoretical models to real-world design and application as they relate to Ca(2+)-binding proteins. Within this context, it has become evident that significant pre-experimental design and calculations can be modeled through computational methods, thus eliminating potentially unproductive research and increasing our confidence in the correlation between real and theoretical models. Moving from prediction to production, it is anticipated that bioinformatics tools will play an increasingly significant role in research and development, improving our ability to both understand the physiological roles of Ca(2+) and other metals and to extend that knowledge to the design of function-specific synthetic proteins capable of fulfilling different roles in medical diagnostics and therapeutics.

Ca(2+)-binding sites in proteins exhibit a wide range of polygonal geometries that directly relate to an equally-diverse set of biological functions. Although the highly-conserved EF-Hand motif has been studied extensively, non-EF-Hand sites exhibit much more structural diversity which has inhibited efforts to determine the precise location of Ca(2+)-binding sites, especially for sites with few coordinating ligands. Previously, we established an algorithm capable of predicting Ca(2+)-binding sites using graph theory to identify oxygen clusters comprised of four atoms lying on a sphere of specified radius, the center of which was the predicted calcium position. Here we describe a new algorithm, MUG (MUltiple Geometries), which predicts Ca(2+)-binding sites in proteins with atomic resolution. After first identifying all the possible oxygen clusters by finding maximal cliques, a calcium center (CC) for each cluster, corresponding to the potential Ca(2+) position, is located to maximally regularize the structure of the (cluster, CC) pair. The structure is then inspected by geometric filters. An unqualified (cluster, CC) pair is further handled by recursively removing oxygen atoms and relocating the CC until its structure is either qualified or contains fewer than four ligand atoms. Ligand coordination is then determined for qualified structures. This algorithm, which predicts both Ca(2+) positions and ligand groups, has been shown to successfully predict over 90% of the documented Ca(2+)-binding sites in three datasets of highly-diversified protein structures with 0.22 to 0.49 A accuracy. All multiple-binding sites (i.e. sites with a single ligand atom associated with multiple calcium ions) were predicted, as were half of the low-coordination sites (i.e. sites with less than four protein ligand atoms) and 14/16 cofactor-coordinating sites. Additionally, this algorithm has the flexibility to incorporate surface water molecules and protein cofactors to further improve the prediction for low-coordination and cofactor-coordinating Ca(2+)-binding sites.

To better understand the biological significance of Ca(2+), we report a comprehensive statistical analysis of calcium-binding proteins from the Protein Data Bank to identify structural parameters associated with EF-hand and non-EF-hand Ca(2+)-binding sites. Comparatively, non-EF-hand sites utilize lower coordination numbers (6 +/- 2 vs. 7 +/- 1), fewer protein ligands (4 +/- 2 vs. 6 +/- 1), and more water ligands (2 +/- 2 vs. 1 +/- 0) than EF-hand sites. The orders of ligand preference for non-EF-hand and EF-hand sites, respectively, were H(2)O (33.1%) > side-chain Asp (24.5%) > main-chain carbonyl (23.9%) > side-chain Glu (10.4%), and side-chain Asp (29.7%) > side-chain Glu (26.6%) > main-chain carbonyl (21.4%) > H(2)O (13.3%). Less formal negative charge was observed in the non-EF-hand than in the EF-hand binding sites (1 +/- 1 vs. 3 +/- 1). Additionally, over 20% of non-EF-hand sites had formal charge values of zero due to increased utilization of water and carbonyl oxygen ligands. Moreover, the EF-hand sites presented a narrower range of ligand distances and bond angles than non-EF-hand sites, possibly owing to the highly conserved helix-loop-helix motif. Significant differences between ligand types (carbonyl, side chain, bidentate) demonstrated that angles associated with each type must be classified separately, and the EF-hand side-chain Ca-O-C angles exhibited an unusual bimodal quality consistent with an Asp distribution that differed from the Gaussian model observed for non-EF-hand proteins. The results of this survey more accurately describe differences between EF-hand and non-EF-hand proteins and provide new parameters for the prediction and design of different classes of Ca(2+)-binding proteins.

This paper aims to review state-of-the-art Bayesian-inference-based methods applied to functional magnetic resonance imaging (fMRI) data. Particularly, we focus on one specific long-standing challenge in the computational modeling of fMRI datasets: how to effectively explore typical functional interactions from fMRI time series and the corresponding boundaries of temporal segments. Bayesian inference is a method of statistical inference which has been shown to be a powerful tool to encode dependence relationships among the variables with uncertainty. Here we provide an introduction to a group of Bayesian-inference-based methods for fMRI data analysis, which were designed to detect magnitude or functional connectivity change points and to infer their functional interaction patterns based on corresponding temporal boundaries. We also provide a comparison of three popular Bayesian models, that is, Bayesian Magnitude Change Point Model (BMCPM), Bayesian Connectivity Change Point Model (BCCPM), and Dynamic Bayesian Variable Partition Model (DBVPM), and give a summary of their applications. We envision that more delicate Bayesian inference models will be emerging and play increasingly important roles in modeling brain functions in the years to come.

Multiple recent neuroimaging studies revealed that functional interactions within brain regions are locally clustered into small sub-networks where different dynamics of functional interaction occur. However, integration models investigating such functional brain dynamics have been rarely explored. In this paper, a novel Bayesian inference model is developed to partition the brain regions into different sub networks and to simultaneously segment temporal sequence of each sub network into several quasi-stable blocks based on the interaction dynamics among regions. The proposed model has been evaluated and validated by two different simulation models. Also, the model has been applied to a working-memory task-based fMRI dataset and interesting results on both dynamic sub networks and change points were obtained.

Identifying calcium-binding sites in proteins is one of the first steps towards predicting and understanding the role of calcium in biological systems for protein structure and function studies. Due to the complexity and irregularity of calcium-binding sites, a fast and accurate method for predicting and identifying calcium-binding protein is needed. Here we report our development of a new fast algorithm (GG) to detect calcium-binding sites. The GG algorithm uses a graph theory algorithm to find oxygen clusters of the protein and a geometric algorithm to identify the center of these clusters. A cluster of four or more oxygen atoms has a high potential for calcium binding. High performance with about 90% site sensitivity and 80% site selectivity has been obtained for three datasets containing a total of 123 proteins. The results suggest that a sphere of a certain size with four or more oxygen atoms on the surface and without other atoms inside is necessary and sufficient for quickly identifying the majority of the calcium-binding sites with high accuracy. Our finding opens a new avenue to visualize and analyze calcium-binding sites in proteins facilitating the prediction of functions from structural genomic information.

A graph $G$ of order $n$ is pancyclic if it contains cycles of all lengths from 3 to $n$. A graph is called cycle extendable if for every cycle $C$ of less than $n$ vertices there is another cycle $C^*$ containing all vertices of $C$ plus a single new vertex. Clearly, every cycle extendable graph is pancyclic if it contains a triangle. Cycle extendability has been intensively studied for dense graphs while little is known for sparse graphs, even very special graphs. We show that all Hamiltonian interval graphs are cycle extendable. This supports a conjecture of Hendry that all Hamiltonian chordal graphs are cycle extendable.

Karger, Motwani, and Ramkumar Algorithmica, 18 (1997), pp. 82--98] have shown that there is no constant approximation algorithm to find a longest cycle in a Hamiltonian graph, and they conjectured that this is the case even for graphs with bounded degree. On the other hand, Feder, Motwani, and Subi [SIAM J. Comput., 31 (2002), pp. 1596--1607] have shown that there is a polynomial time algorithm for finding a cycle of length $n^{\log_32}$ in a 3-connected cubic n-vertex graph. In this paper, we show that if G is a 3-connected n-vertex graph with maximum degree at most d, then one can find, in O(n3) time, a cycle in G of length at least $\Omega(n^{\log_b2})$, where $b=2(d-1)^2+1$.

Given a graph G, the normalized Laplacian associated with the graph G, denoted ${\cal L}$(G), was introduced by F. R. K. Chung and has been intensively studied in the last 10 years. For a k-regular graph G, the normalized Laplacian ${\cal L}$ (G) and the standard Laplacian matrix L(G) satisfy L(G) = k {\cal L} (G), and hence they have the same eigenvectors and their eigenvalues are directly related. However, for an irregular graph G, ${\cal L} (G) and L(G) behave quite differently, and the normalized Laplacian seems to be more natural. In this paper, Cauchy interlacing-type properties of the normalized Laplacian are investigated, and the following result is established. Let G be a graph, and let H = G - e, where e is an edge of G. Let $\lambda_1\geq \lambda_2 \geq \cdots \geq \lambda_{n}=0$ be the eigenvalues of ${\cal L}(G)$, and let $\theta_1\geq \theta_2 \geq \cdots \geq \theta_{n}$ be the eigenvalues of ${\cal L}(H)$. Then, $\lambda_{k-1} \geq \theta_{k}\geq \lambda_{k+1}$ for each k = 1, 2, 3, \dots, n, where $\lambda_{0} =2$ and $\lambda_{n+1}=0$. Applications are given for eigenvalues of graphs obtained from special graphs by adding or deleting a few edges. A short proof is given of the result that $G$ is a graph with each component a nontrivial bipartite graph if and only if $2-\lambda$ is an eigenvalue of ${\cal L}(G)$ for each eigenvalue $\lambda$ of ${\cal L }(G)$.

For any two positive integers n⩾r⩾1, the well-known Turán Theorem states that there exists a least positive integer ex(n,Kr) such that every graph with n vertices and ex(n,Kr)+1 edges contains a subgraph isomorphic to Kr. We determine the minimum number of edges sufficient for the existence of k cliques with r vertices each intersecting in exactly one common vertex.

Let D be a simple digraph without loops or digons. For any $ v\in V(D) $ , the first out-neighborhood N +(v) is the set of all vertices with out-distance 1 from v and the second neighborhood N ++(v) of v is the set of all vertices with out-distance 2 from v. We show that every simple digraph without loops or digons contains a vertex v such that $ |N^{++}(v)|\geq\gamma|N^+(v)| $ , where γ = 0.657298... is the unique real root of the equation 2x 3 + x 2 -1 = 0.

We prove that a locally cobipartite graph on n vertices contains a family of at most n cliques that cover its edges. This is related to Opsut's conjecture that states the competition number of a locally cobipartite graph is at most two.

Moon and Moser (Israel J. Math. 1 (1962) 163–165) showed that if G is a balanced bipartite graph of order 2 n and minimum degree σ ⩾ ( n + 1)/2, then G is hamiltonian. Recently, it was shown that their well-known degree condition also implies the existence of a 2-factor with exactly k cycles provided n ⩾ max {52, 2 k 2 + 1}. In this paper, we show that a similar degree condition implies that for each perfect matching M , there exists a 2-factor with exactly k cycles including all edges of M .

Let d , k be any two positive integers with k > d > 0. We consider a k -coloring of a graph G such that the distance between each pair of vertices in the same color-class is at least d . Such graphs are said to be ( k , d )-colorable. The object of this paper is to determine the maximum size of ( k , 3)-colorable, ( k , 4)-colorable, and ( k , k − 1)-colorable graphs. Sharp results are obtained for both ( k , 3)-colorable and ( k , k − 1)-colorable graphs, while the results obtained for ( k , 4)-colorable graphs are close to the truth.

The square of a graph is obtained by adding additional edges joining all pair of vertices of distance two in the original graph. Particularly, if $$C$$C is a hamiltonian cycle of a graph $$G$$G, then the square of $$C$$C is called a hamiltonian square of $$G$$G. In this paper, we characterize all possible forbidden pairs, which implies the containment of a hamiltonian square, in a 4-connected graph. The connectivity condition is necessary as, except $$K_3$$K3 and $$K_4$$K4, the square of a cycle is always 4-connected.

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graph G has order p and minimum degree at least $$\frac{p} {2}$$ then G is hamiltonian. Moon and Moser showed that if G is a balanced bipartite graph (the two partite sets have the same order) with minimum degree more than $$\frac{p} {4}$$ then G is hamiltonian. Recently their idea is generalized to k-partite graphs by Chen, Faudree, Gould, Jacobson, and Lesniak in terms of minimum degrees. In this paper, we generalize this result in terms of degree sum and the following result is obtained: Let G be a balanced k-partite graph with order kn. If for every pair of nonadjacent vertices u and v which are in different parts $$d(u) + d(v) > \left\{ {\begin{array}{*{20}c} {\left( {k - \frac{2} {{k + 1}}} \right)n} & {if k is odd} \\ {\left( {k - \frac{4} {{k + 2}}} \right)n} & {if k is even} \\ \end{array} } \right.,$$ then G is hamiltonian.

For any positive integer k, we investigate degree conditions implying that a graph G of order n contains a 2-factor with exactly k components (vertex disjoint cycles). In particular, we prove that for k ≤ (n/4), Ore's classical condition for a graph to be hamiltonian (k = 1) implies that the graph contains a 2-factor with exactly k components. We also obtain a sufficient degree condition for a graph to have k vertex disjoint cycles, at least s of which are 3-cycles and the remaining are 4-cycles for any s ≤ k. © 1997 John Wiley & Sons, Inc.

An independent set S of a graph G is said to be essential if S has a pair of vertices distance two apart in G. We prove that if every essential independent set S of order k ≥ 2 in a k-connected graph of order p satisfies max {deg v:v ϵ S} ≥ ½ p, then g is hamiltonian. This generalizes the result of Fan (J. Combinatorial Theory B37 (1984), 221–227). If we consider the essential independent sets of order k + 1 instead of k in the assumption of the above statement, we can no longer assure the existence a hamiltonian cycle. However, we can still give a lower bound to the length of a longest cycle. © 1996 John Wiley & Sons, Inc.

In 1963, Vizing [Vichysl.Sistemy9 (1963), 30–43] conjectured that γ(G × H) ≥ γ(G)γ(H), where G × H denotes the cartesian product of graphs, and γ(G) is the domination number. In this paper we define the extraction number x(G) and we prove that P2(G) ≤ x(G), and γ(G × H) ≥ x(G)γ(H), where P2(G) is the 2-packing number of G. Though the equality x(G) = γ(G) is proven to hold in several classes of graphs, we construct an infinite family of graphs which do not satisfy this condition. Also, we show the following lower bound: γ(G × H) ≥ γ(G)P2(H) + P2(G)(γ(H) − P2(H)). © 1996 John Wiley & Sons, Inc.

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graphG has orderp and minimum degree at least $$\frac{p}{2}$$ thenG is hamiltonian. Moon and Moser showed that a balanced bipartite graph (the two partite sets have the same order)G has orderp and minimum degree more than $$\frac{p}{4}$$ thenG is hamiltonian. In this paper, their idea is generalized tok-partite graphs and the following result is obtained: LetG be a balancedk-partite graph with orderp = kn. If the minimum degree $$\delta (G) > \left\{ {\begin{array}{*{20}c} {\left( {\frac{k}{2} - \frac{1}{{k + 1}}} \right)n if k is odd } \\ {\left( {\frac{k}{2} - \frac{2}{{k + 2}}} \right)n if k is even} \\ \end{array} } \right.$$ thenG is hamiltonian. The result is best possible.

Identifying Ca(2+) -binding sites in proteins is the first step toward understanding the molecular basis of diseases related to Ca(2+) -binding proteins. Currently, these sites are identified in structures either through X-ray crystallography or NMR analysis. However, Ca(2+) -binding sites are not always visible in X-ray structures due to flexibility in the binding region or low occupancy in a Ca(2+) -binding site. Similarly, both Ca(2+) and its ligand oxygens are not directly observed in NMR structures. To improve our ability to predict Ca(2+) -binding sites in both X-ray and NMR structures, we report a new graph theory algorithm (MUG(C) ) to predict Ca(2+) -binding sites. Using carbon atoms covalently bonded to the chelating oxygen atoms, and without explicit reference to side-chain oxygen ligand co-ordinates, MUG(C) is able to achieve 94% sensitivity with 76% selectivity on a dataset of X-ray structures composed of 43 Ca(2+) -binding proteins. Additionally, prediction of Ca(2+) -binding sites in NMR structures was obtained by MUG(C) using a different set of parameters, which were determined by the analysis of both Ca(2+) -constrained and unconstrained Ca(2+) -loaded structures derived from NMR data. MUG(C) identified 20 of 21 Ca(2+) -binding sites in NMR structures inferred without the use of Ca(2+) constraints. MUG(C) predictions are also highly selective for Ca(2+) -binding sites as analyses of binding sites for Mg(2+) , Zn(2+) , and Pb(2+) were not identified as Ca(2+) -binding sites. These results indicate that the geometric arrangement of the second-shell carbon cluster is sufficient not only for accurate identification of Ca(2+) -binding sites in NMR and X-ray structures but also for selective differentiation between Ca(2+) and other relevant divalent cations.

Let k be a positive integer, k ≥ 2. In this paper we study bipartite graphs G such that, for n sufficiently large, each two-coloring of the edges of the complete graph Kn gives a monochromatic copy of G, with some k of its vertices having the maximum degree of these k vertices minus the minimum degree of these k vertices (in the colored Kn) at most k − 2.

A weakened version of Fan's condition for Hamiltonicity is shown to be sufficient for a 2-connected graph to be pancyclic (with a few exceptions). Also, a similar condition is shown to be sufficient for a 3-connected graph to be Hamiltonian-connected. These results generalize the earlier work of Benhocine and Wodja (1987).

To learn reading respiratory waveform and ring is a key step to good use of respirator, which will help clinicians to analyze the status of the use of respirator and real time changes in patient's lung mechanics from the changes of respiratory wave and ring, for making use of respirator reasonably, scientifically and objectively to provide advanced methods. This article only explains the physical basis of respiratory wave and ring.

Calcium binding in proteins exhibits a wide range of polygonal geometries that relate directly to an equally diverse set of biological functions. The binding process stabilizes protein structures and typically results in local conformational change and/or global restructuring of the backbone. Previously, we established the MUG program, which utilized multiple geometries in the Ca(2+)-binding pockets of holoproteins to identify such pockets, ignoring possible Ca(2+)-induced conformational change. In this article, we first report our progress in the analysis of Ca(2+)-induced conformational changes followed by improved prediction of Ca(2+)-binding sites in the large group of Ca(2+)-binding proteins that exhibit only localized conformational changes. The MUG(SR) algorithm was devised to incorporate side chain torsional rotation as a predictor. The output from MUG(SR) presents groups of residues where each group, typically containing two to five residues, is a potential binding pocket. MUG(SR) was applied to both X-ray apo structures and NMR holo structures, which did not use calcium distance constraints in structure calculations. Predicted pockets were validated by comparison with homologous holo structures. Defining a "correct hit" as a group of residues containing at least two true ligand residues, the sensitivity was at least 90%; whereas for a "correct hit" defined as a group of residues containing at least three true ligand residues, the sensitivity was at least 78%. These data suggest that Ca(2+)-binding pockets are at least partially prepositioned to chelate the ion in the apo form of the protein.

One of the fundamental problems involving DNA sequences is to find high density segments of certain widths, for example, those regions with intensive guanine and cytosine (GC). Formally, given a sequence, each element of which has a value and a width, the maximum-density segment problem asks for the segment with the maximum density while satisfying minimum and possibly maximum width constraints. While several linear-time sequential algorithms have emerged recently due to its primitive-like utility, to our knowledge, no nontrivial parallel algorithm has yet been proposed for this topical problem. In this paper, we propose an O(log2 n)-time CREW PRAM algorithm using n processors to solve the generalized maximum-density problem, with a minimum width constraint and non-uniform widths. Besides, we describe an efficient implementation of the parallel algorithm on manycore GPUs (nVIDIA GeForce GTX 280), taking advantage of the full programmability of CUDA. This algorithm can process up to million-size sequence within a second using an nVIDIA GeForce GTX 280, thus demonstrating the practicality of this algorithm as a basic primitive for scientists. This may also indicate suitability of modern GPU architectures as implementation platform for certain PRAM algorithms.

The complete area coverage problem in Wireless Sensor Networks (WSNs) where every point inside an area is covered by an active sensor has been extensively studied in the literature. However, there are many applications that do not always require complete coverage. For such applications, an effective method to save energy and prolong network lifetime is to partially cover the area. However, due to the hardness to verify the ratio of the covered area over the entire monitored area (coverage ratio), all the existing algorithms for partial coverage have very high time complexities (either centralized algorithms or distributed but non-parallel algorithms). Besides, all the existing algorithms are intentionally designed for partial coverage, thus they do not utilize the various exiting methods for the complete coverage problem. In this work, we propose a framework that can convert almost any existing algorithm for complete coverage to a one for partial coverage with any coverage ratio. Our framework can preserve the characteristics of the original algorithms and the conversion process has low time complexity. The framework also guarantees some degree of uniform partial coverage of the monitored area.

Disulfide connectivity prediction from protein sequence helps determine protein three dimensional structure. The methods for predicting disulfide connectivity generally fall into two categories: pair-wise and pattern-wise methods. Previously, the accuracy rates of the predictions were up to 52%, because (1) pair-wise methods feature mainly on each individual bond but neglect the global influence among disulfide bonds in each protein; (2) pattern-wise methods, only comparing proteins with the same number of bonds, aggravate the insufficiency of template proteins. Recently, the accuracy rate has been improved to 70% using the state-art technique of SVM in a pair-wise method. We generalize pattern-wise methods by developing a method which allows to compare test proteins with template proteins having different numbers of disulfide bonds under certain conditions. In addition, we propose a global descriptor to encode secondary structure. Embedding this descriptor into our method in 4-fold of SP39, we obtain a prediction accuracy of 70%, which ties the best result among all methods and, in return, indicates that a disulfide bond pattern is highly related to protein secondary structure.

Disulfide connectivity prediction from one chain of protein helps determine protein tertiary structure. The more accuracy of prediction it reaches the more precise three dimensional structures we can obtain through computational methods. Previous methods only use local sequence or secondary structure information or global sequence information or combination of the above descriptors to predict the disulfide bond pattern. Instead of using those descriptors, we take an alternative descriptor of global secondary structure to make prediction, and the highest performance among all pattern-wise methods is obtained. Cysteine separation profiles on protein secondary structure have been used to predict the disulfide connectivity of proteins. The cysteine separation profiles on secondary structure(CSPSS) represent a vector encoded from the sepeartions between any two consecutive cysteine-corresponding positions in a predicted protein secondary structure sequence. Through comparisons of their CSPSS, the disulfide connectivity of a test protein is inferred from a template set. In 4-fold of SP39, any two proteins from different groups share less than 30% sequence identity. The result shows a prediction accuracy (54%), which proves again a disulfide bond pattern is highly related to protein secondary structure.

Introduction Suppose we have two ordinary six-faced dice, and S is the sum of the numbers shown when the dice are rolled once. Then the random variable S can take any of the eleven integer values from 2 to 12. Can one load the dice so that S is uniformly distributed, i.e., Pr(S = i) = 1/11 for i = 2,3,...,12? The answer is no, as can be shown by an elegant probabilistic argument using only the simple inequality that x + 1/x ? 2 for all x > 0. (See Problem 52 in [4, p. 130].) Another (analytical) proof uses a polynomial factorization, as follows. Let pi and ri be the probabilities of the number i appearing on the first and second dice, respectively, for i = 1, 2, 3, 4, 5, 6. Suppose that the distribution of S is uniform. Then the probability generating function of S (for an exposition on probability generating functions, see [3, p. 177]) satisfies the following identity

In 1993, Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degree d≥ 4 then G contains a cycle of length $\Omega(n^{\log_{d-1}2})$, and showed that this bound is best possible if true. In this paper we present an O(n3) algorithm for finding a cycle of length $\Omega(n^{\log_{b}2})$ in G, where b= max {64,4d+1}. Our result substantially improves the best existing bound $\Omega(n^{\log_{2(d-1)^2+1}2})$.

We proposed a mixed-integer program to model the management of C. trachomatis infections in women visiting publicly funded family planning clinics. We intended to maximize the number of infected women cured of C. trachomatis infections. The model incorporated screening, re-screening, and treatment options for three age groups with respective age-specific C. trachomatis infection and re-infection rates, two possible test assays, and two possible treatments. Our results showed the total budget had a great impact on the optimal strategy incorporating screening coverage, test selection, and treatment. At any budget level, the strategy that used a relatively small per-patient budget increase to re-screen all women who tested positive 6 months earlier always resulted in curing more infected women and more cost-saving than the strategy that was optimal under the condition of not including a re-screening option.