Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “graph theory”

Search indexed PubMed citations on genomics, clinical trials, systematic reviews and public health. Explore titles, authors and supplied subject terms, then open the PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 307 records · Page 17Linked to original sources
PubMed2005

Convergence to the island-model coalescent process in populations with restricted migration.

In this article we apply some graph-theoretic results to the study of coalescence in a structured population with migration. The graph is the pattern of migration among subpopulations, or demes, and we use the theory of random walks on graphs to characterize the ease with which ancestral lineages can traverse the habitat in a series of migration events. We identify conditions under which the coalescent process in populations with restricted migration, such that individuals cannot traverse the habitat freely in a single migration event, nonetheless becomes identical to the coalescent process in the island migration model in the limit as the number of demes tends to infinity. Specifically, we first note that a sequence of symmetric graphs with Diaconis-Stroock constant bounded above has an unstructured Kingman-type coalescent in the limit for a sample of size two from two different demes. We then show that circular and toroidal models with long-range but restricted migration have an upper bound on this constant and so have an unstructured-migration coalescent in the limit. We investigate the rate of convergence to this limit using simulations.

Algorithms↗
PubMed2004

Scalar gradient fields by geometric measure theory.

Upper bounds of the Hausdorff volume of scalar gradient field graphs are derived by means of geometric measure theory. The approach reproduces that scalar gradient fields along a mean imposed scalar gradient become space filling for sufficiently high values of Schmidt numbers Sc. The bounds are consistent with findings from recent high-resolution numerical experiments for 1< or =Sc< or =64, but too rough when compared with numerical simulations. A Reynolds number dependence of the bounds is found due to the additional scalar gradient stretching term in the equation of motion.

Journal Article↗
PubMed2005

Hydrogen-bond topology and the ice VII/VIII and ice Ih/XI proton-ordering phase transitions.

The existence of an ice Ih/XI proton-ordering transition to a low-temperature ferroelectric phase has sparked considerable debate in the literature. Electronic density functional theory calculations, extended using graph invariants, confirm that a transition to a low-temperature ferroelectric phase should occur. The predicted transition at 98 K is in qualitative agreement with the observed transition at 72 K, and the low-temperature phase is the ferroelectric phase determined in diffraction experiments. The theoretical methods used to predict the phase transition are validated by comparing their prediction to the well-characterized ice VII/VIII proton-ordering transition.

Journal Article↗
PubMed2006

Medical image segmentation using minimal path deformable models with implicit shape priors.

This paper presents a new method for segmentation of medical images by extracting organ contours, using minimal path deformable models incorporated with statistical shape priors. In our approach, boundaries of structures are considered as minimal paths, i.e., paths associated with the minimal energy, on weighted graphs. Starting from the theory of minimal path deformable models, an intelligent "worm" algorithm is proposed for segmentation, which is used to evaluate the paths and finally find the minimal path. Prior shape knowledge is incorporated into the segmentation process to achieve more robust segmentation. The shape priors are implicitly represented and the estimated shapes of the structures can be conveniently obtained. The worm evolves under the joint influence of the image features, its internal energy, and the shape priors. The contour of the structure is then extracted as the worm trail. The proposed segmentation framework overcomes the short-comings of existing deformable models and has been successfully applied to segmenting various medical images.

Algorithms↗
PubMed2006

MP-SAGE: A new MP-RAGE sequence with enhanced SNR and CNR for brain imaging utilizing square-spiral phase encoding and variable flip angles.

The magnetization-prepared rapid gradient-echo (MP-RAGE) sequence is well known and widely used for high-resolution, structural brain MRI. Here we present a new version, termed magnetization-prepared spiral acquisition gradient-echo (MP-SAGE), that employs interleaved square-spiral phase-encoding (PE) to take advantage of the 3D nature of the sequence. Resolution loss caused by point-spread function (PSF) blurring is circumvented by the use of variable flip angle (VFA) radiofrequency (RF) pulses. The pulse train is calculated by means of an accurate new signal evolution theory that is derived from the extended phase graph (EPG) description. Phantom results show excellent agreement between theory and experiment for substances with relaxation times similar to those of human brain tissue. Both phantom and in vivo results show a strong enhancement of SNR and CNR compared to the standard MP-RAGE in high-resolution MRI. The benefits for brain tissue segmentation using images obtained with MP-SAGE are shown.

Algorithms↗
PubMedDate not supplied

A graph-based toy model of chemistry.

Large scale chemical reaction networks are a ubiquitous phenomenon, from the metabolism of living cells to processes in planetary atmospheres and chemical technology. At least some of these networks exhibit distinctive global features such as the "small world" behavior. The systematic study of such properties, however, suffers from substantial sampling biases in the few networks that are known in detail. A computational model for generating them is therefore required. Here we present a Toy Model that provides a consistent framework in which generic properties of extensive chemical reaction networks can be explored in detail and that at the same time preserves the "look-and-feel" of chemistry: Molecules are represented as labeled graphs, i.e., by their structural formulas; their basic properties are derived by a caricature version of the Extended Hückel MO theory that operates directly on the graphs; chemical reaction mechanisms are implemented as graph rewriting rules acting on the structural formulas; reactivities and selectivities are modeled by a variant of the Frontier Molecular Orbital Theory based on the Extended Hückel scheme. The approach is illustrated for two types of reaction networks: Diels-Alder reactions and the formose reaction implicated in prebiotic sugar synthesis.

Journal Article↗
PubMed2005

Exact and approximate graph matching using random walks.

In this paper, we propose a general framework for graph matching which is suitable for different problems of pattern recognition. The pattern representation we assume is at the same time highly structured, like for classic syntactic and structural approaches, and of subsymbolic nature with real-valued features, like for connectionist and statistic approaches. We show that random walk based models, inspired by Google's PageRank, give rise to a spectral theory that nicely enhances the graph topological features at node level. As a straightforward consequence, we derive a polynomial algorithm for the classic graph isomorphism problem, under the restriction of dealing with Markovian spectrally distinguishable graphs (MSD), a class of graphs that does not seem to be easily reducible to others proposed in the literature. The experimental results that we found on different test-beds of the TC-15 graph database show that the defined MSD class "almost always" covers the database, and that the proposed algorithm is significantly more efficient than top scoring VF algorithm on the same data. Most interestingly, the proposed approach is very well-suited for dealing with partial and approximate graph matching problems, derived for instance from image retrieval tasks. We consider the objects of the COIL-100 visual collection and provide a graph-based representation, whose node's labels contain appropriate visual features. We show that the adoption of classic bipartite graph matching algorithms offers a straightforward generalization of the algorithm given for graph isomorphism and, finally, we report very promising experimental results on the COIL-100 visual collection.

Algorithms↗
PubMed1989

Protons resolve dual effects of calcium on miniature end-plate potential frequency at frog neuromuscular junctions.

Inhibition of transmitter release by protons (H+) was studied at the frog neuromuscular junction at various extracellular concentrations of calcium ([Ca++]o) and potassium ([K+]o) by recording miniature end-plate potential (MEPP) frequency with the intracellular microelectrode. H+ decreased K+ -stimulated MEPP frequency. A double logarithmic graph of MEPP frequency at 7.5 mM K+ vs. [H+]o yielded a straight line with negative slope. At 10 mM K+, there was a parallel shift to the right of the graph. According to the surface charge model, K+ acts solely to depolarize the prejunctional membrane in accordance with the Nernst equation. By decreasing the prejunctional negative surface charge, H+ decreases K+ -stimulated MEPP frequency by decreasing [Ca++]o at the Ca++ channel. An estimated pKa of 4.20 may represent an acidic site at the Ca++ channel associated with Ca++ influx. As [Ca++]o increased above 1 mM for pH 7.40 and 10 mM K+, MEPP frequency decreased, i.e., the inhibitory component of dual effects of Ca++ occurred. At pH 6.40, the inhibitory component was abolished, unmasking the stimulatory effect of Ca++ on MEPP frequency. Reversal of Ca++ action by H+ could not be explained by surface charge theory alone. A double logarithmic graph of MEPP frequency vs. [K+]o at 8.5-10.5 mM was linear with a slope of 4. There were parallel shifts to the right of this graph for changes in pH from 7.40 to 6.90 and in [Ca++]o from 1 to 2.5 mM. These results are explained on the hypothesis that K+ also acts at an acidic prejunctional site to increase Ca++ -dependent quantal transmitter release. This action of K+ was inhibited by H+ and raised Ca++. Based on kinetic theory, the estimated pKa of the acidic prejunctional K+ site was 6.31. Based on free energy calculations, its cation preference was H+ greater than K+ greater than Ca++.

Animals↗
PubMed1984

Direct potentiometric determination of sodium ion in blood. I. Potentiometric response in simple sodium chloride solutions.

We measured the emf of NaCl solutions (120-160 mmol/L) with a home-built cell in steady-state and with some commercial direct potentiometric analyzers about 20 s after the sample is introduced into the instrument. We compared the results with the theoretical sodium ion activity calculated according to different thermodynamic theories. The slope of the calibration graph was calculated with and without correction for the influence of NaCl concentration on the liquid junction potential of the calomel reference electrode. We conclude that different theories used to calculate the sodium ion activity in the concentration range investigated give almost the same results; furthermore, introduction of the liquid junction potential leads to a more nernstian-like slope of the calibration graph. Measurement of identical NaCl solutions with various commercial analyzers showed different displayed concentrations, presumably because of differences in junction structure, measuring time, and concentration of calibration solutions.

Electrodes↗
PubMedDate not supplied

Using neural network predicted secondary structure information in automatic protein NMR assignment.

In CAPRI, an automated NMR assignment software package that was developed in our laboratory, both chemical shift values and coupling topologies of spin patterns are used in a procedure for amino acids recognition. By using a knowledge base of chemical shift distributions of the 20 amino acid types, fuzzy mathematics, and pattern recognition theory, the spin coupling topological graphs are mapped onto specific amino acid residues. In this work, we investigated the feasibility of using secondary structure information of proteins as predicted by neural networks in the automated NMR assignment. As the 1H and 13C chemical shifts of proteins are known to correlate to their secondary structures, secondary structure information is useful in improving the amino acid recognition. In this study, the secondary structures of proteins predicted by the PHD protein server and our own trained neural networks are used in the amino acid type recognition. The results show that the predicted secondary structure information can help to improve the accuracy of the amino acid recognition.

Algorithms↗
PubMed1993

Heat flux transducer measurement error: a simplified view.

Heat flux transducers (HFTs) provide a simple and direct measurement of body heat exchange. Regrettably, HFTs perturb the heat flux at the measurement site, resulting in underestimations of the true heat flux. Equations to correct the discrepancy are available, but most require high-precision temperature measurements above and/or below the transducer and/or deep within the body tissues. Because this is not always feasible, the equations are of limited practical benefit. A theoretical basis for the magnitude of the correction factor in relation to the thermal resistances of the materials both above and below the HFT has been developed and has been verified experimentally. The theory is presented in a graph that can be used to drive the HFT correction factor directly or as a guide to know that heat flux was measured within a certain accuracy. This may obviate the use of complicated procedures and equations to perhaps needlessly apply a small correction factor to HFT data.

Biophysical Phenomena↗
PubMed2001

The Whitney reduction network: a method for computing autoassociative graphs.

This article introduces a new architecture and associated algorithms ideal for implementing the dimensionality reduction of an m-dimensional manifold initially residing in an n-dimensional Euclidean space where n >> m. Motivated by Whitney's embedding theorem, the network is capable of training the identity mapping employing the idea of the graph of a function. In theory, a reduction to a dimension d that retains the differential structure of the original data may be achieved for some d < or = 2m + 1. To implement this network, we propose the idea of a good-projection, which enhances the generalization capabilities of the network, and an adaptive secant basis algorithm to achieve it. The effect of noise on this procedure is also considered. The approach is illustrated with several examples.

Journal Article↗
PubMed1982

Ocular defocus, spurious resolution and contrast reversal.

With the increasing popularity of periodic gratings in vision research, the effects of ocular defocus, such as spurious resolution and the presence of more than one maximum in the contrast - defocus level function, are very important. Optical transfer function theory is used to develop graphs and formulae that can be used to predict the presence of spurious resolution for given levels of defocus and spatial frequency in aberration-free optical system. Geometrical optical approximations are used extensively, as these lead to very simple formulae. These general equations, applying to any optical system, are extended to the particular case of ocular defocus. Formulae are presented that can be used to predict the presence of spurious resolution, in terms of such variables as pupil size and longitudinal focus error. Conditions for the observation of spuriously resolved gratings are also discussed. An example is presented for observing spurious resolution and contrast reversal and this example can be presented as a "pseudo" visual illusion.

Humans↗
PubMed1991

Calculation of control coefficients of metabolic pathways. A flux-oriented graph-theoretic approach.

Within the premises of the flux-oriented theory of Crabtree & Newsholme [(1987) Biochem. J. 247, 113-120], I have used a graph-theoretic approach for calculating the Control Coefficients of metabolic pathways. It is shown that a directed graph representing the control structure of a metabolic pathway can be constructed in a heuristic manner directly from the reaction diagram of the pathway, without the necessity of writing down the governing equations for the Control Coefficients. The Control Coefficients are derived from an analysis of the topology of the directed graph. The graph-theoretic approach also provides a visual framework for analysing the functional relationships of the individual enzymes. The control structures of the following pathways are examined here: (a) a simple unbranched pathway with four enzymes, (b) a simple branched pathway with three enzymes, and (c) a branched pathway with both carbon and energy (ATP) fluxes.

Metabolism↗
PubMed2004

Universal spectral statistics in Wigner-Dyson, chiral, and Andreev star graphs. II. Semiclassical approach.

A semiclassical approach to the universal ergodic spectral statistics in quantum star graphs is presented for all known ten symmetry classes of quantum systems. The approach is based on periodic orbit theory, the exact semiclassical trace formula for star graphs, and on diagrammatic techniques. The appropriate spectral form factors are calculated up to one order beyond the diagonal and self-dual approximations. The results are in accordance with the corresponding random-matrix theories which supports a properly generalized Bohigas-Giannoni-Schmit conjecture.

Journal Article↗
PubMed2006

Random walks for image segmentation.

A novel method is proposed for performing multilabel, interactive image segmentation. Given a small number of pixels with user-defined (or predefined) labels, one can analytically and quickly determine the probability that a random walker starting at each unlabeled pixel will first reach one of the prelabeled pixels. By assigning each pixel to the label for which the greatest probability is calculated, a high-quality image segmentation may be obtained. Theoretical properties of this algorithm are developed along with the corresponding connections to discrete potential theory and electrical circuits. This algorithm is formulated in discrete space (i.e., on a graph) using combinatorial analogues of standard operators and principles from continuous potential theory, allowing it to be applied in arbitrary dimension on arbitrary graphs.

Algorithms↗
PubMed2000

[Some comments on ecological field].

Based on the data of plant ecological field studies, this paper reviewed the conception of ecological field, field eigenfunctions, graphs of ecological field and its application of ecological field theory in explaining plant interactions. It is suggested that the basic character of ecological field is material, and based on the current research level, it is not sure whether ecological field is a kind of specific field different from general physical field. The author gave some comments on the formula and estimation of parameters of basic field function-ecological potential model on ecological field. Both models have their own characteristics and advantages in specific conditions. The author emphasized that ecological field had even more meaning of ecological methodology, and applying ecological field theory in describing the types and processes of plant interactions had three characteristics: quantitative, synthetic and intuitionistic. Field graphing might provide a new way to ecological studies, especially applying the ecological field theory might give an appropriate quantitative explanation for the dynamic process of plant populations (coexistence and interference competition).

Ecology↗