Petri Net Siphon Analysis and Network Centrality Measures for Identifying Combination Therapies in Signaling Pathways

Aberrant behavior of biological signaling pathways has been implicated in diseases such as cancers. Therapies have been developed to target proteins in these networks in the hope of curing the illness or bringing about remission. However, identifying targets for drug inhibition that exhibit good therapeutic index has proven to be challenging since signaling pathways have a large number of components and many interconnections such as feedback, crosstalk, and divergence. Unfortunately, some characteristics of these pathways such as redundancy, feedback, and drug resistance reduce the efficacy of single drug target therapy and necessitate the employment of more than one drug to target multiple nodes in the system. However, choosing multiple targets with high therapeutic index poses more challenges since the combinatorial search space could be huge. To cope with the complexity of these systems, computational tools such as ordinary differential equations have been used to successfully model some of these pathways. Regrettably, for building these models, experimentally-measured initial concentrations of the components and rates of reactions are needed which are difficult to obtain, and in very large networks, they may not be available at the moment. Fortunately, there exist other modeling tools, though not as powerful as ordinary differential equations, which do not need the rates and initial conditions to model signaling pathways. Petri net and graph theory are among these tools. In this thesis, we introduce a methodology based on Petri net siphon analysis and graph network centrality measures for identifying prospective targets for single and multiple drug therapies. In this methodology, first, potential targets are identified in the Petri net model of a signaling pathway using siphon analysis. Then, the graph-theoretic centrality measures are employed to prioritize the candidate targets. Also, an algorithm is developed to check whether the candidate targets are able to disable the intended outputs in the graph model of the system or not. We implement structural and dynamical models of ErbB1-Ras-MAPK pathways and use them to assess and evaluate this methodology. The identified drug-targets, single and multiple, correspond to clinically relevant drugs. Overall, the results suggest that this methodology, using siphons and centrality measures, shows promise in identifying and ranking drugs. Since this methodology only uses the structural information of the signaling pathways and does not need initial conditions and dynamical rates, it can be utilized in larger networks.

A Study of Some Centrality Measures in Graphs

Centrality is in fact one of the fundamental notions in graph theory which has established its close connection with various other areas like Social networks, Flow networks, Facility location problems etc. Even though a plethora of centrality measures have been introduced from time to time, according to the changing demands, the term is not well defined and we can only give some common qualities that a centrality measure is expected to have. Nodes with high centrality scores are often more likely to be very powerful, indispensable, influential, easy propagators of information, significant in maintaining the cohesion of the group and are easily susceptible to anything that disseminate in the network.

Betweenness Centrality in Some Classes of Graphs

There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.

Eigenvector centrality of nodes in multiplex networks

We extend the concept of eigenvector centrality to multiplex networks, and introduce several alternative parameters that quantify the importance of nodes in a multi-layered networked system, including the definition of vectorial-type centralities. In addition, we rigorously show that, under reasonable conditions, such centrality measures exist and are unique. Computer experiments and simulations demonstrate that the proposed measures provide substantially different results when applied to the same multiplex structure, and highlight the non-trivial relationships between the different measures of centrality introduced.

A new betweenness centrality measure based on an algorithm for ranking the nodes of a network

We propose and discuss a new centrality index for urban street patterns represented as networks in geographical space. This centrality measure, that we call ranking-betweenness centrality, combines the idea behind the random-walk betweenness centrality measure and the idea of ranking the nodes of a network produced by an adapted PageRank algorithm. We initially use a PageRank algorithm in which we are able to transform some information of the network that we want to analyze into numerical values. Numerical values summarizing the information are associated to each of the nodes by means of a data matrix. After running the adapted PageRank algorithm, a ranking of the nodes is obtained, according to their importance in the network. This classification is the starting point for applying an algorithm based on the random-walk betweenness centrality. A detailed example of a real urban street network is discussed in order to understand the process to evaluate the ranking-betweenness centrality proposed, performing some comparisons with other classical centrality measures.

Measuring centrality by a generalization of degree

Network analysis has emerged as a key technique in communication studies, economics, geography, history and sociology, among others. A fundamental issue is how to identify key nodes in a network, for which purpose a number of centrality measures have been developed. This paper proposes a new parametric family of centrality measures called generalized degree. It is based on the idea that a relationship to a more interconnected node contributes to centrality in a greater extent than a connection to a less central one. Generalized degree improves on degree by redistributing its sum over the network with the consideration of the global structure. Application of the measure is supported by a set of basic properties. A sufficient condition is given for generalized degree to be rank monotonic, excluding counter-intuitive changes in the centrality ranking after certain modifications of the network. The measure has a graph interpretation and can be calculated iteratively. Generalized degree is recommended to apply besides degree since it preserves most favorable attributes of degree, but better reflects the role of the nodes in the network and has an increased ability to distinguish between their importance.

Edge centrality via the Holevo quantity

In the study of complex networks, vertex centrality measures are used to identify the most important vertices within a graph. A related problem is that of measuring the centrality of an edge. In this paper, we propose a novel edge centrality index rooted in quantum information. More specifically, we measure the importance of an edge in terms of the contribution that it gives to the Von Neumann entropy of the graph. We show that this can be computed in terms of the Holevo quantity, a well known quantum information theoretical measure. While computing the Von Neumann entropy and hence the Holevo quantity requires computing the spectrum of the graph Laplacian, we show how to obtain a simplified measure through a quadratic approximation of the Shannon entropy. This in turns shows that the proposed centrality measure is strongly correlated with the negative degree centrality on the line graph. We evaluate our centrality measure through an extensive set of experiments on real-world as well as synthetic networks, and we compare it against commonly used alternative measures.

Social network extraction and analysis based on multimodal dyadic interaction

Social interactions are a very important component in people"s lives. Social network analysis has become a common technique used to model and quantify the properties of social interactions. In this paper, we propose an integrated framework to explore the characteristics of a social network extracted from multimodal dyadic interactions. For our study, we used a set of videos belonging to New York Times" Blogging Heads opinion blog. The Social Network is represented as an oriented graph, whose directed links are determined by the Influence Model. The links" weights are a measure of the"influence" a person has over the other. The states of the Influence Model encode automatically extracted audio/visual features from our videos using state-of-the art algorithms. Our results are reported in terms of accuracy of audio/visual data fusion for speaker segmentation and centrality measures used to characterize the extracted social network.

Redes de colaboração científica na área de química no Brasil: um estudo baseado nas coautorias dos artigos da revista Química Nova

In this paper we built three co-authorship networks displaying the acquaintances between countries, universities and authors that have published papers in Quimica Nova from 1995 to 2008. Our research was conducted applying a bibliometric approach to 1782 papers and over 4200 authors. Centrality measures were used and the most significant actors of each network were pointed out. The results using the centrality metrics and the network structures indicated that Quimica Nova resembles a typical scientific community.

Disease-Gene Association Using Genetic Programming

As a result of mutation in genes, which is a simple change in our DNA, we will have undesirable phenotypes which are known as genetic diseases or disorders. These small changes, which happen frequently, can have extreme results. Understanding and identifying these changes and associating these mutated genes with genetic diseases can play an important role in our health, by making us able to find better diagnosis and therapeutic strategies for these genetic diseases. As a result of years of experiments, there is a vast amount of data regarding human genome and different genetic diseases that they still need to be processed properly to extract useful information. This work is an effort to analyze some useful datasets and to apply different techniques to associate genes with genetic diseases. Two genetic diseases were studied here: Parkinson’s disease and breast cancer. Using genetic programming, we analyzed the complex network around known disease genes of the aforementioned diseases, and based on that we generated a ranking for genes, based on their relevance to these diseases. In order to generate these rankings, centrality measures of all nodes in the complex network surrounding the known disease genes of the given genetic disease were calculated. Using genetic programming, all the nodes were assigned scores based on the similarity of their centrality measures to those of the known disease genes. Obtained results showed that this method is successful at finding these patterns in centrality measures and the highly ranked genes are worthy as good candidate disease genes for being studied. Using standard benchmark tests, we tested our approach against ENDEAVOUR and CIPHER - two well known disease gene ranking frameworks - and we obtained comparable results.

Communicability across evolving networks

Many natural and technological applications generate time ordered sequences of networks, defined over a fixed set of nodes; for example time-stamped information about ‘who phoned who’ or ‘who came into contact with who’ arise naturally in studies of communication and the spread of disease. Concepts and algorithms for static networks do not immediately carry through to this dynamic setting. For example, suppose A and B interact in the morning, and then B and C interact in the afternoon. Information, or disease, may then pass from A to C, but not vice versa. This subtlety is lost if we simply summarize using the daily aggregate network given by the chain A-B-C. However, using a natural definition of a walk on an evolving network, we show that classic centrality measures from the static setting can be extended in a computationally convenient manner. In particular, communicability indices can be computed to summarize the ability of each node to broadcast and receive information. The computations involve basic operations in linear algebra, and the asymmetry caused by time’s arrow is captured naturally through the non-mutativity of matrix-matrix multiplication. Illustrative examples are given for both synthetic and real-world communication data sets. We also discuss the use of the new centrality measures for real-time monitoring and prediction.

A matrix iteration for dynamic network summaries

We propose a new algorithm for summarizing properties of large-scale time-evolving networks. This type of data, recording connections that come and go over time, is being generated in many modern applications, including telecommunications and on-line human social behavior. The algorithm computes a dynamic measure of how well pairs of nodes can communicate by taking account of routes through the network that respect the arrow of time. We take the conventional approach of downweighting for length (messages become corrupted as they are passed along) and add the novel feature of downweighting for age (messages go out of date). This allows us to generalize widely used Katz-style centrality measures that have proved popular in network science to the case of dynamic networks sampled at non-uniform points in time. We illustrate the new approach on synthetic and real data.

Interventions in social networks: impact on mood and network dynamics

Results from two studies on longitudinal friendship networks are presented, exploring the impact of a gratitude intervention on positive and negative affect dynamics in a social network. The gratitude intervention had been previously shown to increase positive affect and decrease negative affect in an individual but dynamic group effects have not been considered. In the first study the intervention was administered to the whole network. In the second study two social networks are considered and in each only a subset of individuals, initially low/high in negative affect respectively received the intervention as `agents of change'. Data was analyzed using stochastic actor based modelling techniques to identify resulting network changes, impact on positive and negative affect and potential contagion of mood within the group. The first study found a group level increase in positive and a decrease in negative affect. Homophily was detected with regard to positive and negative affect but no evidence of contagion was found. The network itself became more volatile along with a fall in rate of change of negative affect. Centrality measures indicated that the best broadcasters were the individuals with the least negative affect levels at the beginning of the study. In the second study, the positive and negative affect levels for the whole group depended on the initial levels of negative affect of the intervention recipients. There was evidence of positive affect contagion in the group where intervention recipients had low initial level of negative affect and contagion in negative affect for the group where recipients had initially high level of negative affect.

What makes a species central in a cleaning mutualism network?

Mutualisms often form networks of interacting species, characterized by the existence of a central core of species that potentially drive the ecology and the evolution of the whole community. Centrality measures allow quantification of how central or peripheral a species is within a network, thus informing about the role of each species in network organization, dynamics, and stability. In the present study we addressed the question whether the structural position of species in the network (i.e. their topological importance) relates to their ecological traits. We studied interactions between cleaner and client reef fishes to identify central and peripheral species within a mutualistic network, and investigated five ecological correlates. We used three measures to estimate the level of centrality of a species for distinct structural patterns, such as the number of interactions and the structural proximity to other species. Through the use of a principal component analysis (PCA) we observed that the centrality measures were highly correlated (92.5%) in the studied network, which indicates that the same species plays a similar role for the different structural patterns. Three cleaner and ten client species had positive values of centrality, which suggests that these species are modulating ecological and evolutionary dynamics within the network. Higher centralities were related to higher abundances and feeding habits for client fishes, but not for cleaners. The high correlation between centrality measures in the present study is likely related to the nested structure of the cleaning network. The cleaner species` set, by having central species that are not necessarily the most abundant ones, bears potentially more vulnerable points for network cohesiveness. Additionally, the present study generalizes previous findings for plant-animal mutualisms, as it shows that the structure of marine mutualisms is also related to a complex interplay between abundance and niche-related features.

Inferência estatística clássica para a confiabilidade de rede de coautoria com enfoque nos vértices

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)