QSAR study on benzenesulphonamide carbonic anhydrase inhibitors: topological approach using Balaban index

QSAR study on benzenesulphonamide carbonic anhydrase inhibitors has been made using the most discriminatory Balaban index (J). The regression analysis has shown that even in monoparametric regression this index gave excellent results. Furthermore, using the combination of the Balaban Index (J) with the first-order Randic connectivity index ((1)chi) and indicator parameters, tremendous improvement in the statistics has been observed. The results are critically discussed on the basis of regression data and cross-validation parameters.     

Recent developments in quantitative graph theory: information inequalities for networks

In this article, we tackle a challenging problem in quantitative graph theory. We establish relations between graph entropy measures representing the structural information content of networks. In particular, we prove formal relations between quantitative network measures based on Shannon's entropy to study the relatedness of those measures. In order to establish such information inequalities for graphs, we focus on graph entropy measures based on information functionals. To prove such relations, we use known graph classes whose instances have been proven useful in various scientific areas. Our results extend the foregoing work on information inequalities for graphs.     

Finding landmarks - An investigation of viewing behavior during spatial navigation in VR using a graph-theoretical analysis approach

Vision provides the most important sensory information for spatial navigation. Recent technical advances allow new options to conduct more naturalistic experiments in virtual reality (VR) while additionally gathering data of the viewing behavior with eye tracking investigations. Here, we propose a method that allows one to quantify characteristics of visual behavior by using graph-theoretical measures to abstract eye tracking data recorded in a 3D virtual urban environment. The analysis is based on eye tracking data of 20 participants, who freely explored the virtual city Seahaven for 90 minutes with an immersive VR headset with an inbuild eye tracker. To extract what participants looked at, we defined “gaze” events, from which we created gaze graphs. On these, we applied graph-theoretical measures to reveal the underlying structure of visual attention. Applying graph partitioning, we found that our virtual environment could be treated as one coherent city. To investigate the importance of houses in the city, we applied the node degree centrality measure. Our results revealed that 10 houses had a node degree that exceeded consistently two-sigma distance from the mean node degree of all other houses. The importance of these houses was supported by the hierarchy index, which showed a clear hierarchical structure of the gaze graphs. As these high node degree houses fulfilled several characteristics of landmarks, we named them “gaze-graph-defined landmarks”. Applying the rich club coefficient, we found that these gaze-graph-defined landmarks were preferentially connected to each other and that participants spend the majority of their experiment time in areas where at least two of those houses were visible. Our findings do not only provide new experimental evidence for the development of spatial knowledge, but also establish a new methodology to identify and assess the function of landmarks in spatial navigation based on eye tracking data.     

Laplacian Estrada and Normalized Laplacian Estrada Indices of Evolving Graphs

Large-scale time-evolving networks have been generated by many natural and technological applications, posing challenges for computation and modeling. Thus, it is of theoretical and practical significance to probe mathematical tools tailored for evolving networks. In this paper, on top of the dynamic Estrada index, we study the dynamic Laplacian Estrada index and the dynamic normalized Laplacian Estrada index of evolving graphs. Using linear algebra techniques, we established general upper and lower bounds for these graph-spectrum-based invariants through a couple of intuitive graph-theoretic measures, including the number of vertices or edges. Synthetic random evolving small-world networks are employed to show the relevance of the proposed dynamic Estrada indices. It is found that neither the static snapshot graphs nor the aggregated graph can approximate the evolving graph itself, indicating the fundamental difference between the static and dynamic Estrada indices.     

Towards information inequalities for generalized graph entropies

In this article, we discuss the problem of establishing relations between information measures for network structures. Two types of entropy based measures namely, the Shannon entropy and its generalization, the Rényi entropy have been considered for this study. Our main results involve establishing formal relationships, by means of inequalities, between these two kinds of measures. Further, we also state and prove inequalities connecting the classical partition-based graph entropies and partition-independent entropy measures. In addition, several explicit inequalities are derived for special classes of graphs.     

QSAR prediction of toxicity of nitrobenzenes

A QSAR analysis has been carried out on the toxicities of 40 mono-substituted nitrobenzenes using recently introduced PI and Sz indices, as well as older molecular redundancy (MRI) and Balaban indices (J). The results have shown that no statistically significant mono-parametric QSAR models are possible. Also, that along with PI, Sz, MRI and J indices are the appropriate parameters to be used in developing multiparametric QSAR models. The toxicities of nitrobenzenes are well predicted by a penta-parametric model consisting of PI, Sz, J, MRI and Ip(1) (an indicator parameter taking care of the effect of substitution at 2-position) as the correlating parameters. The predictive ability of the model is determined by a cross-validation method.     

Automatic lumen segmentation using uniqueness of vascular connected region for intravascular optical coherence tomography

We present an automatic lumen segmentation method using uniqueness of connected region for intravascular optical coherence tomography (IVOCT), which can effectively remove the effect on lumen segmentation caused by blood artifacts. Utilizing the uniqueness of vascular wall on A-lines, we detect the A-lines shared by multiple connected regions, identify connected regions generated by blood artifacts using traversal comparison of connected regions' location, shared ratio and area ratio and then remove all artifacts. We compare these three methods by 216 challenging images with severe blood artifacts selected from clinical 1076 IVOCT images. The metrics of the proposed method are evaluated including Dice index, Jaccard index and accuracy of 94.57%, 90.12%, 98.02%. Compared with automatic lumen segmentation based on the previous morphological feature method and widely used dynamic programming method, the metrics of the proposed method are significantly enhanced, especially in challenging images with severe blood artifacts.     

Global snapshot of a protein interaction network-a percolation based approach

MOTIVATION: Biologically significant information can be revealed by modeling large-scale protein interaction data using graph theory based network analysis techniques. However, the methods that are currently being used draw conclusions about the global features of the network from local connectivity data. A more systematic approach would be to define global quantities that measure (1) how strongly a protein ties with the other parts of the network and (2) how significantly an interaction contributes to the integrity of the network, and connect them with phenotype data from other sources. In this paper, we introduce such global connectivity measures and develop a stochastic algorithm based upon percolation in random graphs to compute them. RESULTS: We show that, in terms of global connectivities, the distribution of essential proteins is distinct from the background. This observation highlights a fundamental difference between the essential and the non-essential proteins in the network. We also find that the interaction data obtained from different experimental methods such as immunoprecipitation and two-hybrid techniques contribute differently to network integrities. Such difference between different experimental methods can provide insight into the systematic bias present among these techniques. SUPPLEMENTARY INFORMATION: The full list of our results can be found in the supplemental web site http://www.nas.nasa.gov/Groups/SciTech/nano/msamanta/projects/percolation/index.php     

Integrating multi-attribute similarity networks for robust representation of the protein space

MOTIVATION: A global view of the protein space is essential for functional and evolutionary analysis of proteins. In order to achieve this, a similarity network can be built using pairwise relationships among proteins. However, existing similarity networks employ a single similarity measure and therefore their utility depends highly on the quality of the selected measure. A more robust representation of the protein space can be realized if multiple sources of information are used. RESULTS: We propose a novel approach for analyzing multi-attribute similarity networks by combining random walks on graphs with Bayesian theory. A multi-attribute network is created by combining sequence and structure based similarity measures. For each attribute of the similarity network, one can compute a measure of affinity from a given protein to every other protein in the network using random walks. This process makes use of the implicit clustering information of the similarity network, and we show that it is superior to naive, local ranking methods. We then combine the computed affinities using a Bayesian framework. In particular, when we train a Bayesian model for automated classification of a novel protein, we achieve high classification accuracy and outperform single attribute networks. In addition, we demonstrate the effectiveness of our technique by comparison with a competing kernel-based information integration approach.     

Interrelations of Graph Distance Measures Based on Topological Indices

In this paper, we derive interrelations of graph distance measures by means of inequalities. For this investigation we are using graph distance measures based on topological indices that have not been studied in this context. Specifically, we are using the well-known Wiener index, Randić index, eigenvalue-based quantities and graph entropies. In addition to this analysis, we present results from numerical studies exploring various properties of the measures and aspects of their quality. Our results could find application in chemoinformatics and computational biology where the structural investigation of chemical components and gene networks is currently of great interest.     

Graph sharpening plus graph integration: a synergy that improves protein functional classification

MOTIVATION: Predicting protein function is a central problem in bioinformatics, and many approaches use partially or fully automated methods based on various combination of sequence, structure and other information on proteins or genes. Such information establishes relationships between proteins that can be modelled most naturally as edges in graphs. A priori, however, it is often unclear which edges from which graph may contribute most to accurate predictions. For that reason, one established strategy is to integrate all available sources, or graphs as in graph integration, in the hope that the positive signals will add to each other. However, in the problem of functional prediction, noise, i.e. the presence of inaccurate or false edges, can still be large enough that integration alone has little effect on prediction accuracy. In order to reduce noise levels and to improve integration efficiency, we present here a recent method in graph-based learning, graph sharpening, which provides a theoretically firm yet intuitive and practical approach for disconnecting undesirable edges from protein similarity graphs. This approach has several attractive features: it is quick, scalable in the number of proteins, robust with respect to errors and tolerant of very diverse types of protein similarity measures. RESULTS: We tested the classification accuracy in a test set of 599 proteins with remote sequence homology spread over 20 Gene Ontology (GO) functional classes. When compared to integration alone, graph sharpening plus integration of four vastly different molecular similarity measures improved the overall classification by nearly 30% [0.17 average increase in the area under the ROC curve (AUC)]. Moreover, and partially through the increased sparsity of the graphs induced by sharpening, this gain in accuracy came at negligible computational cost: sharpening and integration took on average 4.66 (+/-4.44) CPU seconds. AVAILABILITY: Software and Supplementary data will be available on http://mammoth.bcm.tmc.edu/     

Inferring Cell-Scale Signalling Networks via Compressive Sensing

Signalling network inference is a central problem in system biology. Previous studies investigate this problem by independently inferring local signalling networks and then linking them together via crosstalk. Since a cellular signalling system is in fact indivisible, this reductionistic approach may have an impact on the accuracy of the inference results. Preferably, a cell-scale signalling network should be inferred as a whole. However, the holistic approach suffers from three practical issues: scalability, measurement and overfitting. Here we make this approach feasible based on two key observations: 1) variations of concentrations are sparse due to separations of timescales; 2) several species can be measured together using cross-reactivity. We propose a method, CCELL, for cell-scale signalling network inference from time series generated by immunoprecipitation using Bayesian compressive sensing. A set of benchmark networks with varying numbers of time-variant species is used to demonstrate the effectiveness of our method. Instead of exhaustively measuring all individual species, high accuracy is achieved from relatively few measurements.     

Disulfide connectivity prediction using recursive neural networks and evolutionary information

MOTIVATION: We focus on the prediction of disulfide bridges in proteins starting from their amino acid sequence and from the knowledge of the disulfide bonding state of each cysteine. The location of disulfide bridges is a structural feature that conveys important information about the protein main chain conformation and can therefore help towards the solution of the folding problem. Existing approaches based on weighted graph matching algorithms do not take advantage of evolutionary information. Recursive neural networks (RNN), on the other hand, can handle in a natural way complex data structures such as graphs whose vertices are labeled by real vectors, allowing us to incorporate multiple alignment profiles in the graphical representation of disulfide connectivity patterns. RESULTS: The core of the method is the use of machine learning tools to rank alternative disulfide connectivity patterns. We develop an ad-hoc RNN architecture for scoring labeled undirected graphs that represent connectivity patterns. In order to compare our algorithm with previous methods, we report experimental results on the SWISS-PROT 39 dataset. We find that using multiple alignment profiles allows us to obtain significant prediction accuracy improvements, clearly demonstrating the important role played by evolutionary information. AVAILABILITY: The Web interface of the predictor is available at http://neural.dsi.unifi.it/cysteines     

Principal Networks

Graph representations of brain connectivity have attracted a lot of recent interest, but existing methods for dividing such graphs into connected subnetworks have a number of limitations in the context of neuroimaging. This is an important problem because most cognitive functions would be expected to involve some but not all brain regions. In this paper we outline a simple approach for decomposing graphs, which may be based on any measure of interregional association, into coherent “principal networks”. The technique is based on an eigendecomposition of the association matrix, and is closely related to principal components analysis. We demonstrate the technique using cortical thickness and diffusion tractography data, showing that the subnetworks which emerge are stable, meaningful and reproducible. Graph-theoretic measures of network cost and efficiency may be calculated separately for each principal network. Unlike some other approaches, all available connectivity information is taken into account, and vertices may appear in none or several of the subnetworks. Subject-by-subject “scores” for each principal network may also be obtained, under certain circumstances, and related to demographic or cognitive variables of interest.