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 109 records · Page 6Linked to original sources
PubMedDate not supplied

Exhaustive generation of organic isomers. 6. Stereoisomers having isolated and spiro cycles and new extended N_tuples.

A new stereoisomer generation system named CAMGEC2 for generation of stereoisomers containing isolated and spiro cycles with one or more descriptors among R, S, Z, E, M, and P is developed using Graph Theory. It includes new approaches for symmetry analysis, cycle detection processes in molecular graphs in a modular way, and also an extension of the N_tuple format for linear representation of molecular graphs that keeps graph topographical information.

Journal Article↗
PubMed2003

A graph-theoretic approach to the partition of individuals into full-sib families.

We present an algorithm to partition a single generation of individuals into full-sib families using single-locus co-dominant marker data. Pairwise likelihood ratios are used to create a graph that represents the full-sib relationships within the data set. Connected-component and minimum-cut algorithms from the graph theory are then employed to find the full-sib families within the graph. The results of a large-scale simulation study show that the algorithm is able to produce accurate partitions when applied to data sets with eight or more loci. Although the algorithm performs best when the distribution of allele frequencies and family sizes in a data set is uniform, the inclusion of more loci or alleles per locus allows accurate partitions to be created from data sets in which these distributions are highly skewed.

Algorithms↗
PubMed2005

ECgene: genome-based EST clustering and gene modeling for alternative splicing.

With the availability of the human genome map and fast algorithms for sequence alignment, genome-based EST clustering became a viable method for gene modeling. We developed a novel gene-modeling method, ECgene (Gene modeling by EST Clustering), which combines genome-based EST clustering and the transcript assembly procedure in a coherent and consistent fashion. Specifically, ECgene takes alternative splicing events into consideration. The position of splice sites (i.e., exon-intron boundaries) in the genome map is utilized as the critical information in the whole procedure. Sequences that share any splice sites are grouped together to define an EST cluster in a manner similar to that of the genome-based version of the UniGene algorithm. Transcript assembly is achieved using graph theory that represents the exon connectivity in each cluster as a directed acyclic graph (DAG). Distinct paths along exons correspond to possible gene models encompassing all alternative splicing events. EST sequences in each cluster are subclustered further according to the compatibility with gene structure of each splice variant, and they can be regarded as clone evidence for the corresponding isoform. The reliability of each isoform is assessed from the nature of cluster members and from the minimum number of clones required to reconstruct all exons in the transcript.

Algorithms↗
PubMed1979

A graph theoretic approach to the development of minimal phylogenetic trees.

The problem of determining the minimal phylogenetic tree is discussed in relation to graph theory. It is shown that this problem is an example of the Steiner problem in graphs which is to connect a set of points by a minimal length network where new points can be added. There is no reported method of solving realistically-sized Steiner problems in reasonable computing time. A heuristic method of approaching the phylogenetic problem is presented, together with a worked example with 7 mammalian cytochrome c sequences. It is shown in this case that the method develops a phylogenetic tree that has the smallest possible number of amino acid replacements. The potential and limitations of the method are discussed. It is stressed that objective methods must be used for comparing different trees. In particular it should be determined how close a given tree is to a mathematically determined lower bound. A theorem is proved which is used to establish a lower bound on the lenghtof any tree and if a tree is found with a length equal to the lower bound, then no shorter tree can exist.

Mathematics↗
PubMed1993

[A method of analysing the reasoning applied in nursing in neuroscience].

It is a preliminary study testing the applicability of a method for knowledge characterization based on graphs theory. 11 (eleven) nurses working in a medical surgical intensive care unit including neurological patients constructed graphs to explain the diagnostic process. The results show that: the knowledge structure is in a developing stage; there is agreement regarding to diagnosis formulation and the data base on which it is founded is diversified and link to a specified form of related causes. The method demonstrated to be feasible and should be reapplied on a larger population.

Adult↗
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↗
PubMed2002

PseudoViewer: automatic visualization of RNA pseudoknots.

MOTIVATION: Several algorithms have been developed for drawing RNA secondary structures, however none of these can be used to draw RNA pseudoknot structures. In the sense of graph theory, a drawing of RNA secondary structures is a tree, whereas a drawing of RNA pseudoknots is a graph with inner cycles within a pseudoknot as well as possible outer cycles formed between a pseudoknot and other structural elements. Thus, RNA pseudoknots are more difficult to visualize than RNA secondary structures. Since no automatic method for drawing RNA pseudoknots exists, visualizing RNA pseudoknots relies on significant amount of manual work and does not yield satisfactory results. The task of visualizing RNA pseudoknots by hand becomes more challenging as the size and complexity of the RNA pseudoknots increase. RESULTS: We have developed a new representation and an algorithm for drawing H-type pseudoknots with RNA secondary structures. Compared to existing representations of H-type pseudoknots, the new representation ensures uniform and clear drawings with no edge crossing for any H-type pseudoknots. To the best of our knowledge, this is the first algorithm for automatically drawing RNA pseudoknots with RNA secondary structures. The algorithm has been implemented in a Java program, which can be executed on any computing system. Experimental results demonstrate that the algorithm generates an aesthetically pleasing drawing of all H-type pseudoknots. The results have also shown that the drawing has high readability, enabling the user to quickly and easily recognize the whole RNA structure as well as the pseudoknots themselves.

Algorithms↗
PubMed1985

Quantum chemical and other theoretical studies of carcinogens, their metabolic activation and attack on DNA constituents.

We have carried out a variety of different types of studies on carcinogens: ab-initio quantum chemical, including generation of electrostatic molecular potential contour (EMPC) maps and graph theoretical generation of polycyclic aromatic hydrocarbon (PAH) structures and characterization of the "carcinogenic" bay regions. Polycyclic aromatic hydrocarbon (PAH) carcinogens are activated metabolically from precarcinogen (PAH's) through proximate carcinogens (PAH epoxides and dihydrodiols) to ultimate carcinogens (PAH dihydrodiolepoxides) which then attack DNA constituents. We carried out ab-initio MODPOT/VRDDO/MERGE calculations on a variety of these molecules using our own ab-initio programs which incorporate as options a number of desirable options for ab-initio calculation on large molecules. From these electronic wave functions, we generated electrostatic molecular potential contour (EMPC) maps around these molecules. These EMPC maps indicated predictively the positions at which epoxides would form and the propensity and geometrical preference to form dihydrodiols and dihydrodiolepoxides. We performed spin and symmetry analyses for attack of O adding across C = C bonds or inserting in C-H or N-H bonds. We also carried out ab-initio calculations for attack of ultimate carcinogens on DNA constituents. Using graph theory we generated all possible structures for any arbitrary numbers of aromatic rings and also set up a graph theoretical characterization of the "carcinogenic" bay region. Most recently, we have incorporated this into a computer program for global prediction of toxicity.

Biotransformation↗
PubMed2000

Backbone cluster identification in proteins by a graph theoretical method.

A graph theoretical algorithm has been developed to identify backbone clusters of residues in proteins. The identified clusters show protein sites with the highest degree of interactions. An adjacency matrix is constructed from the non-bonded connectivity information in proteins. The diagonalization of such a matrix yields eigenvalues and eigenvectors, which contain the information on clusters. In graph theory, distinct clusters can be obtained from the second lowest eigenvector components of the matrix. However, in an interconnected graph, all the points appear as one single cluster. We have developed a method of identifying highly interacting centers (clusters) in proteins by truncating the vector components of high eigenvalues. This paper presents in detail the method adopted for identifying backbone clusters and the application of the algorithm to families of proteins like RNase-A and globin. The objective of this study was to show the efficiency of the algorithm as well as to detect conserved or similar backbone packing regions in a particular protein family. Three clusters in topologically similar regions in the case of the RNase-A family and three clusters around the porphyrin ring in the globin family were observed. The predicted clusters are consistent with the features of the family of proteins such as the topology and packing density. The method can be applied to problems such as identification of domains and recognition of structural similarities in proteins.

Algorithms↗
PubMed1994

Automating the identification and analysis of protein beta-barrels.

beta-Barrels are widespread and well-studied features of a great many protein structures. In this paper an unsupervised method for the detection of beta-barrels is developed based on techniques from graph theory. The hydrogen bonded connectivity of beta-sheets is derived using standard pattern recognition techniques and expressed as a graph. Barrels correspond to topological rings in these connectivity graphs and can thus be identified using ring perception algorithms. Following from this, the characteristic topological structure of a barrel can be expressed using a novel form of reduced nomenclature that counts sequence separations between successive members of the ring set. These techniques are tested by applying them to the detection of barrels in a non-redundant subset of the Brookhaven database. Results indicate that topological rings do seem to correspond uniquely to beta-barrels and that the technique, as implemented, finds the majority of barrels present in the dataset.

Algorithms↗
PubMed1998

A graph-theoretic algorithm for comparative modeling of protein structure.

The interconnected nature of interactions in protein structures appears to be the major hurdle in preventing the construction of accurate comparative models. We present an algorithm that uses graph theory to handle this problem. Each possible conformation of a residue in an amino acid sequence is represented using the notion of a node in a graph. Each node is given a weight based on the degree of the interaction between its side-chain atoms and the local main-chain atoms. Edges are then drawn between pairs of residue conformations/nodes that are consistent with each other (i.e. clash-free and satisfying geometrical constraints). The edges are weighted based on the interactions between the atoms of the two nodes. Once the entire graph is constructed, all the maximal sets of completely connected nodes (cliques) are found using a clique-finding algorithm. The cliques with the best weights represent the optimal combinations of the various main-chain and side-chain possibilities, taking the respective environments into account. The algorithm is used in a comparative modeling scenario to build side-chains, regions of main chain, and mix and match between different homologs in a context-sensitive manner. The predictive power of this method is assessed by applying it to cases where the experimental structure is not known in advance.

Algorithms↗
PubMed2006

A quantitative analysis of secondary RNA structure using domination based parameters on trees.

BACKGROUND: It has become increasingly apparent that a comprehensive database of RNA motifs is essential in order to achieve new goals in genomic and proteomic research. Secondary RNA structures have frequently been represented by various modeling methods as graph-theoretic trees. Using graph theory as a modeling tool allows the vast resources of graphical invariants to be utilized to numerically identify secondary RNA motifs. The domination number of a graph is a graphical invariant that is sensitive to even a slight change in the structure of a tree. The invariants selected in this study are variations of the domination number of a graph. These graphical invariants are partitioned into two classes, and we define two parameters based on each of these classes. These parameters are calculated for all small order trees and a statistical analysis of the resulting data is conducted to determine if the values of these parameters can be utilized to identify which trees of orders seven and eight are RNA-like in structure. RESULTS: The statistical analysis shows that the domination based parameters correctly distinguish between the trees that represent native structures and those that are not likely candidates to represent RNA. Some of the trees previously identified as candidate structures are found to be "very" RNA like, while others are not, thereby refining the space of structures likely to be found as representing secondary RNA structure. CONCLUSION: Search algorithms are available that mine nucleotide sequence databases. However, the number of motifs identified can be quite large, making a further search for similar motif computationally difficult. Much of the work in the bioinformatics arena is toward the development of better algorithms to address the computational problem. This work, on the other hand, uses mathematical descriptors to more clearly characterize the RNA motifs and thereby reduce the corresponding search space. These preliminary findings demonstrate that graph-theoretic quantifiers utilized in fields such as computer network design hold significant promise as an added tool for genomics and proteomics.

Algorithms↗
PubMed2001

Protein flexibility and dynamics using constraint theory.

A new approach is presented for determining the rigid regions in proteins and the flexible joints between them. The short-range forces in proteins are modeled as constraints and we use a recently developed formalism from graph theory to analyze flexibility in the bond network. Forces included in the analysis are the covalent bond-stretching and bond-bending forces, salt bridges, and hydrogen bonds. We use a local function to associate an energy with individual hydrogen bonds, which then can be included or excluded depending on the bond strength. Colored maps of the rigid and flexible regions provide a direct visualization of where the motion of the protein can take place, consistent with these distance constraints. We also define a flexibility index that quantifies the local density of flexible or floppy modes, in terms of the dihedral angles that remain free to rotate in each flexible region. A negative flexibility index provides a measure of the density of redundant bonds in rigid regions. A new application of this approach is to simulate the maximal range of possible motions of the flexible regions by introducing Monte Carlo changes in the free dihedral angles, subject to the distance constraints. This is done using a method that maintains closure of the rings formed by covalent and hydrogen bonds in the flexible parts of the protein, and van der Waals overlaps between atoms are avoided. We use the locus of the possible motions of HIV protease as an example: movies of its motion can be seen at http://www.pa.msu.edu/~lei.

Computer Simulation↗
PubMed2002

The average distances in random graphs with given expected degrees.

Random graph theory is used to examine the "small-world phenomenon"; any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain families of random graphs with given expected degrees the average distance is almost surely of order log nlog d, where d is the weighted average of the sum of squares of the expected degrees. Of particular interest are power law random graphs in which the number of vertices of degree k is proportional to 1kbeta for some fixed exponent beta. For the case of beta > 3, we prove that the average distance of the power law graphs is almost surely of order log nlog d. However, many Internet, social, and citation networks are power law graphs with exponents in the range 2 < beta < 3 for which the power law random graphs have average distance almost surely of order log log n, but have diameter of order log n (provided having some mild constraints for the average distance and maximum degree). In particular, these graphs contain a dense subgraph, which we call the core, having n(clog log n) vertices. Almost all vertices are within distance log log n of the core although there are vertices at distance log n from the core.

Journal Article↗
PubMed2006

Small-world network organization of functional connectivity of EEG slow-wave activity during sleep.

OBJECTIVE: To analyze the functional connectivity patterns of the EEG slow-wave activity during the different sleep stages and Cyclic Alternating Pattern (CAP) conditions, using concepts derived from Graph Theory. METHODS: We evaluated spatial patterns of EEG slow-wave synchronization between all possible pairs of electrodes (19) placed over the scalp of 10 sleeping healthy young normal subjects using two graph theoretical measures: the clustering coefficient (Cp) and the characteristic path length (Lp). The measures were obtained during the different sleep stages and CAP conditions from the real EEG connectivity networks and randomized control (surrogate) networks (Cp-s and Lp-s). RESULTS: Cp and Cp/Cp-s increased significantly from wakefulness to sleep while Lp and Lp/Lp-s did not show changes. Cp/Cp-s was higher for A1 phases, compared to B phases of CAP. CONCLUSIONS: The network organization of the EEG slow-wave synchronization during sleep shows features characteristic of small-world networks (high Cp combined with low Lp); this type of organization is slightly but significantly more evident during the CAP A1 subtypes. SIGNIFICANCE: Our results show feasibility of using graph theoretical measures to characterize the complexity of brain networks during sleep and might indicate sleep, and the A1 phases of CAP in particular, as a period during which slow-wave synchronization shows optimal network organization for information processing.

Adult↗
PubMed2006

Network analysis of Danish cattle industry trade patterns as an evaluation of risk potential for disease spread.

Trade patterns of animal movements in a specific industry are complex and difficult to study because there are many stakeholders, premises that are heterogeneously spread over the country, and a highly dynamic flow of animals exists among them. The Danish cattle industry was defined as a network of animal movements and graph theory was used to analyse the movements of cattle within this network. A premise was defined as a farm, an abattoir or a market. These premises constituted the network nodes in the graph and the animal movements between them were the links. In this framework, each premise had a sub-network of other premises to which it was linked by these animal movements. If no movement of animals were registered for a specific farm, then the sub-network for that premise consisted of only that premise. Otherwise, the sub-network linked the premise of interest to all premises from which and to which animals were moved, as long as there was a path linking animal movements to that specific premise. This approach allowed visualization and analyses of four levels of organization that existed in Denmark animal registers: (1) the animal that was moved, (2) the movements of all animals between two premises, (3) the specific premise network, and (4) the overall industry network. When contagious animals are moved from one premise to another, then to a third and so forth, these movements create a path for potential transfer of pathogens. The paths within which pathogens are present identify the transmission risks. A network of animal movements should provide information about pathogen transmission and disease spread. The network of the Danish cattle industry network was a directed scale-free graph (the direction of a movement was known), with an in-degree power of 2 an out-degree power of 1.46, consisted of 29,999 nodes, and 130,265 movements during a 6-month period. The in clustering coefficient was calculated to be 0.52 for the inward direction (movement to), while it was 0.02 for the outward direction (movement from). In Denmark, the cattle movements between premises demonstrated a large degree of heterogeneity. This heterogeneity in movements between farms should be used to evaluate the risk potential of disease transmission for each premise and must be considered when modelling disease spread between premises. The objective of this research was to describe the network of animal movements and not just the animal movements per se.

Animals↗
PubMed1986

Neighborhood analysis of low magnification structures (glands) in healthy, adenomatous, and carcinomatous colon mucosa.

A new algorithm analyzing neighborhood conditions of adenomatous tissue is is introduced. Using O'Callaghan's definition of neighborhoods, a graph theory approach for measuring histomorphological structures can be created as follows: glands are defined as vertices and the coherence of neighboring glands as edges. The procedure leads to an unoriented, well-defined graph which contains information usually not measurable by conventional morphometric analysis. Measurements on healthy mucosa, tubulo-villous adenoma and highly to moderately differentiated adenocarcinoma of colon revealed statistically significant differences (p less than or equal to 0.05) for the following parameters: number of vertices, number of edges, frequency distribution of n-stars and of n-closed paths. Correct separation and reclassification of 83% of cases could be carried out using discriminant analysis. 11/15 cases (73%) could be classified correctly in a prospective group based upon the learning set. The significance of these findings for automatic pattern recognition in histopathology is discussed.

Adenocarcinoma↗
PubMed2006

Prediction of carbon-13 NMR chemical shift of alkanes with rooted path vector.

Systematic studies were further made on graph theory in quantitative structure-spectrum relationships (QSSR) for various areas of spectroscopies. Chemical shifts (CS) in alkanes for carbon-13 nuclear magnetic resonance (13C NMR) were well correlated with a set of novel molecular graph indices, called the rooted path vector of various lengths, as several multivariate regression equations as following:CS=3.022+5.336P1+7.356P2-1.648P3+0.83859P4+0.210P5-0.138P6-0.506P7+2.486P8-1.669P9; n=402, m=9, R=0.944, RCV=0.9413, S.D.=3.333, F=358.343, U=35833.211, Q=4355.422 for all types (primary, secondly, tertiary, quaternary as well as methane) of carbon atoms CS=0.983+6.811P1+7.584P2-2.029P3+0.809P4+0.106P5+0.043P6-0.124P7+1.715P8-1.101P9; n=374, m=9, R=0.975, RCV=0.9737, S.D.=2.303, F=773.372, U=36912.109, Q=1930.363 for primary, secondly, tertiary (including methane) carbon atoms; and CS=27.819+2.351P2+0.549P3-0.440P4+0.170P5-0.050P6; n=27, m=5, R=0.992, RCV=0.9674, S.D.=0.324, F=265.418, U=138.891, Q=2.198 for quaternary carbon atoms, respectively. Quite good estimation and prediction results were obtained from the quantitative molecular modeling and the performance of multiple linear regression (MLR) equations were tested to work well through cross-validation (CV) with the leave-one-out (LOO) procedure.

Alkanes↗