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

Metabolic PathFinding: inferring relevant pathways in biochemical networks.

Our knowledge of metabolism can be represented as a network comprising several thousands of nodes (compounds and reactions). Several groups applied graph theory to analyse the topological properties of this network and to infer metabolic pathways by path finding. This is, however, not straightforward, with a major problem caused by traversing irrelevant shortcuts through highly connected nodes, which correspond to pool metabolites and co-factors (e.g. H2O, NADP and H+). In this study, we present a web server implementing two simple approaches, which circumvent this problem, thereby improving the relevance of the inferred pathways. In the simplest approach, the shortest path is computed, while filtering out the selection of highly connected compounds. In the second approach, the shortest path is computed on the weighted metabolic graph where each compound is assigned a weight equal to its connectivity in the network. This approach significantly increases the accuracy of the inferred pathways, enabling the correct inference of relatively long pathways (e.g. with as many as eight intermediate reactions). Available options include the calculation of the k-shortest paths between two specified seed nodes (either compounds or reactions). Multiple requests can be submitted in a queue. Results are returned by email, in textual as well as graphical formats (available in http://www.scmbb.ulb.ac.be/pathfinding/).

Algorithms↗
PubMed2006

Payoff-monotonic game dynamics and the maximum clique problem.

Evolutionary game-theoretic models and, in particular, the so-called replicator equations have recently proven to be remarkably effective at approximately solving the maximum clique and related problems. The approach is centered around a classic result from graph theory that formulates the maximum clique problem as a standard (continuous) quadratic program and exploits the dynamical properties of these models, which, under a certain symmetry assumption, possess a Lyapunov function. In this letter, we generalize previous work along these lines in several respects. We introduce a wide family of game-dynamic equations known as payoff-monotonic dynamics, of which replicator dynamics are a special instance, and show that they enjoy precisely the same dynamical properties as standard replicator equations. These properties make any member of this family a potential heuristic for solving standard quadratic programs and, in particular, the maximum clique problem. Extensive simulations, performed on random as well as DIMACS benchmark graphs, show that this class contains dynamics that are considerably faster than and at least as accurate as replicator equations. One problem associated with these models, however, relates to their inability to escape from poor local solutions. To overcome this drawback, we focus on a particular subclass of payoff-monotonic dynamics used to model the evolution of behavior via imitation processes and study the stability of their equilibria when a regularization parameter is allowed to take on negative values. A detailed analysis of these properties suggests a whole class of annealed imitation heuristics for the maximum clique problem, which are based on the idea of varying the parameter during the imitation optimization process in a principled way, so as to avoid unwanted inefficient solutions. Experiments show that the proposed annealing procedure does help to avoid poor local optima by initially driving the dynamics toward promising regions in state space. Furthermore, the models outperform state-of-the-art neural network algorithms for maximum clique, such as mean field annealing, and compare well with powerful continuous-based heuristics.

Journal Article↗
PubMed2003

The conceptual basis of mathematics in cardiology III: linear systems theory and integral transforms.

This is the third in a series of four articles developed for the readers of Coronary Artery Disease. Without language ideas cannot be articulated. What may not be so immediately obvious is that they cannot be formulated either. One of the essential languages of cardiology is mathematics. Unfortunately, medical education does not emphasize, and in fact, often neglects empowering physicians to think mathematically. Reference to statistics, conditional probability, multicompartmental modeling, algebra, calculus and transforms is common but often without provision of genuine conceptual understanding. At the University of Vermont College of Medicine, Professor Bates developed a course designed to address these deficiencies. The course covered mathematical principles pertinent to clinical cardiovascular and pulmonary medicine and research. It focused on fundamental concepts to facilitate formulation and grasp of ideas.This series of four articles was developed to make the material available for a wider audience. The articles will be published sequentially in Coronary Artery Disease. Beginning with fundamental axioms and basic algebraic manipulations they address algebra, function and graph theory, real and complex numbers, calculus and differential equations, mathematical modeling, linear system theory and integral transforms and statistical theory. The principles and concepts they address provide the foundation needed for in-depth study of any of these topics. Perhaps of even more importance, they should empower cardiologists and cardiovascular researchers to utilize the language of mathematics in assessing the phenomena of immediate pertinence to diagnosis, pathophysiology and therapeutics. The presentations are interposed with queries (by Coronary Artery Disease abbreviated as CAD) simulating the nature of interactions that occurred during the course itself. Each article concludes with one or more examples illustrating application of the concepts covered to cardiovascular medicine and biology.

Cardiology↗
PubMed1997

Sequence database searches via de novo peptide sequencing by tandem mass spectrometry.

A method is described for searching protein sequence databases using tandem mass spectra of tryptic peptides. The approach uses a de novo sequencing algorithm to derive a short list of possible sequence candidates which serve as query sequences in a subsequent homology-based database search routine. The sequencing algorithm employs a graph theory approach similar to previously described sequencing programs. In addition, amino acid composition, peptide sequence tags and incomplete or ambiguous Edman sequence data can be used to aid in the sequence determinations. Although sequencing of peptides from tandem mass spectra is possible, one of the frequently encountered difficulties is that several alternative sequences can be deduced from one spectrum. Most of the alternative sequences, however, are sufficiently similar for a homology-based sequence database search to be possible. Unfortunately, the available protein sequence database search algorithms (e.g. Blast or FASTA) require a single unambiguous sequence as input. Here we describe how the publicly available FASTA computer program was modified in order to search protein databases more effectively in spite of the ambiguities intrinsic in de novo peptide sequencing algorithms.

Algorithms↗
PubMed1996

A computerized connectivity approach for analyzing the structural basis of mutagenicity in Salmonella and its relationship with rodent carcinogenicity.

We have applied a new software program, based on graph theory and developed by our group, to predict mutagenicity in Salmonella. The software analyzes, as information in input, the structural formula and the biological activities of a relatively large database of chemicals to generate any possible molecular fragment with size ranging from two to ten nonhydrogen atoms, and detects (as predictors of biological activity) those fragments statistically associated with the biological property investigated. Our previous work used the program to predict carcinogenicity in small rodents. In the current work we applied a modified version of the program, which bases its predictions solely on the most important fragment present in a given molecule, considering as practically negligible the effects of additional less important fragments. For Salmonella mutagenicity we used a database of 551 compounds, and the program achieved a level of predictivity (73.9%) comparable to that obtained by other authors using the Computer Automated Structure Evaluation (CASE) program. We evaluated the relative contributions of biophores and biophobes to overall predictivity: biophores tended to be more important than biophobes, and chemicals containing both biophores and biophobes were more difficult to predict. Many of the molecular fragments identified by the program as being strongly associated with mutagenic activity were similar to the structural alerts identified by the human experts Ashby and Tennant. Our results tend to confirm that structural alerts useful to predict Salmonella mutagenicity are generally not very strong predictors of rodent carcinogenicity. Although the predictivity level achieved for oncogenic activity improved when the program was directly trained with carcinogenicity data, carcinogenicity as a biological endpoint was still more difficult to predict than Salmonella mutagenicity.

Animals↗
PubMed2006

Describing the organization of dominance relationships by dominance-directed tree method.

Methods to describe dominance hierarchies are a key tool in primatology studies. Most current methods are appropriate for analyzing linear and near-linear hierarchies; however, more complex structures are common in primate groups. We propose a method termed "dominance-directed tree." This method is based on graph theory and set theory to analyze dominance relationships in social groups. The method constructs a transitive matrix by imposing transitivity to the dominance matrix and produces a graphical representation of the dominance relationships, which allows an easy visualization of the hierarchical position of the individuals, or subsets of individuals. The method is also able to detect partial and complete hierarchies, and to describe situations in which hierarchical and nonhierarchical principles operate. To illustrate the method, we apply a dominance tree analysis to artificial data and empirical data from a group of Cebus apella.

Animals↗
PubMed2003

FDS: flexible ligand and receptor docking with a continuum solvent model and soft-core energy function.

The docking of flexible small molecule ligands to large flexible protein targets is addressed in this article using a two-stage simulation-based method. The methodology presented is a hybrid approach where the first component is a dock of the ligand to the protein binding site, based on deriving sets of simultaneously satisfied intermolecular hydrogen bonds using graph theory and a recursive distance geometry algorithm. The output structures are reduced in number by cluster analysis based on distance similarities. These structures are submitted to a modified Monte Carlo algorithm using the AMBER-AA molecular mechanics force field with the Generalized Born/Surface Area (GB/SA) continuum model. This solvent model is not only less expensive than an explicit representation, but also yields increased sampling. Sampling is also increased using a rotamer library to direct some of the protein side-chain movements along with large dihedral moves. Finally, a softening function for the nonbonded force field terms is used, enabling the potential energy function to be slowly turned on throughout the course of the simulation. The docking procedure is optimized, and the results are presented for a single complex of the arabinose binding protein. It was found that for a rigid receptor model, the X-ray binding geometry was reproduced and uniquely identified based on the associated potential energy. However, when side-chain flexibility was included, although the X-ray structure was identified, it was one of three possible binding geometries that were energetically indistinguishable. These results suggest that on relaxing the constraint on receptor flexibility, the docking energy hypersurface changes from being funnel-like to rugged. A further 14 complexes were then examined using the optimized protocol. For each complex the docking methodology was tested for a fully flexible ligand, both with and without protein side-chain flexibility. For the rigid protein docking, 13 out of the 15 test cases were able to find the experimental binding mode; this number was reduced to 11 for the flexible protein docking. However, of these 11, in the majority of cases the experimental binding mode was not uniquely identified, but was present in a cluster of low energy structures that were energetically indistinguishable. These results not only support the presence of a rugged docking energy hypersurface, but also suggest that it may be necessary to consider the possibility of more than one binding conformation during ligand optimization.

Algorithms↗
PubMed2004

Automated acquisition and processing of multidimensional image data in confocal in vivo microscopy.

The successful development of visualization techniques for live cell imaging leads to the development of suitable software for the acquisition and processing of multidimensional image data. This report compares several possible approaches to image acquisition and processing in confocal in vivo microscopy and suggests new alternatives to the published methods. Special attention is paid to spinning disk systems based either on a classical Nipkow disk or on the microlens principle. This study shows how to optimize image acquisition process in live cell studies using camera binning feature and how to perform object tracking using a new fast image registration method based on the graph theory.

Algorithms↗
PubMed1992

Selection of representative protein data sets.

The Protein Data Bank currently contains about 600 data sets of three-dimensional protein coordinates determined by X-ray crystallography or NMR. There is considerable redundancy in the data base, as many protein pairs are identical or very similar in sequence. However, statistical analyses of protein sequence-structure relations require nonredundant data. We have developed two algorithms to extract from the data base representative sets of protein chains with maximum coverage and minimum redundancy. The first algorithm focuses on optimizing a particular property of the selected proteins and works by successive selection of proteins from an ordered list and exclusion of all neighbors of each selected protein. The other algorithm aims at maximizing the size of the selected set and works by successive thinning out of clusters of similar proteins. Both algorithms are generally applicable to other data bases in which criteria of similarity can be defined and relate to problems in graph theory. The largest nonredundant set extracted from the current release of the Protein Data Bank has 155 protein chains. In this set, no two proteins have sequence similarity higher than a certain cutoff (30% identical residues for aligned subsequences longer than 80 residues), yet all structurally unique protein families are represented. Periodically updated lists of representative data sets are available by electronic mail from the file server "netserv@embl-heidelberg.de." The selection may be useful in statistical approaches to protein folding as well as in the analysis and documentation of the known spectrum of three-dimensional protein structures.

Algorithms↗
PubMed1994

Structural similarity between binding sites in influenza sialidase and isocitrate dehydrogenase: implications for an alternative approach to rational drug design.

Using searching techniques based on algorithms derived from graph theory, we have established a similarity between a 3-dimensional cluster of side chains implicated in drug binding in influenza sialidase and side chains involved in isocitrate binding in Escherichia coli isocitrate dehydrogenase. The possible implications of the use of such comparative methods in drug design are discussed.

Algorithms↗
PubMed2004

Automatic domain decomposition of proteins by a Gaussian Network Model.

Proteins are often comprised of domains of apparently independent folding units. These domains can be defined in various ways, but one useful definition divides the protein into substructures that seem to move more or less independently. The same methods that allow fairly accurate calculation of motion can be used to help classify these substructures. We show how the Gaussian Network Model (GNM), commonly used for determining motion, can also be adapted to automatically classify domains in proteins. Parallels between this physical network model and graph theory implementation are apparent. The method is applied to a nonredundant set of 55 proteins, and the results are compared to the visual assignments by crystallographers. Apart from decomposing proteins into structural domains, the algorithm can generally be applied to any large macromolecular system to decompose it into motionally decoupled sub-systems.

Algorithms↗
PubMed2005

Evolution and similarity evaluation of protein structures in contact map space.

Prediction of fold from amino acid sequence of a protein has been an active area of research in the past few years, but the limited accuracy of existing techniques emphasizes the need to develop newer approaches to tackle this task. In this study, we use contact map prediction as an intermediate step in fold prediction from sequence. Contact map is a reduced graph-theoretic representation of proteins that models the local and global inter-residue contacts in the structure. We start with a population of random contact maps for the protein sequence and "evolve" the population to a "high-feasibility" configuration using a genetic algorithm. A neural network is employed to assess the feasibility of contact maps based on their 4 physically relevant properties. We also introduce 5 parameters, based on algebraic graph theory and physical considerations, that can be used to judge the structural similarity between proteins through contact maps. To predict the fold of a given amino acid sequence, we predict a contact map that will sufficiently approximate the structure of the corresponding protein. Then we assess the similarity of this contact map with the representative contact map of each fold; the fold that corresponds to the closest match is our predicted fold for the input sequence. We have found that our feasibility measure is able to differentiate between feasible and infeasible contact maps. Further, this novel approach is able to predict the folds from sequences significantly better than a random predictor.

Amino Acid Sequence↗
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↗
PubMed2001

Replication and mutation on neutral networks.

Folding of RNA sequences into secondary structures is viewed as a map that assigns a uniquely defined base pairing pattern to every sequence. The mapping is non-invertible since many sequences fold into the same minimum free energy (secondary) structure or shape. The pre-images of this map, called neutral networks, are uniquely associated with the shapes and vice versa. Random graph theory is used to construct networks in sequence space which are suitable models for neutral networks. The theory of molecular quasispecies has been applied to replication and mutation on single-peak fitness landscapes. This concept is extended by considering evolution on degenerate multi-peak landscapes which originate from neutral networks by assuming that one particular shape is fitter than all the others. On such a single-shape landscape the superior fitness value is assigned to all sequences belonging to the master shape. All other shapes are lumped together and their fitness values are averaged in a way that is reminiscent of mean field theory. Replication and mutation on neutral networks are modeled by phenomenological rate equations as well as by a stochastic birth-and-death model. In analogy to the error threshold in sequence space the phenotypic error threshold separates two scenarios: (i) a stationary (fittest) master shape surrounded by closely related shapes and (ii) populations drifting through shape space by a diffusion-like process. The error classes of the quasispecies model are replaced by distance classes between the master shape and the other structures. Analytical results are derived for single-shape landscapes, in particular, simple expressions are obtained for the mean fraction of master shapes in a population and for phenotypic error thresholds. The analytical results are complemented by data obtained from computer simulation of the underlying stochastic processes. The predictions of the phenomenological approach on the single-shape landscape are very well reproduced by replication and mutation kinetics of tRNA(phe). Simulation of the stochastic process at a resolution of individual distance classes yields data which are in excellent agreement with the results derived from the birth-and-death model.

Base Pairing↗
PubMed1998

The Choice Probabilities of the Latent-Scale Model Satisfy the Size-Independent Model When n Is Small.

Two probabilistic models for subset choices are compared. The first one, due to Marley (1993), was dubbed the latent-scale model by Regenwetter, Marley, and Joe (1996). The second one is Falmagne and Regenwetter's (1996) size-independent model of approval voting. We show that for up to five choice alternatives, the choice probabilities generated by the latent-scale model can be explained also by the size-independent model. The proof uses the König-Hall theorem of graph theory and the characterization of the size-independent model by the approval-voting polytope of Doignon and Regenwetter (1997). The problem remains open for the case with more than five choice alternatives. Copyright 1998 Academic Press.

Journal Article↗
PubMed1992

A fast and efficient method for 2D and 3D molecular shape description.

A new formalism for molecular shape description is described. The formalism, based on considering each molecule as a collection of its 3-atom submolecules, is applied to both the graph theory and geometrical coordinate representations of molecules. The timing results for shape description of several databases indicate that this new method is applicable to large databases. Furthermore, results from clustering a small database show good agreement with clustering results obtained by a distance-matching algorithm.

Algorithms↗
PubMed1985

Distribution of different cell types within the rat thymus in the neonatal period of life.

This study attempted to define reciprocal positions of cell types within the thymus. Random or non-random contacts between specific cell types were analyzed by means of graph theory. For analysis, thymus blocks were sectioned serially and, then, thymus cells were categorized into types, based on morphological criteria. The distribution of individual cell types within the cortex, cortico-medullary zone and medulla was presented in form of a map. In the analysis, three types of epithelial cell, characteristic of each thymus zone, macrophages, Langerhans-like cells and lymphocytes were found in non-random relations to one another. Moreover, characteristic groups of cells associated with one another were also demonstrated.

Animals↗
PubMed1995

Graph-theoretical assignment of secondary structure in multidimensional protein NMR spectra: application to the lac repressor headpiece.

A novel procedure is presented for the automatic identification of secondary structures in proteins from their corresponding NOE data. The method uses a branch of mathematics known as graph theory to identify prescribed NOE connectivity patterns characteristic of the regular secondary structures. Resonance assignment is achieved by connecting these patterns of secondary structure together, thereby matching the connected spin systems to specific segments of the protein sequence. The method known as SERENDIPITY refers to a set of routines developed in a modular fashion, where each program has one or several well-defined tasks. NOE templates for several secondary structure motifs have been developed and the method has been successfully applied to data obtained from NOESY-type spectra. The present report describes the application of the SERENDIPITY protocol to a 3D NOESY-HMQC spectrum of the 15N-labelled lac repressor headpiece protein. The application demonstrates that, under favourable conditions, fully automated identification of secondary structures and semi-automated assignment are feasible.

Amino Acid Sequence↗