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 91 records · Page 5Linked to original sources
PubMed2005

Applying organizational network analysis techniques to study information use in a public health agency.

We are applying organizational network analysis to explore information use in a public health department. The technique is grounded in social science theory, and employs calculations derived from graph theory to generate statistical and graphical models from relational data matrices. For this pilot we will develop network models to characterize how information use in routine work contributes to the agency's performance goals. This is the first step in ongoing work that will extend network analysis with computational methods, to predict the potential effects that improving information use has on the agency's performance.

Humans↗
PubMed1997

Generic properties of combinatory maps: neutral networks of RNA secondary structures.

Random graph theory is used to model and analyse the relationships between sequences and secondary structures of RNA molecules, which are understood as mappings from sequence space into shape space. These maps are non-invertible since there are always many orders of magnitude more sequences than structures. Sequences folding into identical structures form neutral networks. A neutral network is embedded in the set of sequences that are compatible with the given structure. Networks are modeled as graphs and constructed by random choice of vertices from the space of compatible sequences. The theory characterizes neutral networks by the mean fraction of neutral neighbors (lambda). The networks are connected and percolate sequence space if the fraction of neutral nearest neighbors exceeds a threshold value (lambda > lambda *). Below threshold (lambda < lambda *), the networks are partitioned into a largest "giant" component and several smaller components. Structures are classified as "common" or "rare" according to the sizes of their pre-images, i.e. according to the fractions of sequences folding into them. The neutral networks of any pair of two different common structures almost touch each other, and, as expressed by the conjecture of shape space covering sequences folding into almost all common structures, can be found in a small ball of an arbitrary location in sequence space. The results from random graph theory are compared to data obtained by folding large samples of RNA sequences. Differences are explained in terms of specific features of RNA molecular structures.

Base Sequence↗
PubMed1992

Analysis of protein sheet topologies by graph theoretical methods.

In order to find rules for the secondary structure prediction of proteins which describe the (sequentially) long-range interactions in sheet structures methods of applied graph theory were used. The so called beta graph which describes the sheet topology was defined for every protein in the Brookhaven Data Bank containing beta sheets. The resemblance of proteins at that topological level is discussed, and four notations and graphic representations of sheets which describe the sequential and topological neighborhoods of the strands were derived. This description level supports the usage of data structures which allow the implementation of efficient algorithms for the analysis and comparison of beta structures in proteins. A computer program for the representation and retrieval of bibliographic data and beta sheet structures was implemented. Some examples for substructure search illustrate the usefulness of the program. Two graphic catalogues were compiled: one contains all beta graphs of PDB proteins and the other all occurring different greek key descriptions.

Computer Simulation↗
PubMed2004

RAG: RNA-As-Graphs web resource.

BACKGROUND: The proliferation of structural and functional studies of RNA has revealed an increasing range of RNA's structural repertoire. Toward the objective of systematic cataloguing of RNA's structural repertoire, we have recently described the basis of a graphical approach for organizing RNA secondary structures, including existing and hypothetical motifs. DESCRIPTION: We now present an RNA motif database based on graph theory, termed RAG for RNA-As-Graphs, to catalogue and rank all theoretically possible, including existing, candidate and hypothetical, RNA secondary motifs. The candidate motifs are predicted using a clustering algorithm that classifies RNA graphs into RNA-like and non-RNA groups. All RNA motifs are filed according to their graph vertex number (RNA length) and ranked by topological complexity. CONCLUSIONS: RAG's quantitative cataloguing allows facile retrieval of all classes of RNA secondary motifs, assists identification of structural and functional properties of user-supplied RNA sequences, and helps stimulate the search for novel RNAs based on predicted candidate motifs.

Computational Biology↗
PubMed2004

The small world of the cerebral cortex.

While much information is available on the structural connectivity of the cerebral cortex, especially in the primate, the main organizational principles of the connection patterns linking brain areas, columns and individual cells have remained elusive. We attempt to characterize a wide variety of cortical connectivity data sets using a specific set of graph theory methods. We measure global aspects of cortical graphs including the abundance of small structural motifs such as cycles, the degree of local clustering of connections and the average path length. We examine large-scale cortical connection matrices obtained from neuroanatomical data bases, as well as probabilistic connection matrices at the level of small cortical neuronal populations linked by intra-areal and inter-areal connections. All cortical connection matrices examined in this study exhibit "small-world" attributes, characterized by the presence of abundant clustering of connections combined with short average distances between neuronal elements. We discuss the significance of these universal organizational features of cortex in light of functional brain anatomy. Supplementary materials are at www.indiana.edu/~cortex/lab.htm.

Animals↗
PubMed2005

Networks and epidemic models.

Networks and the epidemiology of directly transmitted infectious diseases are fundamentally linked. The foundations of epidemiology and early epidemiological models were based on population wide random-mixing, but in practice each individual has a finite set of contacts to whom they can pass infection; the ensemble of all such contacts forms a 'mixing network'. Knowledge of the structure of the network allows models to compute the epidemic dynamics at the population scale from the individual-level behaviour of infections. Therefore, characteristics of mixing networks-and how these deviate from the random-mixing norm-have become important applied concerns that may enhance the understanding and prediction of epidemic patterns and intervention measures. Here, we review the basis of epidemiological theory (based on random-mixing models) and network theory (based on work from the social sciences and graph theory). We then describe a variety of methods that allow the mixing network, or an approximation to the network, to be ascertained. It is often the case that time and resources limit our ability to accurately find all connections within a network, and hence a generic understanding of the relationship between network structure and disease dynamics is needed. Therefore, we review some of the variety of idealized network types and approximation techniques that have been utilized to elucidate this link. Finally, we look to the future to suggest how the two fields of network theory and epidemiological modelling can deliver an improved understanding of disease dynamics and better public health through effective disease control.

Animals↗
PubMed2002

Beyond blobs in percolation cluster structure: the distribution of 3-blocks at the percolation threshold.

The incipient infinite cluster appearing at the bond percolation threshold can be decomposed into singly connected "links" and multiply connected "blobs." Here we decompose blobs into objects known in graph theory as 3-blocks. A 3-block is a graph that cannot be separated into disconnected subgraphs by cutting the graph at two or fewer vertices. Clusters, blobs, and 3-blocks are special cases of k-blocks with k=1, 2, and 3, respectively. We study bond percolation clusters at the percolation threshold on two-dimensional (2D) square lattices and three-dimensional cubic lattices and, using Monte Carlo simulations, determine the distribution of the sizes of the 3-blocks into which the blobs are decomposed. We find that the 3-blocks have fractal dimension d(3)=1.2+/-0.1 in 2D and 1.15+/-0.1 in 3D. These fractal dimensions are significantly smaller than the fractal dimensions of the blobs, making possible more efficient calculation of percolation properties. Additionally, the closeness of the estimated values for d(3) in 2D and 3D is consistent with the possibility that d(3) is dimension independent. Generalizing the concept of the backbone, we introduce the concept of a "k-bone," which is the set of all points in a percolation system connected to k disjoint terminal points (or sets of disjoint terminal points) by k disjoint paths. We argue that the fractal dimension of a k-bone is equal to the fractal dimension of k-blocks, allowing us to discuss the relation between the fractal dimension of k-blocks and recent work on path crossing probabilities.

Journal Article↗
PubMed2003

Haplotyping as perfect phylogeny: a direct approach.

A full haplotype map of the human genome will prove extremely valuable as it will be used in large-scale screens of populations to associate specific haplotypes with specific complex genetic-influenced diseases. A haplotype map project has been announced by NIH. The biological key to that project is the surprising fact that some human genomic DNA can be partitioned into long blocks where genetic recombination has been rare, leading to strikingly fewer distinct haplotypes in the population than previously expected (Helmuth, 2001; Daly et al., 2001; Stephens et al., 2001; Friss et al., 2001). In this paper we explore the algorithmic implications of the no-recombination in long blocks observation, for the problem of inferring haplotypes in populations. This assumption, together with the standard population-genetic assumption of infinite sites, motivates a model of haplotype evolution where the haplotypes in a population are assumed to evolve along a coalescent, which as a rooted tree is a perfect phylogeny. We consider the following algorithmic problem, called the perfect phylogeny haplotyping problem (PPH), which was introduced by Gusfield (2002) - given n genotypes of length m each, does there exist a set of at most 2n haplotypes such that each genotype is generated by a pair of haplotypes from this set, and such that this set can be derived on a perfect phylogeny? The approach taken by Gusfield (2002) to solve this problem reduces it to established, deep results and algorithms from matroid and graph theory. Although that reduction is quite simple and the resulting algorithm nearly optimal in speed, taken as a whole that approach is quite involved, and in particular, challenging to program. Moreover, anyone wishing to fully establish, by reading existing literature, the correctness of the entire algorithm would need to read several deep and difficult papers in graph and matroid theory. However, as stated by Gusfield (2002), many simplifications are possible and the list of "future work" in Gusfield (2002) began with the task of developing a simpler, more direct, yet still efficient algorithm. This paper accomplishes that goal, for both the rooted and unrooted PPH problems. It establishes a simple, easy-to-program, O(nm(2))-time algorithm that determines whether there is a PPH solution for input genotypes and produces a linear-space data structure to represent all of the solutions. The approach allows complete, self-contained proofs. In addition to algorithmic simplicity, the approach here makes the representation of all solutions more intuitive than in Gusfield (2002), and solves another goal from that paper, namely, to prove a nontrivial upper bound on the number of PPH solutions, showing that that number is vastly smaller than the number of haplotype solutions (each solution being a set of n pairs of haplotypes that can generate the genotypes) when the perfect phylogeny requirement is not imposed.

Algorithms↗
PubMed1989

Distances as degrees of freedom.

Tertiary contact distance information of varying resolution for large biological molecules abounds in the literature. The results provided herein develop a framework by which information of this type can be used to reduce the allowable configuration space of a macromolecule. The approach combines graph theory and distance geometry. Large molecules are represented as simple, undirected graphs, with atoms, or groups, as vertices, and distances between them as edges. It is shown that determination of the exact structure of a molecule in three dimensions only requires the specification of all the distances in a single tetrahedron, and four distances to every other atom. This is 4N-10 distances which is a subset of the total N(N-1)/2 unique distances in a molecule consisting of N atoms. This requirement for only 4N-10 distances has serious implications for distance geometry implementations in which all N(N-1)/2 distances are specified by bounded random numbers. Such distance matrices represent overspecified systems which when solved lead to non-obvious distribution of any error caused by inherent contradictions in the input data. It is also shown that numerous valid subsets of 4N-10 distances can be constructed. It is thus possible to tailor a subset of distances using all known distances as degrees of freedom, and thereby reduce the configuration space of the molecule. Simple algebraic relationships are derived that relate sets of distances, and complicated rotations are avoided. These relationships are used to construct minimum, complete sets of distances necessary to specify the exact structure of the entire molecule in three dimensions from incomplete distance information, and to identify sets of inconsistent distances. The method is illustrated for the flexible structural types present in large ribosomal RNAs: 1.) A five-membered ring; 2.) a chemically bonded chain with its ends in contact (i.e., a hairpin loop); 3.) the spatial orientation of two separate molecules, and; 4.) an RNA helix that can have variation in individual base pairs, giving rise to global deviation from standardized helical forms.

Base Composition↗
PubMed1981

Towards a theory of cell assemblies.

The term cell assembly, first introduced by D. O. Hebb, is defined in the framework of graph theory. This definition leads to some beautiful problems concerning the number and size of cell assemblies in large graphs. Some approaches to solve these problems are presented. In particular, the graphs Kn X Km are constructed that have n . m points, n + m - 2 connections per point, and at least 2n + 2m - 4 assemblies. Several new notions of connectivity in directed graphs are introduced and their relationships are investigated. The insight into these notions and their relationships will be helpful for further construction of graphs with many assemblies and/or high connectivity. The resulting graphs are not only important for the idea of cell assemblies in the content of neurodynamics, they may also find applications in the construction of communication networks and associative memories.

Brain↗
PubMedDate not supplied

Maximum symmetrical split of molecular graphs. Application to organic synthesis design.

Whereas the potential symmetry of a molecule may be a feature of importance in synthesis design, this one is often difficult to detect visually in the structural formula. In the present article, we describe an efficient algorithm for the perception of this molecular property. We have addressed this problem in terms of graph theory and defined it as the Maximum Symmetrical Split of a molecular graph. A solution is obtained by deleting in such a graph a minimum number of edges and vertices so that the resulting subgraph consists of exactly two isomorphic connected components that correspond to a pair of synthetically equivalent synthons. In view to reduce the search space of the problem, we have based our algorithm on CSP techniques. In this study, we have found that the maximum symmetrical split is an original kind of Constraint Satisfaction Problem. The algorithm has been implemented into the RESYN_Assistant system, and its performance has been tested on a set of varied molecules which were the targets of previously published synthetic studies. The results show that potential symmetry is perceived quickly and efficiently by the program. The graphical display of this perception information may help a chemist to design reflexive or highly convergent syntheses.

Journal Article↗
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↗