A graph theoretic approach to testing associations between disparate sources of functional genomic data

The last few years have seen the advent of high-throughput technologies to analyze various properties of the transcriptome and proteome of several organisms. The congruency of these different data sources, or lack thereof, can shed light on the mechanisms that govern cellular function. A central challenge for bioinformatics research is to develop a unified framework for combining the multiple sources of functional genomics information and testing associations between them, thus obtaining a robust and integrated view of the underlying biology. We present a graph theoretic approach to test the significance of the association between multiple disparate sources of functional genomics data by proposing two statistical tests, namely edge permutation and node label permutation tests. We demonstrate the use of the proposed tests by finding significant association between a Gene Ontology-derived "predictome" and data obtained from mRNA expression and phenotypic experiments for Saccharomyces cerevisiae. Moreover, we employ the graph theoretic framework to recast a surprising discrepancy presented in Giaever et al. (2002) between gene expression and knockout phenotype, using expression data from a different set of experiments.

Assembling a consistent set of sentences in relational probabilistic logic with stochastic independence

We examine the representation of judgements of stochastic independence in probabilistic logics. We focus on a relational logic where (i) judgements of stochastic independence are encoded by directed acyclic graphs, and (ii) probabilistic assessments are flexible in the sense that they are not required to specify a single probability measure. We discuss issues of knowledge representation and inference that arise from our particular combination of graphs, stochastic independence, logical formulas and probabilistic assessments. (C) 2007 Elsevier B.V. All rights reserved.

Probabilistic logic with independence

This paper investigates probabilistic logics endowed with independence relations. We review propositional probabilistic languages without and with independence. We then consider graph-theoretic representations for propositional probabilistic logic with independence; complexity is analyzed, algorithms are derived, and examples are discussed. Finally, we examine a restricted first-order probabilistic logic that generalizes relational Bayesian networks. (c) 2007 Elsevier Inc. All rights reserved.

Models and tools for value systems analysis in collaborative environments

Dissertation to obtain the degree of Doctor in Electrical and Computer Engineering, specialization of Collaborative Networks

The correlation structure of spatial autoregressions

This paper investigates how the correlations implied by a first-order simultaneous autoregressive (SAR(1)) process are affected by the weights matrix and the autocorrelation parameter. A graph theoretic representation of the covariances in terms of walks connecting the spatial units helps to clarify a number of correlation properties of the processes. In particular, we study some implications of row-standardizing the weights matrix, the dependence of the correlations on graph distance, and the behavior of the correlations at the extremes of the parameter space. Throughout the analysis differences between directed and undirected networks are emphasized. The graph theoretic representation also clarifies why it is difficult to relate properties ofW to correlation properties of SAR(1) models defined on irregular lattices.

Optimized delta expansion for relativistic nuclear models

The optimized delta-expansion is a nonperturbative approach for field theoretic models which combines the techniques of perturbation theory and the variational principle. This technique is discussed in the lambda phi(4) model and then implemented in the Walecka model for the equation of state of nuclear matter. The results obtained with the delta expansion are compared with those obtained with the traditional mean field, relativistic Hartree and Hartree-Fock approximations.

Applied Graph Theory in Computer Vision and Pattern Recognition

This book will serve as a foundation for a variety of useful applications of graph theory to computer vision, pattern recognition, and related areas. It covers a representative set of novel graph-theoretic methods for complex computer vision and pattern recognition tasks. The first part of the book presents the application of graph theory to low-level processing of digital images such as a new method for partitioning a given image into a hierarchy of homogeneous areas using graph pyramids, or a study of the relationship between graph theory and digital topology. Part II presents graph-theoretic learning algorithms for high-level computer vision and pattern recognition applications, including a survey of graph based methodologies for pattern recognition and computer vision, a presentation of a series of computationally efficient algorithms for testing graph isomorphism and related graph matching tasks in pattern recognition and a new graph distance measure to be used for solving graph matching problems. Finally, Part III provides detailed descriptions of several applications of graph-based methods to real-world pattern recognition tasks. It includes a critical review of the main graph-based and structural methods for fingerprint classification, a new method to visualize time series of graphs, and potential applications in computer network monitoring and abnormal event detection.

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.

GENEOs, compactifications, and graphs

Our objective in this thesis is to study the pseudo-metric and topological structure of the space of group equivariant non-expansive operators (GENEOs). We introduce the notions of compactification of a perception pair, collectionwise surjectivity, and compactification of a space of GENEOs. We obtain some compactification results for perception pairs and the space of GENEOs. We show that when the data spaces are totally bounded and endow the common domains with metric structures, the perception pairs and every collectionwise surjective space of GENEOs can be embedded isometrically into the compact ones through compatible embeddings. An important part of the study of topology of the space of GENEOs is to populate it in a rich manner. We introduce the notion of a generalized permutant and show that this concept too, like that of a permutant, is useful in defining new GENEOs. We define the analogues of some of the aforementioned concepts in a graph theoretic setting, enabling us to use the power of the theory of GENEOs for the study of graphs in an efficient way. We define the notions of a graph perception pair, graph permutant, and a graph GENEO. We develop two models for the theory of graph GENEOs. The first model addresses the case of graphs having weights assigned to their vertices, while the second one addresses weighted on the edges. We prove some new results in the proposed theory of graph GENEOs and exhibit the power of our models by describing their applications to the structural study of simple graphs. We introduce the concept of a graph permutant and show that this concept can be used to define new graph GENEOs between distinct graph perception pairs, thereby enabling us to populate the space of graph GENEOs in a rich manner and shed more light on its structure.

The tree cut and merge algorithm for estimation of network reliability

This article presents Monte Carlo techniques for estimating network reliability. For highly reliable networks, techniques based on graph evolution models provide very good performance. However, they are known to have significant simulation cost. An existing hybrid scheme (based on partitioning the time space) is available to speed up the simulations; however, there are difficulties with optimizing the important parameter associated with this scheme. To overcome these difficulties, a new hybrid scheme (based on partitioning the edge set) is proposed in this article. The proposed scheme shows orders of magnitude improvement of performance over the existing techniques in certain classes of network. It also provides reliability bounds with little overhead.

A hybrid approach to multi-agent decision-making

In the aftermath of a large-scale disaster, agents' decisions derive from self-interested (e.g. survival), common-good (e.g. victims' rescue) and teamwork (e.g. fire extinction) motivations. However, current decision-theoretic models are either purely individual or purely collective and find it difficult to deal with motivational attitudes; on the other hand, mental-state based models find it difficult to deal with uncertainty. We propose a hybrid, CvI-JI, approach that combines: i) collective 'versus' individual (CvI) decisions, founded on the Markov decision process (MDP) quantitative evaluation of joint-actions, and ii)joint-intentions (JI) formulation of teamwork, founded on the belief-desire-intention (BDI) architecture of general mental-state based reasoning. The CvI-JI evaluation explores the performance's improvement

Decisions with multiple simultaneous goals and uncertain causal effects

A key aspect of decision-making in a disaster response scenario is the capability to evaluate multiple and simultaneously perceived goals. Current competing approaches to build decision-making agents are either mental-state based as BDI, or founded on decision-theoretic models as MDP. The BDI chooses heuristically among several goals and the MDP searches for a policy to achieve a specific goal. In this paper we develop a preferences model to decide among multiple simultaneous goals. We propose a pattern, which follows a decision-theoretic approach, to evaluate the expected causal effects of the observable and non-observable aspects that inform each decision. We focus on yes-or-no (i.e., pursue or ignore a goal) decisions and illustrate the proposal using the RoboCupRescue simulation environment.