ppointer

02.19.14

This entry was posted in Abstracts and tagged Algorithms Bayesian factor graph Kalman Pearl's belief propagation Systems Biology viterbi on by

Factor Graphs and the Sum-Product Algorithm

Frank R. Kschischang, Senior Member, IEEE, Brendan J. Frey, Member, IEEE, and
Hans-Andrea Loeliger, Member, IEEE

Abstract:
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.

04.02.14

This entry was posted in Abstracts and tagged direct dependencies network convolution Systems Biology on by

Network deconvolution as a general method to distinguish direct dependencies in networks

Soheil Feizi, Daniel Marbach, Muriel Médard & Manolis Kellis
Nature Biotechnology 31,726–733 (2013) doi:10.1038/nbt.2635

Last updated: 26 March 2014 19:22:38 EDT

Abstract:

Recognizing direct relationships between variables connected in a network is a pervasive problem in biological, social and information sciences as correlation-based networks contain numerous indirect relationships. Here we present a general method for inferring direct effects from an observed correlation matrix containing both direct and indirect effects. We formulate the problem as the inverse of network convolution, and introduce an algorithm that removes the combined effect of all indirect paths of arbitrary length in a closed-form solution by exploiting eigen-decomposition and infinite-series sums. We demonstrate the effectiveness of our approach in several network applications: distinguishing direct targets in gene expression regulatory networks; recognizing directly interacting amino-acid residues for protein structure prediction from sequence alignments; and distinguishing strong collaborations in co-authorship social networks using connectivity information alone. In addition to its theoretical impact as a foundational graph theoretic tool, our results suggest network deconvolution is widely applicable for computing direct dependencies in network science across diverse disciplines.