CiteULike: Tag inference

Vision as Bayesian inference: analysis by synthesis?

Alan Yuille — 2006-09-05T15:06:31-00:00

Trends in Cognitive Sciences, Vol. 10, No. 7. (July 2006), pp. 301-308.

We argue that the study of human vision should be aimed at determining how humans perform natural tasks with natural images. Attempts to understand the phenomenology of vision from artificial stimuli, although worthwhile as a starting point, can lead to faulty generalizations about visual systems, because of the enormous complexity of natural images. Dealing with this complexity is daunting, but Bayesian inference on structured probability distributions offers the ability to design theories of vision that can deal with the complexity of natural images, and that use `analysis by synthesis' strategies with intriguing similarities to the brain. We examine these strategies using recent examples from computer vision, and outline some important imlications for cognitive science.

Factor graphs and the sum-product algorithm

FR Kschischang — 2006-01-21T22:06:50-00:00

Information Theory, IEEE Transactions on, Vol. 47, No. 2. (2001), pp. 498-519.

Algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of “local” functions, each of which depends on a subset of the variables. Such a factorization can be visualized with a bipartite graph that we call a factor graph, In this tutorial paper, we present a generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph. Following a single, simple computational rule, the sum-product algorithm computes-either exactly or approximately-various marginal functions derived from the global function. A wide variety of algorithms developed in artificial intelligence, signal processing, and digital communications can be derived as specific instances of the sum-product algorithm, including the forward/backward algorithm, the Viterbi algorithm, the iterative “turbo” decoding algorithm, Pearl's (1988) belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms

Using Multiple Segmentations to Discover Objects and their Extent in Image Collections

Bryan Russell — 2007-11-03T02:57:08-00:00

(2006), pp. 1605-1614.

Dynamic Conditional Random Fields

For Labeling — 2006-12-21T15:02:33-00:00

Conditional random fields (CRFs) for sequence modeling have several advantages over joint models such as HMMs, including the ability to relax strong independence assumptions made in those models, and the ability to incorporate arbitrary overlapping features. Previous work has focused on linear-chain CRFs, which correspond to finite-state machines, and have efficient exact inference algorithms. Often, however, we wish to label sequence data in multiple interacting ways---for example,...

Automatic eyeglasses removal from face images.

C Wu — 2006-07-24T12:52:17-00:00

IEEE Trans Pattern Anal Mach Intell, Vol. 26, No. 3. (March 2004), pp. 322-336.

In this paper, we present an intelligent image editing and face synthesis system that automatically removes eyeglasses from an input frontal face image. Although conventional image editing tools can be used to remove eyeglasses by pixel-level editing, filling in the deleted eyeglasses region with the right content is a difficult problem. Our approach works at the object level where the eyeglasses are automatically located, removed as one piece, and the void region filled. Our system consists of three parts: eyeglasses detection, eyeglasses localization, and eyeglasses removal. First, an eye region detector, trained offline, is used to approximately locate the region of eyes, thus the region of eyeglasses. A Markov-chain Monte Carlo method is then used to accurately locate key points on the eyeglasses frame by searching for the global optimum of the posterior. Subsequently, a novel sample-based approach is used to synthesize the face image without the eyeglasses. Specifically, we adopt a statistical analysis and synthesis approach to learn the mapping between pairs of face images with and without eyeglasses from a database. Extensive experiments demonstrate that our system effectively removes eyeglasses.

Structure-Driven Algorithms for Truth Maintenance

Rina Dechter — 2007-03-18T20:36:40-00:00

Artificial Intelligence, Vol. 82, No. 1-2. (1996), pp. 1-2.

This paper studies truth-maintenance and belief revision tasks on singly-connected structures for the purpose of understanding how structural features could be exploited in such tasks. We present distributed algorithms and show that, in the JTMS framework, both belief revision and consistency maintenance are linear in the size of the knowledgebase on singly connected structures. However, the ATMS task is exponential in the branching degree of the network. The singly-connected model, while...

Readings in Uncertain Reasoning (Morgan Kaufmann Series in Representation and Reasoning)

Glenn Shafer — 2006-01-30T14:05:35-00:00

Probabilistic Reasoning in Intelligent Systems : Networks of Plausible Inference

Judea Pearl — 2005-06-23T10:50:11-00:00

(01 September 1988)

Probabilistic Reasoning in Intelligent Systems is a complete and accessible account of the theoretical foundations and computational methods that underlie plausible reasoning under uncertainty. The author provides a coherent explication of probability as a language for reasoning with partial belief and offers a unifying perspective on other AI approaches to uncertainty, such as the Dempster-Shafer formalism, truth maintenance systems, and nonmonotonic logic. The author distinguishes syntactic and semantic approaches to uncertainty--and offers techniques, based on belief networks, that provide a mechanism for making semantics-based systems operational. Specifically, network-propagation techniques serve as a mechanism for combining the theoretical coherence of probability theory with modern demands of reasoning-systems technology: modular declarative inputs, conceptually meaningful inferences, and parallel distributed computation. Application areas include diagnosis, forecasting, image interpretation, multi-sensor fusion, decision support systems, plan recognition, planning, speech recognition--in short, almost every task requiring that conclusions be drawn from uncertain clues and incomplete information. Probabilistic Reasoning in Intelligent Systems will be of special interest to scholars and researchers in AI, decision theory, statistics, logic, philosophy, cognitive psychology, and the management sciences. Professionals in the areas of knowledge-based systems, operations research, engineering, and statistics will find theoretical and computational tools of immediate practical use. The book can also be used as an excellent text for graduate-level courses in AI, operations research, or applied probability.

WinBUGS – A Bayesian modelling framework: Concepts, structure, and extensibility

David Lunn — 2006-07-28T11:48:30-00:00

Statistics and Computing, Vol. 10, No. 4. (October 2000), pp. 325-337.

Causality: Models, Reasoning, and Inference

Judea Pearl — 2006-01-30T13:58:19-00:00

(13 March 2000)

Written by one of the pre-eminent researchers in the field, this book provides a comprehensive exposition of modern analysis of causation. It shows how causality has grown from a nebulous concept into a mathematical theory with significant applications in the fields of statistics, artificial intelligence, philosophy, cognitive science, and the health and social sciences. Pearl presents a unified account of the probabilistic, manipulative, counterfactual and structural approaches to causation, and devises simple mathematical tools for analyzing the relationships between causal connections, statistical associations, actions and observations. The book will open the way for including causal analysis in the standard curriculum of statistics, artifical intelligence, business, epidemiology, social science and economics. Students in these areas will find natural models, simple identification procedures, and precise mathematical definitions of causal concepts that traditional texts have tended to evade or make unduly complicated. This book will be of interest to professionals and students in a wide variety of fields. Anyone who wishes to elucidate meaningful relationships from data, predict effects of actions and policies, assess explanations of reported events, or form theories of causal understanding and causal speech will find this book stimulating and invaluable.

An evaluation of explanations of probabilistic inference.

HJ Suermondt — 2006-07-28T11:38:13-00:00

Comput Biomed Res, Vol. 26, No. 3. (June 1993), pp. 242-254.

Providing explanations of the conclusions of decision-support systems can be viewed as presenting inference results in a manner that enhances the user's insight into how these results were obtained. The ability to explain inferences has been demonstrated to be an important factor in making medical decision-support systems acceptable for clinical use. Although many researchers in artificial intelligence have explored the automatic generation of explanations for decision-support systems based on symbolic reasoning, research in automated explanation of probabilistic results has been limited. We present the results of an evaluation study of INSITE, a program that explains the reasoning of decision-support systems based on Bayesian belief networks. In the domain of anesthesia, we compared subjects who had access to a belief network with explanations of the inference results to control subjects who used the same belief network without explanations. We show that, compared to control subjects, the explanation subjects demonstrated greater diagnostic accuracy, were more confident about their conclusions, were more critical of the belief network, and found the presentation of the inference results more clear.

Temporal Boolean Network Models of Genetic Networks and Their Inference from Gene Expression Time Series

Adrian Silvescu — 2006-01-30T13:52:02-00:00

Complex Systems, Vol. 13 (2001), pp. 54-70.

This paper motivates and introduces a generalization of the Boolean network model to address dependencies among activity of genes that span for more than one unit of time. The resulting model, called the temporal Boolean network or the TBN(n; k; T ) model, allows the expression of each gene to be controlled by a Boolean function of the expression levels of at most k genes at times in ft t (T 1)g. We apply an adaptation of a popular machine learning algorithm for decision tree induction for...

Development of a system for the inference of large scale genetic networks.

Y Maki — 2006-01-30T13:50:49-00:00

Pac Symp Biocomput (2001), pp. 446-458.

We propose a system named AIGNET (Algorithms for Inference of Genetic Networks), and introduce two top-down approaches for the inference of interrelated mechanism among genes in genetic network that is based on the steady state and temporal analyses of gene expression patterns against some kinds of gene perturbations such as disruption or overexpression. The former analysis is performed by a static Boolean network model based on multi-level digraph, and the latter one is by S-system model. By integrating these two analyses, we show our strategy is flexible and rich in structure to treat gene expression patterns; we applied our strategy to the inference of a genetic network that is composed of 30 genes as a case study. Given the gene expression time-course data set under the conditions of wild-type and the deletion of one gene, our system enabled us to reconstruct the same network architecture as original one.

Bayesian Inference in Cyclical Component Dynamic Linear Models

Mike West — 2006-01-18T12:02:11-00:00

Journal of the American Statistical Association, Vol. 90, No. 432. (???? 1995), pp. 1301-1312.

. This articles discusses developments in Bayesian time series modelling and analysis relevant in studies of time series in the physical and engineering sciences. With illustrations and references, we discuss: Bayesian inference and computation in various state-space models, with examples in analysing quasi-periodic series; isolation and modelling of various components of error in time series; decompositions of time series into significant latent subseries; nonlinear time series models based on ...

Dynamic Bayesian network and nonparametric regression for nonlinear modeling of gene networks from time series gene expression data

Sunyong Kim — 2005-12-19T14:27:30-00:00

Biosystems, Vol. 75, No. 1-3. (July 2004), pp. 57-65.

We propose a dynamic Bayesian network and nonparametric regression model for constructing a gene network from time series microarray gene expression data. The proposed method can overcome a shortcoming of the Bayesian network model in the sense of the construction of cyclic regulations. The proposed method can analyze the microarray data as a continuous data and can capture even nonlinear relations among genes. It can be expected that this model will give a deeper insight into complicated biological systems. We also derive a new criterion for evaluating an estimated network from Bayes approach. We conduct Monte Carlo experiments to examine the effectiviness of the proposed method. We also demonstrate the proposed method through the analysis of the Saccharomyces cerevisiae gene expression data.

Bayesian sequential inference for stochastic kinetic biochemical network models.

A Golightly — 2006-07-26T19:51:08-00:00

J Comput Biol, Vol. 13, No. 3. (April 2006), pp. 838-851.

As postgenomic biology becomes more predictive, the ability to infer rate parameters of genetic and biochemical networks will become increasingly important. In this paper, we explore the Bayesian estimation of stochastic kinetic rate constants governing dynamic models of intracellular processes. The underlying model is replaced by a diffusion approximation where a noise term represents intrinsic stochastic behavior and the model is identified using discrete-time (and often incomplete) data that is subject to measurement error. Sequential MCMC methods are then used to sample the model parameters on-line in several data-poor contexts. The methodology is illustrated by applying it to the estimation of parameters in a simple prokaryotic auto-regulatory gene network.

How to infer gene networks from expression profiles

Mukesh Bansal — 2007-02-21T21:52:28-00:00

Mol Syst Biol, Vol. 3 (13 February 2007)

Reconstructing gene-regulatory networks from time series, knock-out data, and prior knowledge

Florian Geier — 2007-02-03T19:13:44-00:00

BMC Systems Biology, Vol. 1, No. 1. (2007)

BACKGROUND:Cellular processes are controlled by gene-regulatory networks. Several computational methods are currently used to learn the structure of gene-regulatory networks from data. This study focusses on time series gene expression and gene knock-out data in order to identify the underlying network structure. We compare the performance of different network reconstruction methods using synthetic data generated from an ensemble of reference networks. Data requirements as well as optimal experiments for the reconstruction of gene-regulatory networks are investigated. Additionally, the impact of prior knowledge on network reconstruction as well as the effect of unobserved cellular processes is studied. RESULTS:We identify linear Gaussian dynamic Bayesian networks and variable selection based on F-statistics as suitable methods for the reconstruction of gene-regulatory networks from time series data. Commonly used discrete dynamic Bayesian networks perform inferior and this result can be attributed to the inevitable information loss by discretization of expression data. It is shown that short time series generated under transcription factor knock-out are optimal experiments in order to reveal the structure of gene regulatory networks. Relative to the level of observational noise, we give estimates for the required amount of gene expression data in order to accurately reconstruct gene-regulatory networks. The benefit of using of prior knowledge within a Bayesian learning framework is found to be limited to conditions of small gene expression data size. Unobserved processes, like protein-protein interactions, induce dependencies between gene expression levels similar to direct transcriptional regulation. We show that these dependencies cannot be distinguished from transcription factor mediated gene regulation on the basis of gene expression data alone. CONCLUSIONS:Currently available data size and data quality make the reconstruction of gene networks from gene expression data a challenge. In this study, we identify an optimal type of experiment, requirements on the gene expression data quality and size as well as appropriate reconstruction methods in order to reverse engineer gene regulatory networks from time series data.

Inference in belief networks: A procedural guide

C Huang — 2006-07-13T17:43:20-00:00

International Journal of Approximate Reasoning, Vol. 15, No. 3. (1996), pp. 225-263.

Belief networks are popular tools for encoding uncertainty in expert systems. These networks rely on inference algorithms to compute beliefs in the context of observed evidence. One established method for exact inference on belief networks is the Probability Propagation in Trees of Clusters (PPTC) algorithm, as developed by Lauritzen and Spiegelhalter and refined by Jensen et al. PPTC converts the belief network into a secondary structure, then computes probabilities by manipulating the...

The Factored Frontier Algorithm for Approximate Inference in DBNs

Kevin Murphy — 2006-07-13T17:12:37-00:00

pp. 378-385.

The Factored Frontier (FF) algorithm is a simple approximate inference algorithm for Dynamic Bayesian Networks (DBNs). It is very similar to the fully factorized version of the Boyen-Koller (BK) algorithm, but instead of doing an exact update at every step followed by marginalisation (projection), it always works with factored distributions. Hence it can be applied to models for which the exact update step is intractable. We show that FF is equivalent to (one iteration of) loopy belief...

Query DAGs: A Practical Paradigm for Implementing Belief-Network Inference

Adnan Darwiche — 2006-07-13T17:11:55-00:00

Journal of Artificial Intelligence Research, Vol. 6 (1997), pp. 147-176.

We describe a new paradigm for implementing inference in belief networks, which consists of two steps: (1) compiling a belief network into an arithmetic expression called a Query DAG (Q-DAG); and (2) answering queries using a simple evaluation algorithm. Each node of a Q-DAG represents a numeric operation, a number, or a symbol for evidence. Each leaf node of a Q-DAG represents the answer to a network query, that is, the probability of some event of interest. It appears that Q-DAGs can be...

Inference and Learning in Hybrid Bayesian Networks

Kevin Murphy — 2006-07-13T16:58:43-00:00

No. CSD-98-990. (November, 1998)

We survey the literature on methods for inference and learning in Bayesian Networks composed of discrete and continuous nodes, in which the continuous nodes have a multivariate Gaussian distribution, whose mean and variance depends on the values of the discrete nodes. We also briefly consider hybrid Dynamic Bayesian Networks, an extension of switching Kalman filters. This report is meant to summarize what is known at a sufficient level of detail to enable someone to implement the algorithms,...

Inferring causal relationships among intermediate phenotypes and biomarkers: a case study of rheumatoid arthritis.

W Li — 2006-09-02T10:33:08-00:00

Bioinformatics, Vol. 22, No. 12. (15 June 2006), pp. 1503-1507.

MOTIVATION: Genetic association analysis is based on statistical correlations which do not assign any cause-to-effect arrows between the two correlated variables. Normally, such assignment of cause and effect label is not necessary in genetic analysis since genes are always the cause and phenotypes are always the effect. However, among intermediate phenotypes and biomarkers, assigning cause and effect becomes meaningful, and causal inference can be useful. RESULTS: We show that causal inference is possible by an example in a study of rheumatoid arthritis. With the help of genotypic information, the shared epitope, the causal relationship between two biomarkers related to the disease, anti-cyclic citrullinated peptide (anti-CCP) and rheumatoid factor (RF) has been established. We emphasize the fact that third variable must be a genotype to be able to resolve potential ambiguities in causal inference. Two non-trivial conclusions have been reached by the causal inference: (1) anti-CCP is a cause of RF and (2) it is unlikely that a third confounding factor contributes to both anti-CCP and RF.

From correlation to causation networks: a simple approximate learning algorithm and its application to high-dimensional plant gene expression data

Rainer Rhein — 2007-08-06T15:19:38-00:00

BMC Systems Biology, Vol. 1, No. 1. (2007)

BACKGROUND:The use of correlation networks is widespread in the analysis of gene expression and proteomics data, even though it is known that correlations not only confound direct and indirect associations but also provide no means to distinguish between cause and effect. For 'causal' analysis typically the inference of a directed graphical model is required. However, this is rather difficult due to the curse of dimensionality.RESULTS:We propose a simple heuristic for the statistical learning of a high-dimensional 'causal' network. The method first converts a correlation network into a partial correlation graph. Subsequently, a partial ordering of the nodes is established by multiple testing of the log-ratio of standardized partial variances. This allows identifying a directed acyclic causal network as a subgraph of the partial correlation network. We illustrate the approach by analyzing a large Arabidopsis thaliana expression data set. CONCLUSIONS:The proposed approach is a heuristic algorithm that is based on a number of approximations, such as substituting lower order partial correlations by full order partial correlations. Nevertheless, for small samples and for sparse networks the algorithm not only yields sensible first order approximations of the causal structure in high-dimensional genomic data but is also computationally highly efficient. Availability and requirements: The method is implemented in the GeneNet R package (version 1.2.0), available from CRAN and from http://strimmerlab.org/software/genets/. The software includes an R script for reproducing the network analysis of the Arabidopsis thaliana data.

Inferring Transcriptional Regulatory Networks from High-throughput Data.

Rui-Sheng Wang — 2007-09-26T06:06:05-00:00

Bioinformatics (22 September 2007)

MOTIVATION: Inferring the relationships between transcription factors (TFs) and their targets has utmost importance for understanding the complex regulatory mechanisms in cellular systems. However, the transcription factor activities (TFAs) cannot be measured directly by standard microarray experiment owing to various posttranslational modifications. In particular, cooperative mechanism and combinatorial control are common in gene regulation, e.g. TFs usually recruit other proteins cooperatively to facilitate transcriptional reaction processes. RESULTS: In this paper, we propose a novel method for inferring transcriptional regulatory networks (TRN) from gene expression data based on protein transcription complexes and mass action law. With gene expression data and TFAs estimated from transcription complex information, the inference of TRN is formulated as a linear programming problem which has a globally optimal solution in terms ofL(1) norm error. The proposed method not only can easily incorporate ChIP-Chip data as prior knowledge but also can integrate multiple gene expression datasets from different experiments simultaneously. A unique feature of our method is to take into account protein cooperation in transcription process. We tested our method by using both synthetic data and several experimental datasets in yeast. The extensive results illustrate the effectiveness of the proposed method for predicting transcription regulatory relationships between TFs with co-regulators and target genes. AVAILABILITY: The software TRNinfer is available from http://intelligent.eic.osaka-sandai.ac.jp/chenen/TRNinfer.htm. CONTACT: chen@eic.osaka-sandai.ac.jp, zxs@amt.ac.cn.

Adaptively inferring human transcriptional subnetworks.

D Das — 2007-02-13T19:37:50-00:00

Mol Syst Biol, Vol. 2 (2006)

Although the human genome has been sequenced, progress in understanding gene regulation in humans has been particularly slow. Many computational approaches developed for lower eukaryotes to identify cis-regulatory elements and their associated target genes often do not generalize to mammals, largely due to the degenerate and interactive nature of such elements. Motivated by the switch-like behavior of transcriptional responses, we present a systematic approach that allows adaptive determination of active transcriptional subnetworks (cis-motif combinations, the direct target genes and physiological processes regulated by the corresponding transcription factors) from microarray data in mammals, with accuracy similar to that achieved in lower eukaryotes. Our analysis uncovered several new subnetworks active in human liver and in cell-cycle regulation, with similar functional characteristics as the known ones. We present biochemical evidence for our predictions, and show that the recently discovered G2/M-specific E2F pathway is wider than previously thought; in particular, E2F directly activates certain mitotic genes involved in hepatocellular carcinomas. Additionally, we demonstrate that this method can predict subnetworks in a condition-specific manner, as well as regulatory crosstalk across multiple tissues. Our approach allows systematic understanding of how phenotypic complexity is regulated at the transcription level in mammals and offers marked advantage in systems where little or no prior knowledge of transcriptional regulation is available.

Importance of input perturbations and stochastic gene expression in the reverse engineering of genetic regulatory networks: insights from an identifiability analysis of an in silico network.

DE Zak — 2005-11-17T20:52:33-00:00

Genome Res, Vol. 13, No. 11. (November 2003), pp. 2396-2405.

Gene expression profiles are an increasingly common data source that can yield insights into the functions of cells at a system-wide level. The present work considers the limitations in information content of gene expression data for reverse engineering regulatory networks. An in silico genetic regulatory network was constructed for this purpose. Using the in silico network, a formal identifiability analysis was performed that considered the accuracy with which the parameters in the network could be estimated using gene expression data and prior structural knowledge (which transcription factors regulate which genes) as a function of the input perturbation and stochastic gene expression. The analysis yielded experimentally relevant results. It was observed that, in addition to prior structural knowledge, prior knowledge of kinetic parameters, particularly mRNA degradation rate constants, was necessary for the network to be identifiable. Also, with the exception of cases where the noise due to stochastic gene expression was high, complex perturbations were more favorable for identifying the network than simple ones. Although the results may be specific to the network considered, the present study provides a framework for posing similar questions in other systems.

Probabilistic inference of molecular networks from noisy data sources

Ivan Iossifov — 2007-03-07T10:40:59-00:00

Bioinformatics, Vol. 20, No. 8. (22 May 2004), pp. 1205-1213.

Summary: Information on molecular networks, such as networks of interacting proteins, comes from diverse sources that contain remarkable differences in distribution and quantity of errors. Here, we introduce a probabilistic model useful for predicting protein interactions from heterogeneous data sources. The model describes stochastic generation of protein-protein interaction networks with real-world properties, as well as generation of two heterogeneous sources of protein-interaction information: research results automatically extracted from the literature and yeast two-hybrid experiments. Based on the domain composition of proteins, we use the model to predict protein interactions for pairs of proteins for which no experimental data are available. We further explore the prediction limits, given experimental data that cover only part of the underlying protein networks. This approach can be extended naturally to include other types of biological data sources. 10.1093/bioinformatics/bth061

Inference of disease-related molecular logic from systems-based microarray analysis.

V Varadan — 2006-11-03T16:26:12-00:00

PLoS Comput Biol, Vol. 2, No. 6. (16 June 2006)

Computational analysis of gene expression data from microarrays has been useful for medical diagnosis and prognosis. The ability to analyze such data at the level of biological modules, rather than individual genes, has been recognized as important for improving our understanding of disease-related pathways. It has proved difficult, however, to infer pathways from microarray data by deriving modules of multiple synergistically interrelated genes, rather than individual genes. Here we propose a systems-based approach called Entropy Minimization and Boolean Parsimony (EMBP) that identifies, directly from gene expression data, modules of genes that are jointly associated with disease. Furthermore, the technique provides insight into the underlying biomolecular logic by inferring a logic function connecting the joint expression levels in a gene module with the outcome of disease. Coupled with biological knowledge, this information can be useful for identifying disease-related pathways, suggesting potential therapeutic approaches for interfering with the functions of such pathways. We present an example providing such gene modules associated with prostate cancer from publicly available gene expression data, and we successfully validate the results on additional independently derived data. Our results indicate a link between prostate cancer and cellular damage from oxidative stress combined with inhibition of apoptotic mechanisms normally triggered by such damage.

Tree-based reparameterization framework for analysis of belief propagation and related algorithms

M Wainwright — 2005-12-02T19:14:14-00:00

(2003)

We present a tree-based reparameterization (TRP) framework that provides a new conceptual view of a large class of algorithms for computing approximate marginals in graphs with cycles. This class includes the belief propagation (BP) or sum-product algorithm as well as variations and extensions of BP. Algorithms in this class can be formulated as a sequence of reparameterization updates, each of which entails refactorizing a portion of the distribution corresponding to an acyclic subgraph (i.e., ...

Information Theory, Inference & Learning Algorithms

David Mackay — 2005-03-26T08:56:32-00:00

(15 June 2002)

Information theory and inference, often taught separately, are here united in one entertaining textbook. These topics lie at the heart of many exciting areas of contemporary science and engineering - communication, signal processing, data mining, machine learning, pattern recognition, computational neuroscience, bioinformatics, and cryptography. This textbook introduces theory in tandem with applications. Information theory is taught alongside practical communication systems, such as arithmetic coding for data compression and sparse-graph codes for error-correction. A toolbox of inference techniques, including message-passing algorithms, Monte Carlo methods, and variational approximations, are developed alongside applications of these tools to clustering, convolutional codes, independent component analysis, and neural networks. The final part of the book describes the state of the art in error-correcting codes, including low-density parity-check codes, turbo codes, and digital fountain codes -- the twenty-first century standards for satellite communications, disk drives, and data broadcast. Richly illustrated, filled with worked examples and over 400 exercises, some with detailed solutions, David MacKay's groundbreaking book is ideal for self-learning and for undergraduate or graduate courses. Interludes on crosswords, evolution, and sex provide entertainment along the way. In sum, this is a textbook on information, communication, and coding for a new generation of students, and an unparalleled entry point into these subjects for professionals in areas as diverse as computational biology, financial engineering, and machine learning.

Inferring protein interactions from phylogenetic distance matrices.

J Gertz — 2006-04-24T09:25:53-00:00

Bioinformatics, Vol. 19, No. 16. (1 November 2003), pp. 2039-2045.

Finding the interacting pairs of proteins between two different protein families whose members are known to interact is an important problem in molecular biology. We developed and tested an algorithm that finds optimal matches between two families of proteins by comparing their distance matrices. A distance matrix provides a measure of the sequence similarity of proteins within a family. Since the protein sets of interest may have dozens of proteins each, the use of an efficient approximate solution is necessary. Therefore the approach we have developed consists of a Metropolis Monte Carlo optimization algorithm which explores the search space of possible matches between two distance matrices. We demonstrate that by using this algorithm we are able to accurately match chemokines and chemokine-receptors as well as the tgfbeta family of ligands and their receptors.

Inferring network mechanisms: the Drosophila melanogaster protein interaction network.

M Middendorf — 2006-06-29T21:35:34-00:00

Proc Natl Acad Sci U S A, Vol. 102, No. 9. (1 March 2005), pp. 3192-3197.

Naturally occurring networks exhibit quantitative features revealing underlying growth mechanisms. Numerous network mechanisms have recently been proposed to reproduce specific properties such as degree distributions or clustering coefficients. We present a method for inferring the mechanism most accurately capturing a given network topology, exploiting discriminative tools from machine learning. The Drosophila melanogaster protein network is confidently and robustly (to noise and training data subsampling) classified as a duplication-mutation-complementation network over preferential attachment, small-world, and a duplication-mutation mechanism without complementation. Systematic classification, rather than statistical study of specific properties, provides a discriminative approach to understand the design of complex networks.

Inferring subnetworks from perturbed expression profiles.

Dana Pe’er — 2005-12-29T17:13:32-00:00

Bioinformatics, Vol. 17 Suppl 1 (2001)

Genome-wide expression profiles of genetic mutants provide a wide variety of measurements of cellular responses to perturbations. Typical analysis of such data identifies genes affected by perturbation and uses clustering to group genes of similar function. In this paper we discover a finer structure of interactions between genes, such as causality, mediation, activation, and inhibition by using a Bayesian network framework. We extend this framework to correctly handle perturbations, and to identify significant subnetworks of interacting genes. We apply this method to expression data of S. cerevisiae mutants and uncover a variety of structured metabolic, signaling and regulatory pathways.

Modelling regulatory pathways in E. coli from time series expression profiles.

IM Ong — 2005-12-29T17:12:29-00:00

Bioinformatics, Vol. 18 Suppl 1 (2002)

MOTIVATION: Cells continuously reprogram their gene expression network as they move through the cell cycle or sense changes in their environment. In order to understand the regulation of cells, time series expression profiles provide a more complete picture than single time point expression profiles. Few analysis techniques, however, are well suited to modelling such time series data. RESULTS: We describe an approach that naturally handles time series data with the capabilities of modelling causality, feedback loops, and environmental or hidden variables using a Dynamic Bayesian network. We also present a novel way of combining prior biological knowledge and current observations to improve the quality of analysis and to model interactions between sets of genes rather than individual genes. Our approach is evaluated on time series expression data measured in response to physiological changes that affect tryptophan metabolism in E. coli. Results indicate that this approach is capable of finding correlations between sets of related genes.

Influence of network topology and data collection on network inference.

VA Smith — 2005-12-29T17:06:32-00:00

Pac Symp Biocomput (2003), pp. 164-175.

We recently developed an approach for testing the accuracy of network inference algorithms by applying them to biologically realistic simulations with known network topology. Here, we seek to determine the degree to which the network topology and data sampling regime influence the ability of our Bayesian network inference algorithm, NETWORKINFERENCE, to recover gene regulatory networks. NETWORKINFERENCE performed well at recovering feedback loops and multiple targets of a regulator with small amounts of data, but required more data to recover multiple regulators of a gene. When collecting the same number of data samples at different intervals from the system, the best recovery was produced by sampling intervals long enough such that sampling covered propagation of regulation through the network but not so long such that intervals missed internal dynamics. These results further elucidate the possibilities and limitations of network inference based on biological data.

Inferring cellular networks using probabilistic graphical models.

Nir Friedman — 2005-02-21T19:04:10-00:00

Science, Vol. 303, No. 5659. (6 February 2004), pp. 799-805.

High-throughput genome-wide molecular assays, which probe cellular networks from different perspectives, have become central to molecular biology. Probabilistic graphical models are useful for extracting meaningful biological insights from the resulting data sets. These models provide a concise representation of complex cellular networks by composing simpler submodels. Procedures based on well-understood principles for inferring such models from data facilitate a model-based methodology for analysis and discovery. This methodology and its capabilities are illustrated by several recent applications to gene expression data.

Incorporating biological knowledge into evaluation of causal regulatory hypotheses.

L Chrisman — 2005-12-29T16:35:27-00:00

Pac Symp Biocomput (2003), pp. 128-139.

Biological data can be scarce and costly to obtain. The small number of samples available typically limits statistical power and makes reliable inference of causal relations extremely difficult. However, we argue that statistical power can be increased substantially by incorporating prior knowledge and data from diverse sources. We present a Bayesian framework that combines information from different sources and we show empirically that this lets one make correct causal inferences with small sample sizes that otherwise would be impossible.

An Introduction to Bayesian Reference Analysis: Inference on the Ratio of Multinomial Parameters

Jose Bernardo — 2006-04-10T00:51:54-00:00

This paper offers an introduction to Bayesian reference analysis, often described as the more successful method to produce non-subjective, model-based, posterior distributions. The ideas are illustrated in detail with an interesting problem, the ratio of multinomial parameters, for which no model-based Bayesian analysis has been proposed. Signposts are provided to the huge related literature.

A new dynamic Bayesian network (DBN) approach for identifying gene regulatory networks from time course microarray data.

M Zou — 2007-02-05T18:08:38-00:00

Bioinformatics, Vol. 21, No. 1. (1 January 2005), pp. 71-79.

MOTIVATION: Signaling pathways are dynamic events that take place over a given period of time. In order to identify these pathways, expression data over time are required. Dynamic Bayesian network (DBN) is an important approach for predicting the gene regulatory networks from time course expression data. However, two fundamental problems greatly reduce the effectiveness of current DBN methods. The first problem is the relatively low accuracy of prediction, and the second is the excessive computational time. RESULTS: In this paper, we present a DBN-based approach with increased accuracy and reduced computational time compared with existing DBN methods. Unlike previous methods, our approach limits potential regulators to those genes with either earlier or simultaneous expression changes (up- or down-regulation) in relation to their target genes. This allows us to limit the number of potential regulators and consequently reduce the search space. Furthermore, we use the time difference between the initial change in the expression of a given regulator gene and its potential target gene to estimate the transcriptional time lag between these two genes. This method of time lag estimation increases the accuracy of predicting gene regulatory networks. Our approach is evaluated using time-series expression data measured during the yeast cell cycle. The results demonstrate that this approach can predict regulatory networks with significantly improved accuracy and reduced computational time compared with existing DBN approaches.

A Bayesian connectivity-based approach to constructing probabilistic gene regulatory networks.

X Zhou — 2007-02-05T17:59:53-00:00

Bioinformatics, Vol. 20, No. 17. (22 November 2004), pp. 2918-2927.

MOTIVATION: We have hypothesized that the construction of transcriptional regulatory networks using a method that optimizes connectivity would lead to regulation consistent with biological expectations. A key expectation is that the hypothetical networks should produce a few, very strong attractors, highly similar to the original observations, mimicking biological state stability and determinism. Another central expectation is that, since it is expected that the biological control is distributed and mutually reinforcing, interpretation of the observations should lead to a very small number of connection schemes. RESULTS: We propose a fully Bayesian approach to constructing probabilistic gene regulatory networks (PGRNs) that emphasizes network topology. The method computes the possible parent sets of each gene, the corresponding predictors and the associated probabilities based on a nonlinear perceptron model, using a reversible jump Markov chain Monte Carlo (MCMC) technique, and an MCMC method is employed to search the network configurations to find those with the highest Bayesian scores to construct the PGRN. The Bayesian method has been used to construct a PGRN based on the observed behavior of a set of genes whose expression patterns vary across a set of melanoma samples exhibiting two very different phenotypes with respect to cell motility and invasiveness. Key biological features have been faithfully reflected in the model. Its steady-state distribution contains attractors that are either identical or very similar to the states observed in the data, and many of the attractors are singletons, which mimics the biological propensity to stably occupy a given state. Most interestingly, the connectivity rules for the most optimal generated networks constituting the PGRN are remarkably similar, as would be expected for a network operating on a distributed basis, with strong interactions between the components.

Inferring dynamic architecture of cellular networks using time series of gene expression, protein and metabolite data.

E Sontag — 2005-02-16T13:10:55-00:00

Bioinformatics, Vol. 20, No. 12. (12 August 2004), pp. 1877-1886.

MOTIVATION: High-throughput technologies have facilitated the acquisition of large genomics and proteomics datasets. However, these data provide snapshots of cellular behavior, rather than help us reveal causal relations. Here, we propose how these technologies can be utilized to infer the topology and strengths of connections among genes, proteins and metabolites by monitoring time-dependent responses of cellular networks to experimental interventions. RESULTS: We demonstrate that all connections leading to a given network node, e.g. to a particular gene, can be deduced from responses to perturbations none of which directly influences that node, e.g. using strains with knock-outs to other genes. To infer all interactions from stationary data, each node should be perturbed separately or in combination with other nodes. Monitoring time series provides richer information and does not require perturbations to all nodes. Overall, the methods we propose are capable of deducing and quantifying functional interactions within and across cellular gene, signaling and metabolic networks. SUPPLEMENTARY INFORMATION: Supplementary material is available at http://www.dbi.tju.edu/bioinformatics2004.pdf

Reconstructing biological networks using conditional correlation analysis.

JJ Rice — 2007-02-05T17:47:59-00:00

Bioinformatics, Vol. 21, No. 6. (March 2005), pp. 765-773.

MOTIVATION: One of the present challenges in biological research is the organization of the data originating from high-throughput technologies. One way in which this information can be organized is in the form of networks of influences, physical or statistical, between cellular components. We propose an experimental method for probing biological networks, analyzing the resulting data and reconstructing the network architecture. METHODS: We use networks of known topology consisting of nodes (genes), directed edges (gene-gene interactions) and a dynamics for the genes' mRNA concentrations in terms of the gene-gene interactions. We proposed a network reconstruction algorithm based on the conditional correlation of the mRNA equilibrium concentration between two genes given that one of them was knocked down. Using simulated gene expression data on networks of known connectivity, we investigated how the reconstruction error is affected by noise, network topology, size, sparseness and dynamic parameters. RESULTS: Errors arise from correlation between nodes connected through intermediate nodes (false positives) and when the correlation between two directly connected nodes is obscured by noise, non-linearity or multiple inputs to the target node (false negatives). Two critical components of the method are as follows: (1) the choice of an optimal correlation threshold for predicting connections and (2) the reduction of errors arising from indirect connections (for which a novel algorithm is proposed). With these improvements, we can reconstruct networks with the topology of the transcriptional regulatory network in Escherichia coli with a reasonably low error rate.

Causal Protein-Signaling Networks Derived from Multiparameter Single-Cell Data

Karen Sachs — 2005-07-15T13:15:06-00:00

Science, Vol. 308, No. 5721. (22 April 2005), pp. 523-529.

Machine learning was applied for the automated derivation of causal influences in cellular signaling networks. This derivation relied on the simultaneous measurement of multiple phosphorylated protein and phospholipid components in thousands of individual primary human immune system cells. Perturbing these cells with molecular interventions drove the ordering of connections between pathway components, wherein Bayesian network computational methods automatically elucidated most of the traditionally reported signaling relationships and predicted novel interpathway network causalities, which we verified experimentally. Reconstruction of network models from physiologically relevant primary single cells might be applied to understanding native-state tissue signaling biology, complex drug actions, and dysfunctional signaling in diseased cells.

Learning the Structure of Dynamic Probabilistic Networks

Nir Friedman — 2006-01-19T03:03:15-00:00

(1999), pp. 139-147.

Dynamic probabilistic networks are a compact representation of complex stochastic processes. In this paper we examine how to learn the structure of a DPN from data. We extend structure scoring rules for standard probabilistic networks to the dynamic case, and showhow to search for structure whensome of the variables are hidden. Finally, we examine two applications where such a technology might be useful: predicting and classifying dynamic behaviors, and learning causal orderings in biological...

Bayesian network analysis of signaling networks: a primer.

D Pe'er — 2006-01-19T03:00:32-00:00

Sci STKE, Vol. 2005, No. 281. (26 April 2005)

High-throughput proteomic data can be used to reveal the connectivity of signaling networks and the influences between signaling molecules. We present a primer on the use of Bayesian networks for this task. Bayesian networks have been successfully used to derive causal influences among biological signaling molecules (for example, in the analysis of intracellular multicolor flow cytometry). We discuss ways to automatically derive a Bayesian network model from proteomic data and to interpret the resulting model.

Inferring dynamic credentials for r&\#244;le-based trust management

Daniele Gorla — 2007-11-14T06:57:41-00:00

(2006), pp. 213-224.

Modality conflicts in semantics aware access control

Ernesto Damiani — 2007-11-14T06:49:38-00:00

(2006), pp. 249-256.

A Modal Logic for Role-Based Access Control

Thumrongsak Kosiyatrakul — 2007-11-14T06:55:35-00:00

Computer Network Security (2005), pp. 179-193.

Making correct access-control decisions is central to security, which in turn requires accounting correctly for the identity, credentials, roles, authority, and privileges of users and their agents. In networked systems, these decisions are made more complex because of delegation and differing access-control policies. Methods for reasoning rigorously about access control and computer-assisted reasoning tools for verification are effective for providing assurances of security. In this paper we extend the access-control logic of [11,1] to also support reasoning about role-based access control (RBAC), which is a popular technique for reducing the complexity of assigning privileges to users. The result is an access-control logic which is simple enough for design and verification engineers to use to assure the correctness of systems with access-control requirements but yet powerful enough to reason about delegations, credentials, and trusted authorities. We explain how to describe RBAC components such as user assignments, permission assignments, role inheritance, role activations, and users’ requests. The logic and its extensions are proved to be sound and implemented in the HOL (Higher Order Logic version 4) theorem prover. We also provide formal support for RBAC’s static separation of duty and dynamic separation of duty constraints in the HOL theorem prover. As a result, HOL can be used to verify properties of RBAC access-control policies, credentials, authority, and delegations.

Hybrid role hierarchy for generalized temporal role based access control model

JBD Joshi — 2007-11-17T03:41:18-00:00

Computer Software and Applications Conference, 2002. COMPSAC 2002. Proceedings. 26th Annual International (2002), pp. 951-956.

A generalized temporal role based access control (GTRBAC) model that captures an exhaustive set of temporal constraint needs for access control has been proposed. GTRBAC's language constructs allow one to specify various temporal constraints on role, user-role assignments and role-permission assignments. We present the notion of different types of role hierarchies based on the permission-inheritance and role activation semantics. In particular, we look at how new hierarchical relations between a pair of roles that are not directly related can be derived through other well-defined hierarchically related roles. When the different hierarchy types coexist in a role hierarchy, inferring such derived hierarchical relations between a pair of roles can be complex. The results presented provide a basis for formally analyzing the derived inheritance and activation semantics between every pair of roles in a hierarchy.