Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “Network graphs”

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 397 records · Page 22Linked to original sources
PubMed2003

Mixing patterns in networks.

We study assortative mixing in networks, the tendency for vertices in networks to be connected to other vertices that are like (or unlike) them in some way. We consider mixing according to discrete characteristics such as language or race in social networks and scalar characteristics such as age. As a special example of the latter we consider mixing according to vertex degree, i.e., according to the number of connections vertices have to other vertices: do gregarious people tend to associate with other gregarious people? We propose a number of measures of assortative mixing appropriate to the various mixing types, and apply them to a variety of real-world networks, showing that assortative mixing is a pervasive phenomenon found in many networks. We also propose several models of assortatively mixed networks, both analytic ones based on generating function methods, and numerical ones based on Monte Carlo graph generation techniques. We use these models to probe the properties of networks as their level of assortativity is varied. In the particular case of mixing by degree, we find strong variation with assortativity in the connectivity of the network and in the resilience of the network to the removal of vertices.

Journal Article↗
PubMed2003

Geometrical capillary network analysis.

BACKGROUND: Skin microcirculation, especially the superficial network, can be assessed by a computer capillary video microscope system. The study of morphology and dynamics of microcirculation must include all dynamic and cooperative processes between the capillaries. For characterizing capillary ensembles, the statistical and geometrical properties of the network need to be explored. METHODS: The microvaculature of the skin and the microcirculation were investigated by combining videocapillaroscopy (VCP) and image processing techniques based on computational geometry and graph theory. Our goal was to characterize the capillary network in noisy pictures of the scalp. Different geometric methods were developed, based on proximity parameters (distance and surface) in order to circumscribe and construct this network. RESULTS: By studying the distribution of these parameters, extreme values or outliers, which usually correspond to artifact subregions in the pictures could be eliminated. Different algorithms were developed and has been implemented in an image processing software (Capilab Toolbox). CONCLUSION: This computerized system is capable of real-time processings, increasing the quality of videocapillaroscope images and minimizing the disturbance of artifacts. The algorithms presented here are easy to implement and can process any kind of images of the skin, even in the scalp. In association with an example-based detection system, this method can be generalized to other stimuli in the same conditions.

Capillaries↗
PubMed2003

Computerized diagnostic decision support system for the classification of preinvasive cervical squamous lesions.

Previous studies have revealed considerable interobserver and intraobserver variation in the histological classification of preinvasive cervical squamous lesions. The aim of the present study was to develop a decision support system (DSS) for the histological interpretation of these lesions. Knowledge and uncertainty were represented in the form of a Bayesian belief network that permitted the storage of diagnostic knowledge and, for a given case, the collection of evidence in a cumulative manner that provided a final probability for the possible diagnostic outcomes. The network comprised 8 diagnostic histological features (evidence nodes) that were each independently linked to the diagnosis (decision node) by a conditional probability matrix. Diagnostic outcomes comprised normal; koilocytosis; and cervical intraepithelial neoplasia (CIN) I, CIN II, and CIN III. For each evidence feature, a set of images was recorded that represented the full spectrum of change for that feature. The system was designed to be interactive in that the histopathologist was prompted to enter evidence into the network via a specifically designed graphical user interface (i-Path Diagnostics, Belfast, Northern Ireland). Membership functions were used to derive the relative likelihoods for the alternative feature outcomes, the likelihood vector was entered into the network, and the updated diagnostic belief was computed for the diagnostic outcomes and displayed. A cumulative probability graph was generated throughout the diagnostic process and presented on screen. The network was tested on 50 cervical colposcopic biopsy specimens, comprising 10 cases each of normal, koilocytosis, CIN I, CIN II, and CIN III. These had been preselected by a consultant gynecological pathologist. Using conventional morphological assessment, the cases were classified on 2 separate occasions by 2 consultant and 2 junior pathologists. The cases were also then classified using the DSS on 2 occasions by the 4 pathologists and by 2 medical students with no experience in cervical histology. Interobserver and intraobserver agreement using morphology and using the DSS was calculated with kappa statistics. Intraobserver reproducibility using conventional unaided diagnosis was reasonably good (kappa range, 0.688 to 0.861), but interobserver agreement was poor (kappa range, 0.347 to 0.747). Using the DSS improved overall reproducibility between individuals. Using the DSS, however, did not enhance the diagnostic performance of junior pathologists when comparing their DSS-based diagnosis against an experienced consultant. However, the generation of a cumulative probability graph also allowed a comparison of individual performance, how individual features were assessed in the same case, and how this contributed to diagnostic disagreement between individuals. Diagnostic features such as nuclear pleomorphism were shown to be particularly problematic and poorly reproducible. DSSs such as this therefore not only have a role to play in enhancing decision making but also in the study of diagnostic protocol, education, self-assessment, and quality control.

Bayes Theorem↗
PubMed2006

PIANA: protein interactions and network analysis.

UNLABELLED: We present a software framework and tool called Protein Interactions And Network Analysis (PIANA) that facilitates working with protein interaction networks by (1) integrating data from multiple sources, (2) providing a library that handles graph-related tasks and (3) automating the analysis of protein-protein interaction networks. PIANA can also be used as a stand-alone application to create protein interaction networks and perform tasks such as predicting protein interactions and helping to identify spots in a 2D electrophoresis gel. AVAILABILITY: PIANA is under the GNU GPL. Source code, database and detailed documentation may be freely downloaded from http://sbi.imim.es/piana.

Computer Graphics↗
PubMed2005

Evolutionary dynamics on graphs.

Evolutionary dynamics have been traditionally studied in the context of homogeneous or spatially extended populations. Here we generalize population structure by arranging individuals on a graph. Each vertex represents an individual. The weighted edges denote reproductive rates which govern how often individuals place offspring into adjacent vertices. The homogeneous population, described by the Moran process, is the special case of a fully connected graph with evenly weighted edges. Spatial structures are described by graphs where vertices are connected with their nearest neighbours. We also explore evolution on random and scale-free networks. We determine the fixation probability of mutants, and characterize those graphs for which fixation behaviour is identical to that of a homogeneous population. Furthermore, some graphs act as suppressors and others as amplifiers of selection. It is even possible to find graphs that guarantee the fixation of any advantageous mutant. We also study frequency-dependent selection and show that the outcome of evolutionary games can depend entirely on the structure of the underlying graph. Evolutionary graph theory has many fascinating applications ranging from ecology to multi-cellular organization and economics.

Biological Evolution↗
PubMed2004

An improved transiently chaotic neural network for the maximum independent set problem.

By analyzing the dynamic behaviors of the transiently chaotic neural network and greedy heuristic for the maximum independent set (MIS) problem, we present an improved transiently chaotic neural network for the MIS problem in this paper. Extensive simulations are performed and the results show that this proposed transiently chaotic neural network can yield better solutions to p-random graphs than other existing algorithms. The efficiency of the new model is also confirmed by the results on the complement graphs of some DIMACS clique instances in the second DIMACS challenge. Moreover, the improved model uses fewer steps to converge to stable state in comparison with the original transiently chaotic neural network.

Algorithms↗
PubMed1996

New approaches in molecular structure prediction.

In the past years, much effort has been put on the development of new methodologies and algorithms for the prediction of protein secondary and tertiary structures from (sequence) data; this is reviewed in detail. New approaches for these predictions such as neural network methods, genetic algorithms, machine learning, and graph theoretical methods are discussed. Secondary structure prediction algorithms were improved mostly by considering families of related proteins; however, for the reliable tertiary structure modeling of proteins, knowledge-based techniques are still preferred. Methods and examples with more or less successful results are described. Also, programs and parameterizations for energy minimisations, molecular dynamics, and electrostatic interactions have been improved, especially with respect to their former limits of applicability. Other topics discussed in this review include the use of traditional and on-line databases, the docking problem and surface properties of biomolecules, packing of protein cores, de novo design and protein engineering, prediction of membrane protein structures, the verification and reliability of model structures, and progress made with currently available software and computer hardware. In summary, the prediction of the structure, function, and other properties of a protein is still possible only within limits, but these limits continue to be moved.

Chemical Phenomena↗
PubMed1999

Microspatial genetic structure in the land snail helix aspersa (Gastropoda: helicidae)

The microspatial genetic structure of allele frequencies at seven isozyme loci was examined for 15 populations of the land snail Helix aspersa sampled in a village from Brittany (north-western France). Spatial heterogeneity of allele frequencies was highly significant (P < 0.001). Fixation indices reflected nonrandom mating within neighbourhoods and a slight but consistent differentiation between colonies (FST=0.044; P < 0.01). Analyses of gene flow or genetic distances failed to reveal a significant relationship with geographical distance, probably because of the complexity of environmental heterogeneity. However, matrix comparisons between genetic distances and connectivity networks among adjacent colonies (Gabriel-connected graph) yielded a significant correlation in every case, indicating a 'step-by-step' relationship between neighbouring localities. Moreover, most of the allozymes were spatially structured and showed (i) a gradual isolation of colonies with increasing geographical distances, and (ii), for some correlogram profiles, a circular gradient illustrating a multidirectional colonization of the village. The probable existence of disperser individuals allowed us to suggest a metapopulation model which would explain the maintenance of such animals in fragmented habitats where anthropogenic disturbances and extinction/recolonization events are commonly observed.

Journal Article↗
PubMed2002

An eigenvector method for estimating item parameters of the dichotomous and polytomous Rasch models.

The purpose of this paper is to describe a technique for obtaining item parameters of the Rasch model, a technique in which the item parameters are extracted from the eigenvector of a matrix derived from comparisons between pairs of items. The technique can be applied to both dichotomous and polytomous data. In application to a previously published data set, it is shown that the technique provides item parameter estimates comparable to those produced by joint maximum likelihood estimation, and for the most difficult items, the technique appears to produce superior estimates. This method has several advantages. It easily accommodates missing data, and makes transparent the basis for item parameter estimation in the presence of missing data. Furthermore, the method provides a link to other methods in the social sciences and, in particular, provides the framework for application of graph theory to the analysis of assessment networks. Finally, it exploits several characteristics that are unique to the Rasch model.

Algorithms↗
PubMedDate not supplied

Theorems speaking for the asymmetry of all animal brains.

In random graph theory it has been proved that with the increasing size of a graph, the proportion of the non-symmetric graphs increases and this class becomes the dominant one while the number of symmetric cases turns to be 'negligible'. Thus the asymmetry (AS) is the generic property. Since nervous systems are representable by graphs or better with special digraphs, the networks, it follows that the brains are asymmetric in a strong sense according to which all cells are distinguishable from each other alone by their internal connections. Such a consequence holds perfectly only if a random evolution or generation of neural networks is supposed. Thus apparent symmetries have to come from heavily controlled (i.e. non random) ontogenetic processes. At the present time the possible total cellular heterogeneity of the various nervous systems has still unclear functional implications. In small nervous systems the odd number of neurons alone is neither a sufficient nor a necessary condition of the asymmetry in the outlined sense.

Animals↗
PubMed1993

Developing a standard data structure for medical language--the SNOMED proposal.

The Systematized Nomenclature of Medicine, Third Edition, SNOMED International, is a comprehensive structured nomenclature of human and veterinary medicine, the terms of which are detailed, fine grained and semantically typed. Terms are assigned to eleven independent modules (fields), each of which is systematized. Terms may be linked to on another to represent complex entities or manifestations or alternately complex terms dissected into their elemental parts. Terms are illustrated utilizing a frame representation. Efforts are in progress to build both a conceptual graph and a frame-based semantic network encompassing each SNOMED term, effectively building a knowledge base. In this way, the knowledge contained in each alphanumeric representation is made explicit. SNOMED is a linked data structure capable of faithfully representing the activities, observations and diagnoses found in the medical record in a computer processable form.

Animals↗
PubMed2006

A topology-constrained distance network algorithm for protein structure determination from NOESY data.

This article formulates the multidimensional nuclear Overhauser effect spectroscopy (NOESY) interpretation problem using graph theory and presents a novel, bottom-up, topology-constrained distance network analysis algorithm for NOESY cross peak interpretation using assigned resonances. AutoStructure is a software suite that implements this topology-constrained distance network analysis algorithm and iteratively generates structures using the three-dimensional (3D) protein structure calculation programs XPLOR/CNS or DYANA. The minimum input for AutoStructure includes the amino acid sequence, a list of resonance assignments, and lists of 2D, 3D, and/or 4D-NOESY cross peaks. AutoStructure can also analyze homodimeric proteins when X-filtered NOESY experiments are available. The quality of input data and final 3D structures is evaluated using recall, precision, and F-measure (RPF) scores, a statistical measure of goodness of fit with the input data. AutoStructure has been tested on three protein NMR data sets for which high-quality structures have previously been solved by an expert, and yields comparable high-quality distance constraint lists and 3D protein structures in hours. We also compare several protein structures determined using AutoStructure with corresponding homologous proteins determined with other independent methods. The program has been used in more than two dozen protein structure determinations, several of which have already been published.

Algorithms↗
PubMed2005

Load distribution in weighted complex networks.

We study the load distribution in weighted networks by measuring the effective number of optimal paths passing through a given vertex. The optimal path, along which the total cost is minimum, crucially depends on the cost distribution function p(c) (c) . In the strong disorder limit, where p(c) (c) approximately c(-1) , the load distribution follows a power law both in the Erdös-Rényi (ER) random graphs and in the scale-free (SF) networks, and its characteristics are determined by the structure of the minimum spanning tree. The distribution of loads at vertices with a given vertex degree also follows the SF nature similar to the whole load distribution, implying that the global transport property is not correlated to the local structural information. Finally, we measure the effect of disorder by the correlation coefficient between vertex degree and load, finding that it is larger for ER networks than for SF networks.

Journal Article↗
PubMed2002

Generalized Taylor-Aris dispersion in discrete spatially periodic networks: microfluidic applications.

A theory is presented for the lumped parameter, convective-diffusive transport of individual, noninteracting Brownian solute particles ("macromolecules") moving within spatially periodic, solvent-filled networks--the latter representing models of chip-based microfluidic chromatographic separation devices, as well as porous media. Using graph-theoretical techniques, the composite medium is conceptually decomposed into a network of channels (the edges) through which the solute is transported by a combination of molecular diffusion and either "piggyback" entrainment within a flowing solvent or an externally applied force field acting upon the solute molecules. A probabilistic choice of egress channel for a solute particle exiting the intersection (vertex) of the channels is furnished by an imperfect mixing model. A spatially periodic, Taylor-Aris-like "method-of-moments" scheme is applied to this transport model, leading to discrete matrix equations for computing the network-scale particle velocity vector U(*) and dispersivity dyadic D(*) in terms of the prescribed microscale transport parameters and network geometry characterizing the basic unit cell of which the spatially periodic device is comprised. The ensuing algebraic equations governing the vertex-based, discrete unit-cell "fields" P(0)(infinity)(i) and B(i) (i=1,2,...,n), whose paradigmatic summations yield U(*) and D(*), constitute discrete analogs of classical continuous macrotransport phenomenological parameters, P(0)(infinity)(r) and B(r), with r a continuous position vector defined within the unit cell. The ease with which these discrete calculations can be performed for complex networks renders feasible parametric studies of potential microfluidic chip designs, particularly those pertinent to biomolecular separation schemes. Application of this discrete theory to the dispersion analysis of pressure-driven flow in spatially periodic serpentine microchannels is shown to accord with existing results previously derived using classical continuous macrotransport theory.

Journal Article↗
PubMed2004

Complexity analysis of yeast proteome network.

Topological and compositional complexity of protein-protein networks is assessed in a variety of ways making use of graph theory and information theory. The methodology used is borrowed from mathematical chemistry and includes complexity descriptors such as substructure count, overall connectivity, walk count, and information on various vertex distributions. The approach is applied to the (incomplete) proteome of Saccharomyces cerevisiae containing 232 protein complexes of a total of 1,440 proteins. The proteome network and each of its nine functional subsets of protein complexes are disconnected graphs, containing a number of noninteracting species and a major component. A weighted edge between two vertices in these graphs stands for the number of shared proteins between the respective complexes. The major component is a highly connected, 'small-world' network, in which the average vertex distance between protein complexes does not exceed 2.2 (2.4 for the entire proteome), whereas the maximum distance does not exceed 4 (or 5 for the proteome). The vertex degree distribution in the major proteome component with 199 complexes follows the power law P(k) approximately k(-gamma), with gamma approximately = 1.7. The analysis of the functional organization of the yeast proteome has shown that, for any pair of biological functions, there always exist many proteins that can perform both functions. The potential application of the quantitative proteome descriptors discussed includes quantitative relationships between the structure and biological action of dynamic protein complexes in changing environment, identification of targets for markers/drugs, as well as system analysis and comparative studies of proteomes.

Fungal Proteins↗
PubMed1992

Graph-grammar productions for the modeling of medical dilemmas.

We introduce graph-grammar production rules, which can guide physicians to construct models for normative decision making. A physician describes a medical decision problem using standard terminology, and the graph-grammar system matches a graph-manipulation rule to each of the standard terms. With minimal help from the physician, these graph-manipulation rules can construct an appropriate Bayesian probabilistic network. The physician can then assess the necessary probabilities and utilities to arrive at a rational decision. The grammar relies on prototypical forms that we have observed in models of medical dilemmas. We have found graph grammars to be a concise and expressive formalism for describing prototypical forms, and we believe such grammars can greatly facilitate the modeling of medical dilemmas and medical plans.

Bayes Theorem↗
PubMed1984

[Hemo- and lymphomicrocirculatory bed of the broad ligament of the uterus in the presence of collateral circulation].

Structural adaptation of the vascular bed in the broad ligament of the dog uterus has been studied at various time of the experimental phlebohypertension. Restitution of the circulation after the posterior vena cava occulsion occurs phasically. The venous collateralies are not formed at one time and it is connected with the venous pressure level in the inferiocaval system and with some changes in the construction of the microcirculatory bed. Basing on the morphometry data, a general equation has been derived which reflects dynamics of the microangiological parameters and demonstrates unidirectionness of the adaptive reactions in the vascular bed at the disturbed venous circulation. Using principles of the system-structural analysis and the mathematical graph theory, we consider the microcirculatory system of the broad ligament of the uterus as a graph-system and study the reorganization of the microcirculatory network at a venous congestion. Realization of the compensatory possibilities is reached in the microcirculatory bed by a changed relationships in the number of the intervascular connections. The latter are estimated according to the graph-schemes of the microvascular bed. Morphokinetics of the connections between the vessels is characterized by widening or narrowing the borders of the "adaptive norm" and by changing the microangioarchitectonics. At the same time, there is noted formation of specialized microhemoangioconstructions. Morphofunctional state of the lymphatic system is connected with reorganization of the angioarchitectonics. This is certain manifestation of the law of the lymphatic and blood beds "synergism". Thus, the structural changes of the vascular bed are aimed to support a certain hemodynamic level.

Animals↗
PubMed2006

Disturbed functional connectivity in brain tumour patients: evaluation by graph analysis of synchronization matrices.

OBJECTIVE: Cerebral functions are based on the functional interactions between multiple distinct specialized regions of the brain. Functional interactions require anatomical connections as well as the synchronization of brain oscillations. The present work aims at evaluating the impact of brain tumours on spatial patterns of functional connectivity of the brain measured at rest by MEG. METHODS: We analyzed the statistical dependency (by computing the synchronization likelihood (SL, a measure of generalized synchronization)) between MEG signals at rest, in 17 patients with a brain tumour and in 15 healthy controls. Following an approach that derives from graph theory, we also analyzed the architectural properties of the networks by computing two parameters from the SL matrix, the cluster coefficient C and the characteristic path length L. RESULTS: Alterations in synchronization levels were found in the patients and were not focal but involved intra-hemispheric connectivity. Effects were different considering the frequencies sub-bands, predominating in a decrease in high frequencies bands for long-distance connections and an increase in slower bands for local connectivity. In addition, graph analysis reveals changes in the normal "small-world" network architecture in addition to changes in synchronization levels with some differences according to the studied frequency sub-bands. CONCLUSIONS: Brain tumours alter the functional connectivity and the "network" architecture of the brain. These alterations are not focal and effects are different considering the frequencies sub-bands. SIGNIFICANCE: These neurophysiological changes may contribute to the cognitive alterations observed in patients with brain tumours.

Adult↗