Graph theoretical insights into evolution of multidomain proteins.

We study properties of multidomain proteins from a graph theoretical perspective. In particular, we demonstrate connections between properties of the domain overlap graph and certain variants of Dollo parsimony models. We apply our graph theoretical results to address several interrelated questions: do proteins acquire new domains infrequently, or often enough that the same combinations of domains will be created repeatedly through independent events? Once domain architectures are created do they persist? In other words, is the existence of ancestral proteins with domain compositions not observed in contemporary proteins unlikely? Our experimental results indicate that independent merges of domain pairs are not uncommon in large superfamilies.     

Graph theoretical methods for comparing phytosociological structures

This paper describes some methods that can be used to compare the phytosociological structure of plant communities using some graph theoretic properties of the directed graphs that represent them. In such a graph, the species are represented by points and the association of species A with species B is represented by a directed line segment going from B to A. Two communities can be compared using simple indices to measure the similarity of their species-lists (point similarity) and of the species associations in them (line similarity). A more sophisticated and informative measure of line similarity is the probability that, given the number of points shared by two graphs, they have at least as many lines in common as they are observed to have. A formula for calculating that probability is given here. The graphs of community structure can also be compared with respect to the homogeneity of the distribution of the lines among the points, a property related to the number of species that are important in determining the composition of the community. These techniques are illustrated using the graphs of the phytosociological structure of intertidal seaweed communities on the southeast coast of Nova Scotia.Nomenclature follows: South and Cardinal (1970)     

TransMiner: Mining transitive associations among biological objects from text

Associations among biological objects such as genes, proteins, and drugs can be discovered automatically from the scientific literature. TransMiner is a system for finding associations among objects by mining the Medline database of the scientific literature. The direct associations among the objects are discovered based on the principle of co-occurrence in the form of an association graph. The principle of transitive closure is applied to the association graph to find potential transitive associations. The potential transitive associations that are indeed direct are discovered by iterative retrieval and mining of the Medline documents. Those associations that are not found explicitly in the entire Medline database are transitive associations and are the candidates for hypothesis generation. The transitive associations were ranked based on the sum of weight of terms that cooccur with both the objects. The direct and transitive associations are visualized using a graph visualization applet. TransMiner was tested by finding associations among 56 breast cancer genes and among 24 objects in the calpain signal transduction pathway. TransMiner was also used to rediscover associations between magnesium and migraine.     

Graph theoretical model of a sensorimotor connectome in zebrafish

Mapping the detailed connectivity patterns (connectomes) of neural circuits is a central goal of neuroscience. The best quantitative approach to analyzing connectome data is still unclear but graph theory has been used with success. We present a graph theoretical model of the posterior lateral line sensorimotor pathway in zebrafish. The model includes 2,616 neurons and 167,114 synaptic connections. Model neurons represent known cell types in zebrafish larvae, and connections were set stochastically following rules based on biological literature. Thus, our model is a uniquely detailed computational representation of a vertebrate connectome. The connectome has low overall connection density, with 2.45% of all possible connections, a value within the physiological range. We used graph theoretical tools to compare the zebrafish connectome graph to small-world, random and structured random graphs of the same size. For each type of graph, 100 randomly generated instantiations were considered. Degree distribution (the number of connections per neuron) varied more in the zebrafish graph than in same size graphs with less biological detail. There was high local clustering and a short average path length between nodes, implying a small-world structure similar to other neural connectomes and complex networks. The graph was found not to be scale-free, in agreement with some other neural connectomes. An experimental lesion was performed that targeted three model brain neurons, including the Mauthner neuron, known to control fast escape turns. The lesion decreased the number of short paths between sensory and motor neurons analogous to the behavioral effects of the same lesion in zebrafish. This model is expandable and can be used to organize and interpret a growing database of information on the zebrafish connectome.     

Using iterative ridge regression to explore associations between conditioned variables

We address a specific case of joint probability mapping, where the information presented is the probabilistic associations of random variables under a certain condition variable (conditioned associations). Bayesian and dependency networks graphically map the joint probabilities of random variables, though both networks may identify associations that are independent of the condition (background associations). Since the background associations have the same topological features as conditioned associations, it is difficult to discriminate between conditioned and non-conditioned associations, which results in a major increase in the search space. We introduce a modification of the dependency network method, which produces a directed graph, containing only condition-related associations. The graph nodes represent the random variables and the graph edges represent the associations that arise under the condition variable. This method is based on ridge-regression, where one can utilize a numerically robust and computationally efficient algorithm implementation. We illustrate the method's efficiency in the context of a medically relevant process, the emergence of drug-resistant variants of human immunodeficiency virus (HIV) in drug-treated, HIV-infected people. Our mapping was used to discover associations between variants that are conditioned by the initiation of a particular drug treatment regimen. We have demonstrated that our method can recover known associations of such treatment with selected resistance mutations as well as documented associations between different mutations. Moreover, our method revealed novel associations that are statistically significant and biologically plausible.     

tRNA structure from a graph and quantum theoretical perspective

One of the objectives of theoretical biochemistry is to find a suitable representation of molecules allowing us to encode what we know about their structures, interactions and reactivity. Particularly, tRNA structure is involved in some processes like aminoacylation and genetic code translation, and for this reason these molecules represent a biochemical object of the utmost importance requiring characterization. We propose here two fundamental aspects for characterizing and modeling them. The first takes into consideration the connectivity patterns, i.e. the set of linkages between atoms or molecular fragments (a key tool for this purpose is the use of graph theory), and the second one requires the knowledge of some properties related to the interactions taking place within the molecule, at least in an approximate way, and perhaps of its reactivity in certain means. We used quantum mechanics to achieve this goal; specifically, we have used partial charges as a manifestation of the reply to structural changes. These charges were appropriately modified to be used as weighted factors for elements constituting the molecular graph. This new graph-tRNA context allow us to detect some structure-function relationships.     

基于图自编码器和协同训练预测miRNA[]与疾病的关联

近年来,越来越多的生物学实验研究表明,microRNA (miRNA)在人类复杂疾病的发展中发挥着重要作用。因此,预测miRNA与疾病之间的关联有助于疾病的准确诊断和有效治疗。由于传统的生物学实验是一种昂贵且耗时的方式,于是许多基于生物学数据的计算模型被提出来预测miRNA与疾病的关联。本研究提出了一种端到端的深度学习模型来预测miRNA-疾病关联关系,称为MDAGAC。首先,通过整合疾病语义相似性,miRNA功能相似性和高斯相互作用谱核相似性,构建miRNA和疾病的相似性图。然后,通过图自编码器和协同训练来改善标签传播的效果。该模型分别在miRNA图和疾病图上建立了两个图自编码器,并对这两个图自编码器进行了协同训练。miRNA图和疾病图上的图自编码器能够通过初始关联矩阵重构得分矩阵,这相当于在图上传播标签。miRNA-疾病关联的预测概率可以从得分矩阵得到。基于五折交叉验证的实验结果表明,MDAGAC方法可靠有效,优于现有的几种预测miRNA-疾病关联的方法。     

DLGCN:基于图卷积网络的药物-lncRNA[]关联预测

为实现高通量识别新的药物-长链非编码RNA(Long non-coding RNA, lncRNA)关联,本文提出了一种基于图卷积网络模型来识别潜在药物-lncRNA关联的方法DLGCN(Drug-LncRNA graph convolution network)。首先,基于药物的结构信息和lncRNA的序列信息分别构建了药物-药物和lncRNA-lncRNA相似性网络,并整合实验证实的药物-lncRNA关联构建了药物-lncRNA异质性网络。然后,将注意力机制和图卷积运算应用于该网络中,学习药物和lncRNA的低维特征,基于整合的低维特征预测新的药物-lncRNA关联。通过效能评估,DLGCN的受试者工作特性曲线下面积(Area under receiver operating characteristic, AUROC)达到0.843 1,优于经典的机器学习方法和常见的深度学习方法。此外,DLGCN预测到姜黄素能够调控lncRNA MALAT1的表达,已被最近的研究证实。DLGCN能够有效预测药物-lncRNA关联,为肿瘤治疗新靶点的识别和抗癌药物的筛选提供了重要参考。     

Graph theoretical analysis of complex networks in the brain

Since the discovery of small-world and scale-free networks the study of complex systems from a network perspective has taken an enormous flight. In recent years many important properties of complex networks have been delineated. In particular, significant progress has been made in understanding the relationship between the structural properties of networks and the nature of dynamics taking place on these networks. For instance, the 'synchronizability' of complex networks of coupled oscillators can be determined by graph spectral analysis. These developments in the theory of complex networks have inspired new applications in the field of neuroscience. Graph analysis has been used in the study of models of neural networks, anatomical connectivity, and functional connectivity based upon fMRI, EEG and MEG. These studies suggest that the human brain can be modelled as a complex network, and may have a small-world structure both at the level of anatomical as well as functional connectivity. This small-world structure is hypothesized to reflect an optimal situation associated with rapid synchronization and information transfer, minimal wiring costs, as well as a balance between local processing and global integration. The topological structure of functional networks is probably restrained by genetic and anatomical factors, but can be modified during tasks. There is also increasing evidence that various types of brain disease such as Alzheimer's disease, schizophrenia, brain tumours and epilepsy may be associated with deviations of the functional network topology from the optimal small-world pattern.     

Some theoretical aspects of reprogramming the standard genetic code

Reprogramming of the standard genetic code to include non-canonical amino acids (ncAAs) opens new prospects for medicine, industry, and biotechnology. There are several methods of code engineering, which allow us for storing new genetic information in DNA sequences and producing proteins with new properties. Here, we provided a theoretical background for the optimal genetic code expansion, which may find application in the experimental design of the genetic code. We assumed that the expanded genetic code includes both canonical and non-canonical information stored in 64 classical codons. What is more, the new coding system is robust to point mutations and minimizes the possibility of reversion from the new to old information. In order to find such codes, we applied graph theory to analyze the properties of optimal codon sets. We presented the formal procedure in finding the optimal codes with various number of vacant codons that could be assigned to new amino acids. Finally, we discussed the optimal number of the newly incorporated ncAAs and also the optimal size of codon groups that can be assigned to ncAAs.     

Graph theoretical analysis of the phytosociological structure of plant communities: An application to mixed forest

Summary A sampling method, compatible with the theory elaborated in the previous paper, was used to investigate the mixed-forest community of a woodlot in Southern Ontario. The results provide an illustration of the graph theoretical methods developed for the elucidation of a community's phytosociological structure. Certain conjectures about the community are tested and it is found that Goodall's hypothesis concerning the nature of a plant community is supported. The tests also show that the vegetation of the study area forms a single natural grouping despite the disparity of the position ofAcer saccharum and the polarity evident among the other tree species.Nomenclature follows Gleason (1952).From a thesis submitted to the University of Toronto in partial fulfilment of the requirements for the degree of Master of Science.I wish to thank Dr. G. A. Yarranton for his ideas and helpful supervision, and my father for his advice and encouragement. Thanks ag also due to Miss J. E. Ellard and Mr. S. Roy who helped prepare the figures. This research has been supported by a National Research Council of Canada and by NRCC grant A-2910.     

Identification of regulatory properties of metabolic networks by graph theoretical modeling

An earlier graph theoretical model of metabolic and gene-expression networks has been modified and extended to include the effect of electrical potentials on binding constants, representation of uncatalyzed processes, and treatment of parallel reactions catalyzed by a single enzyme. Formal operations on the graph, which are facilitated by a set of standardized guidelines, identify the feedback signals in the network and rank them according to their influence. The technique was applied to a model of glycolysis in ascites tumor cells in the absence and presence of 12.5 mM exogenous glucose. Feedback regulation was widely distributed and mostly due to binding of adenine nucleotide cofactors to the enzymes of the network. The major changes in feedback regulation on adding glucose is the relief of inhibition of hexokinase and phosphofructokinase and the activation of pyruvate kinase. We conclude that regulation of tumor cell glycolysis is not restricted to hexokinase or to (Na+,K+)-ATPase as was previously suggested by others.     

Stability of multienzyme systems with feedback regulation: a graph theoretical approach

Stability of multienzyme systems with feedback regulation has been analyzed on the basis of the Lienard-Chipart criteria. The rules governing the topological graph construction for multienzyme systems have been developed. A theorem about correspondence of the graph constructed and coefficients of the characteristic polynomial of linearized kinetic equations is proved. The graph-theoretical stability analysis proposed is illustrated by a number of examples of multienzyme systems with feedback regulation.     

Extracting gene networks for low-dose radiation using graph theoretical algorithms

Genes with common functions often exhibit correlated expression levels, which can be used to identify sets of interacting genes from microarray data. Microarrays typically measure expression across genomic space, creating a massive matrix of co-expression that must be mined to extract only the most relevant gene interactions. We describe a graph theoretical approach to extracting co-expressed sets of genes, based on the computation of cliques. Unlike the results of traditional clustering algorithms, cliques are not disjoint and allow genes to be assigned to multiple sets of interacting partners, consistent with biological reality. A graph is created by thresholding the correlation matrix to include only the correlations most likely to signify functional relationships. Cliques computed from the graph correspond to sets of genes for which significant edges are present between all members of the set, representing potential members of common or interacting pathways. Clique membership can be used to infer function about poorly annotated genes, based on the known functions of better-annotated genes with which they share clique membership (i.e., “guilt-by-association”). We illustrate our method by applying it to microarray data collected from the spleens of mice exposed to low-dose ionizing radiation. Differential analysis is used to identify sets of genes whose interactions are impacted by radiation exposure. The correlation graph is also queried independently of clique to extract edges that are impacted by radiation. We present several examples of multiple gene interactions that are altered by radiation exposure and thus represent potential molecular pathways that mediate the radiation response.     

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.     

A review of theoretical aspects of HLA and disease associations

A number of antigens (alleles) of the human histocompatibility (HLA) system have been shown to be associated with a wide range of chronic diseases. Recently a great deal of interest has been shown in many of the theoretical aspects of HLA disease associations. These range from statistical problems of detecting significant associations to the development of models to determine the mode of inheritance of the disease. These models, as well as other features of HLA disease associations, will be reviewed in this paper.     

The interplay between microscopic and mesoscopic structures in complex networks

Understanding a complex network's structure holds the key to understanding its function. The physics community has contributed a multitude of methods and analyses to this cross-disciplinary endeavor. Structural features exist on both the microscopic level, resulting from differences between single node properties, and the mesoscopic level resulting from properties shared by groups of nodes. Disentangling the determinants of network structure on these different scales has remained a major, and so far unsolved, challenge. Here we show how multiscale generative probabilistic exponential random graph models combined with efficient, distributive message-passing inference techniques can be used to achieve this separation of scales, leading to improved detection accuracy of latent classes as demonstrated on benchmark problems. It sheds new light on the statistical significance of motif-distributions in neural networks and improves the link-prediction accuracy as exemplified for gene-disease associations in the highly consequential Online Mendelian Inheritance in Man database.     

The graph theoretical analysis of the SSVEP harmonic response networks

Steady-state visually evoked potentials (SSVEP) have been widely used in the neural engineering and cognitive neuroscience researches. Previous studies have indicated that the SSVEP fundamental frequency responses are correlated with the topological properties of the functional networks entrained by the periodic stimuli. Given the different spatial and functional roles of the fundamental frequency and harmonic responses, in this study we further investigated the relation between the harmonic responses and the corresponding functional networks, using the graph theoretical analysis. We found that the second harmonic responses were positively correlated to the mean functional connectivity, clustering coefficient, and global and local efficiencies, while negatively correlated with the characteristic path lengths of the corresponding networks. In addition, similar pattern occurred with the lowest stimulus frequency (6.25 Hz) at the third harmonic responses. These findings demonstrate that more efficient brain networks are related to larger SSVEP responses. Furthermore, we showed that the main connection pattern of the SSVEP harmonic response networks originates from the interactions between the frontal and parietal–occipital regions. Overall, this study may bring new insights into the understanding of the brain mechanisms underlying SSVEP.     

TSAR,a new graph–theoretical approach to computational modeling of protein side‐chain flexibility: Modeling of ionization properties of proteins

A new graph–theoretical approach called thermodynamic sampling of amino acid residues (TSAR) has been elaborated to explicitly account for the protein side chain flexibility in modeling conformation‐dependent protein properties. In TSAR, a protein is viewed as a graph whose nodes correspond to structurally independent groups and whose edges connect the interacting groups. Each node has its set of states describing conformation and ionization of the group, and each edge is assigned an array of pairwise interaction potentials between the adjacent groups. By treating the obtained graph as a belief‐network—a well‐established mathematical abstraction—the partition function of each node is found. In the current work we used TSAR to calculate partition functions of the ionized forms of protein residues. A simplified version of a semi‐empirical molecular mechanical scoring function, borrowed from our Lead Finder docking software, was used for energy calculations. The accuracy of the resulting model was validated on a set of 486 experimentally determined pK_a values of protein residues. The average correlation coefficient (R) between calculated and experimental pK_a values was 0.80, ranging from 0.95 (for Tyr) to 0.61 (for Lys). It appeared that the hydrogen bond interactions and the exhaustiveness of side chain sampling made the most significant contribution to the accuracy of pK_a calculations. Proteins 2011; © 2011 Wiley‐Liss, Inc.