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 271 records · Page 15Linked to original sources
PubMed1981

A new hypothesis on memory - a possible role of local circuits in the formation of the memory trace.

An hypothesis is proposed arguing that local circuits might work as biochemical units involved in synthesis of macromolecules related to the memory processes. Specific sequences in the activation of local circuits should act as a "template" for the synthesis of particular memory molecules, which, in turn, may facilitate the repetition of the original sequences of bioelectrical signals (short-term memory). The resynthesis of the local memory molecules in cell body areas, their flow to terminal areas via axoplasmic transport and their possible passage to other nerve cells via transynaptic transport might be the basis of long term memory. The role of diffuse neuronal systems (e.g. noradrenaline systems) is discussed in the frame of memory recall and consolidation. The suggested hypothesis can be represented in a very effective way by means of the graph theory.

Animals↗
PubMed1993

Computationally efficient cluster representation in molecular sequence megaclassification.

Molecular sequence megaclassification is a technique for automated protein sequence analysis and annotation. Implementation of the method has been limited by the need to store and randomly access a database of all the sequence pair similarities. More than 80,000 protein sequences are now present in the public databases, and the pair similarity data table for the full protein sequence database requires over 1 gigabyte of storage. In this paper we present a computationally efficient representation of groups based on a graph theory approach where sequence clusters are described by a minimal spanning tree of highest scoring similarity pairs. This representation allows a classification of N proteins to be stored in order(N) memory. The use of this minimal spanning tree representation simplifies analysis of groups, the description of group characteristics and the manual correction of artifacts resulting from false hits. The new tree representation also introduces new possibilities for artifact generation in sequence classification. Methods for detecting and removing these artifacts are discussed.

Algorithms↗
PubMed1995

Syntactic structure analysis.

Syntactic structure analysis is a relatively new technique in diagnostic quantitative pathology that, based on the graph theory, can provide quantitative information on tissue architecture. This article gives an introduction to syntactic structure analysis and discusses the potential of syntactic structure analysis in diagnostic quantitative pathology. In addition, some examples of its application in histo- and cytopathology are presented and it is speculated which other applications the user of syntactic structure may find for quantitation of architecture in diagnostic quantitative pathology.

Algorithms↗
PubMed1996

The hippocampus as a cognitive graph.

A theory of cognitive mapping is developed that depends only on accepted properties of hippocampal function, namely, long-term potentiation, the place cell phenomenon, and the associative or recurrent connections made among CA3 pyramidal cells. It is proposed that the distance between the firing fields of connected pairs of CA3 place cells is encoded as synaptic resistance (reciprocal synaptic strength). The encoding occurs because pairs of cells with coincident or overlapping fields will tend to fire together in time, thereby causing a decrease in synaptic resistance via long-term potentiation; in contrast, cells with widely separated fields will tend never to fire together, causing no change or perhaps (via long-term depression) an increase in synaptic resistance. A network whose connection pattern mimics that of CA3 and whose connection weights are proportional to synaptic resistance can be formally treated as a weighted, directed graph. In such a graph, a "node" is assigned to each CA3 cell and two nodes are connected by a "directed edge" if and only if the two corresponding cells are connected by a synapse. Weighted, directed graphs can be searched for an optimal path between any pair of nodes with standard algorithms. Here, we are interested in finding the path along which the sum of the synaptic resistances from one cell to another is minimal. Since each cell is a place cell, such a path also corresponds to a path in two-dimensional space. Our basic finding is that minimizing the sum of the synaptic resistances along a path in neural space yields the shortest (optimal) path in unobstructed two-dimensional space, so long as the connectivity of the network is great enough. In addition to being able to find geodesics in unobstructed space, the same network enables solutions to the "detour" and "shortcut" problems, in which it is necessary to find an optimal path around a newly introduced barrier and to take a shorter path through a hole opened up in a preexisting barrier, respectively. We argue that the ability to solve such problems qualifies the proposed hippocampal object as a cognitive map. Graph theory thus provides a sort of existence proof demonstrating that the hippocampus contains the necessary information to function as a map, in the sense postulated by others (O'Keefe, J., and L. Nadel. 1978. The Hippocampus as a Cognitive Map. Clarendon Press, Oxford, UK). It is also possible that the cognitive mapping functions of the hippocampus are carried out by parallel graph searching algorithms implemented as neural processes. This possibility has the great attraction that the hippocampus could then operate in much the same way to find paths in general problem space; it would only be necessary for pyramidal cells to exhibit a strong nonpositional firing correlate.

Animals↗
PubMed1991

Structural analysis of neural circuits using the theory of directed graphs.

A new approach to analysis of structural properties of biological neural circuits is proposed based on their representation in the form of abstract structures called directed graphs. To exemplify this methodology, structural properties of a biological neural network and randomly wired circuits (RC) were compared. The analyzed biological circuit (BC) represented a sample of 39 neural nuclei which are responsible for the control of the cardiovascular function in higher vertebrates. Initially, direct connections of both circuits were stored in a square matrix format. Then, standard algorithms derived from the theory of directed graphs were applied to analyze the pathways of the circuits according to their length (in number of synapses), degree of connectedness, and structural strength. Thus, the BC was characterized by the presence of short, reciprocal, and unidirectional pathways which presented a high degree of heterogeneity in their strengths. This heterogeneity was mainly due to the existence of a small cluster of reciprocally connected neural nuclei in the circuit that have access, through short pathways, to most of the network. On the other hand, RCs were characterized by the presence of long and mainly reciprocal pathways which showed lower and absolute homogeneous strengths. Through this study the proposed methodology was demonstrated to be a simple and efficient way to store, analyze, and compare basic neuroanatomical information.

Animals↗
PubMed1978

Automatic generation of steady state enzyme rate equation and the associated constraint equations.

A computer algorithm is presented to derive initial velocity rate equation for general enzyme raction mechanisms, including sequential as well as complicated random mechanisms. The method is based on the theory of graph and the theory of prime number. In complicated mechanisms, there are many pathways and hence many cycles. The values of the rate constants are constrained according to the principle of detailed balance: the product of rate constants in the clockwise direction of a cycle must equal to the product of the rate constants in the counter-clockwise direction of the same cycle. An algorithm is presented to derive the appropriate constraint equations. These constraint equations are arranged so that when the rate equation is used for estimating rate constants, the resulting rate constants would satisfy the principle of detailed balance automatically.

Computers↗
PubMed2005

Kinetic theory of random graphs: from paths to cycles.

The structural properties of evolving random graphs are investigated. Treating linking as a dynamic aggregation process, rate equations for the distribution of node to node distances (paths) and of cycles are formulated and solved analytically. At the gelation point, the typical length of paths and cycles, l , scales with the component size k as l approximately k(1/2) . Dynamic and finite-size scaling laws for the behavior at and near the gelation point are obtained. Finite-size scaling laws are verified using numerical simulations.

Journal Article↗
PubMed2005

Recursive neural networks for processing graphs with labelled edges: theory and applications.

In this paper, we introduce a new recursive neural network model able to process directed acyclic graphs with labelled edges. The model uses a state transition function which considers the edge labels and is independent both from the number and the order of the children of each node. The computational capabilities of the new recursive architecture are assessed. Moreover, in order to test the proposed architecture on a practical challenging application, the problem of object detection in images is also addressed. In fact, the localization of target objects is a preliminary step in any recognition system. The proposed technique is general and can be applied in different detection systems, since it does not exploit any a priori knowledge on the particular problem. Some experiments on face detection, carried out on scenes acquired by an indoor camera, are reported, showing very promising results.

Computer Simulation↗
PubMed2000

Periodic-orbit theory of anderson localization on graphs

We present the first quantum system where Anderson localization is completely described within periodic-orbit theory. The model is a quantum graph analogous to an aperiodic Kronig-Penney model in one dimension. The exact expression for the probability to return to an initially localized state is computed in terms of classical trajectories. It saturates to a finite value due to localization, while the diagonal approximation decays diffusively. Our theory is based on the identification of families of isometric orbits. The coherent periodic-orbit sums within these families, and the summation over all families, are performed analytically using advanced combinatorial methods.

Journal Article↗
PubMedDate not supplied

Generating graphs for visual analytics through interactive sketching.

We introduce an interactive graph generator, GreenSketch, designed to facilitate the creation of descriptive graphs required for different visual analytics tasks. The human-centric design approach of GreenSketch enables users to master the creation process without specific training or prior knowledge of graph model theory. The customized user interface encourages users to gain insight into the connection between the compact matrix representation and the topology of a graph layout when they sketch their graphs. Both the human-enforced and machine-generated randomnesses supported by GreenSketch provide the flexibility needed to address the uncertainty factor in many analytical tasks. This paper describes more than two dozen examples that cover a wide variety of graph creations from a single line of nodes to a real-life small-world network that describes a snapshot of telephone connections. While the discussion focuses mainly on the design of GreenSketch, we include a case study that applies the technology in a visual analytics environment and a usability study that evaluates the strengths and weaknesses of our design approach.

Algorithms↗
PubMed2004

Comparative analysis of protein domain organization.

We have developed a set of graph theory-based tools, which we call Comparative Analysis of Protein Domain Organization (CADO), to survey and compare protein domain organizations of different organisms. In the language of CADO, the organization of protein domains in a given organism is shown as a domain graph in which protein domains are represented as vertices, and domain combinations, defined as instances of two domains found in one protein, are represented as edges. CADO provides a new way to analyze and compare whole proteomes, including identifying the consensus and difference of domain organization between organisms. CADO was used to analyze and compare >50 bacterial, archaeal, and eukaryotic genomes. Examples and overviews presented here include the analysis of the modularity of domain graphs and the functional study of domains based on the graph topology. We also report on the results of comparing domain graphs of two organisms, Pyrococcus horikoshii (an extremophile) and Haemophilus influenzae (a parasite with reduced genome) with other organisms. Our comparison provides new insights into the genome organization of these organisms. Finally, we report on the specific domain combinations characterizing the three kingdoms of life, and the kingdom "signature" domain organizations derived from those specific domain combinations.

Animals↗
PubMed2025

CaXML: Chemistry-informed machine learning explains mutual changes between protein conformations and calcium ions in calcium-binding proteins using structural and topological features.

Proteins' flexibility is a feature in communicating changes in cell signaling instigated by binding with secondary messengers, such as calcium ions, associated with the coordination of muscle contraction, neurotransmitter release, and gene expression. When binding with the disordered parts of a protein, calcium ions must balance their charge states with the shape of calcium-binding proteins and their versatile pool of partners depending on the circumstances they transmit. Accurately determining the ionic charges of those ions is essential for understanding their role in such processes. However, it is unclear whether the limited experimental data available can be effectively used to train models to accurately predict the charges of calcium-binding protein variants. Here, we developed a chemistry-informed, machine-learning algorithm that implements a game theoretic approach to explain the output of a machine-learning model without the prerequisite of an excessively large database for high-performance prediction of atomic charges. We used the ab initio electronic structure data representing calcium ions and the structures of the disordered segments of calcium-binding peptides with surrounding water molecules to train several explainable models. Network theory was used to extract the topological features of atomic interactions in the structurally complex data dictated by the coordination chemistry of a calcium ion, a potent indicator of its charge state in protein. Our design created a computational tool of CaXML, which provided a framework of explainable machine learning model to annotate ionic charges of calcium ions in calcium-binding proteins in response to the chemical changes in an environment. Our framework will provide new insights into protein design for engineering functionality based on the limited size of scientific data in a genome space.

Machine Learning↗
PubMed1995

Hydrogen bonding motifs of protein side chains: descriptions of binding of arginine and amide groups.

The modes of hydrogen bonding of arginine, asparagine, and glutamine side chains and of urea have been examined in small-molecule crystal structures in the Cambridge Structural Database and in crystal structures of protein-nucleic acid and protein-protein complexes. Analysis of the hydrogen bonding patterns of each by graph-set theory shows three patterns of rings (R) with one or two hydrogen bond acceptors and two donors and with eight, nine, or six atoms in the ring, designated R2(2)(8), R2(2)(9), and R1(2)(6). These three patterns are found for arginine-like groups and for urea, whereas only the first two patterns R2(2)(8) and R2(2)(9) are found for asparagine- and glutamine-like groups. In each case, the entire system is planar within 0.7 A or less. On the other hand, in macromolecular crystal structures, the hydrogen bonding patterns in protein-nucleic acid complexes between the nucleic acid base and the protein are all R2(2)(9), whereas hydrogen bonding between Watson-Crick-like pairs of nucleic acid bases is R2(2)(8). These two hydrogen bonding arrangements [R2(2)(9)] and R2(2)(8)] are predetermined by the nature of the groups available for hydrogen bonding. The third motif identified, R1(2)(6), involves hydrogen bonds that are less linear than in the other two motifs and is found in proteins.

Adenine↗
PubMed1980

The frequency of cyclic processes in biological multistate systems.

Cyclic processes in stochastic models of macromolecular biological systems are considered. The diagram solution of the model equations (master equation) gives rise to special functions of the rate constants, called the circuit (or one-way cycle) fluxes. As Hill has shown, these functions are the fundamental theoretical components of the operational fluxes, i.e., of the rates of reaction, of transport, of energy conversion, etc. Evidence recently has been found by Monte Carlo simulations that the circuit fluxes can be interpreted as the frequencies of circuit completions. Making use of the theory of graphs, we prove that this physical interpretation of the circuit fluxes is generally valid.

Kinetics↗
PubMed1995

Neuronal growth via hybrid system of self-growing and diffusion based grammar rules: I.

The formation of neuronal networks requires axonal growth towards target neurons. A simple set of grammar rules is introduced to describe axonal growth towards target cells situated both at short and long distances from the growing neuron. Growth for short distances is described by growth following the highest gradient of a chemical compound (which is spread by diffusion from the targets). This approach fails to describe long-distance growth, which is addressed by adopting a graph grammar theory for growing trees. With these rules a flexible tool to draw network of neurons by computer can be developed.

Animals↗
PubMedDate not supplied

A fast method for arranging DNA sequence fragments.

A method is described which allows efficient arrangement of DNA sequence fragments and, based on this arrangement, reconstruction of a complete DNA sequence. The concepts and algorithms used are based on the mathematical theory of graphs. The amount of human interaction required is considerably reduced compared to existing methods. An experiment with a set of 168 fragments yields a DNA sequence of about 5800 bases almost automatically.

Base Sequence↗
PubMed2026

Infra-low-frequency neurofeedback alters EEG network efficiency: exploratory evidence from healthy volunteers.

Infra-Low-Frequency Neurofeedback (ILF-NFB) combines classic frequency-band (FB) and infra-low-frequency (ILF) EEG components in implicit training protocols and is increasingly applied in clinical contexts. Yet, the neurophysiological mechanisms underlying ILF-NFB remain to be further elucidated. In this randomized, sham-controlled and double-blind study, we explored the online impact of a one-session ILF-NFB application on EEG correlates in healthy participants (39 analyzed datasets). Continuous 31-channel EEG was recorded during verum and sham feedback in a double-blind, randomized crossover design. In this exploratory analysis approach, functional connectivity was estimated using the debiased weighted phase-lag index (dwPLI) and analyzed with graph-theoretical measures. The results revealed higher global efficiency during verum compared to sham in the Beta1 band (12-15 Hz), reaching significance in the primary comparison but not surviving Bonferroni correction across the five tested bands; block-wise follow-ups showed a significant verum-sham difference in the first half of the neurofeedback session and a directionally consistent pattern in the second half. The Condition × Block interaction was not significant. No consistent differences were observed in other frequency bands, nor for betweenness centrality. While preliminary, these exploratory results point to possible network-level effects during ILF-NFB and motivate further confirmatory work in extended training protocols and clinical populations.

Humans↗