Combinatorial Optimization

GaussDCA: Multivariate Gaussian Inference of Protein Contacts from Multiple Sequence Alignment

GaussDCA-julia.tgz25.09 KB
GaussDCA-matlab.tgz24.36 KB

This is the code which accompanies the paper "Fast and accurate multivariate Gaussian modeling of protein families: Predicting residue contacts and protein-interaction partners" by Carlo Baldassi, Marco Zamparo, Christoph Feinauer, Andrea Procaccini, Riccardo Zecchina, Martin Weigt and Andrea Pagnani, (2014) PLoS ONE 9(3): e92721. doi:10.1371/journal.pone.0092721

The code comes in two versions, one for Julia and one for MATLAB. They provide nearly identical funcitionality. The Julia code is slightly faster, and doesn't require compilation of external modules.

Julia code

You can download the Julia code from the attached file "GaussDCA-julia.tgz"; however, the recommended way to obtain the code is by using the command Pkg.clone("https://github.com/carlobaldassi/GaussDCA.jl") in the julia command line. See also the documentation at https://github.com/carlobaldassi/GaussDCA.jl.

Matlab code

You can download the MATLAB code from the attached file "GaussDCA-matlab.tgz", or from https://github.com/carlobaldassi/GaussDCA.matlab. See the README.md file for instructions.

The patient-zero problem with noisy observation

The patient-zero problem consists in finding the initial source of an epidemic outbreak given observations at a later time. In this seminar, I will describe a Bayesian method which is able to infer details on the past history of an epidemics based solely on the topology of the contact network and a single snapshot of partial and noisy observations. The method is built on a Bethe approximation for the posterior distribution, and is inherently exact on tree graphs. Moreover, it can be coupled to a set of equations, based on the variational expression of the Bethe free energy, to find the patient-zero along with maximum-likelihood epidemic parameters.
I will describe the method and some results for simulated epidemics on random graphs, and briefly mention future directions of research in the discrete-time setting, as well as a new method - currently in the test phase - that can perform inference on a continuous time spreading model and deal efficiently with real contact-time data.

Thu, 30/10/2014 - 14:30
Alessandro Ingrosso
HuGeF, Via Nizza 52

A cavity-method based approach to the Steiner tree problem on graphs

The minimum weight Steiner tree problem (MST) is an important combinatorial optimization problem over networks that has applications in a wide range of fields. I will mainly focus my attention on two variants of the problem:
the Vertex-disjoint Steiner trees problem and Edges-disjoint Steiner trees problem on graphs. For each variant I will propose some efficient algorithms based on the Belief Propagation approximation scheme.

Thu, 23/10/2014 - 14:30
Anna Paola Muntoni

RBP algorithm for lossy compression in reduced, ultrasparse GF(q) codes

gf-rbp.tgz24.36 KB

This code implements a novel data compression technique for binary symmetric sources based on the cavity method over GF(q), the Galois Field of order q. We present a scheme of low complexity and near-optimal empirical performance. The compression step is based on a reduction of a sparse low-density parity-check code over GF(q) and is done through the so-called reinforced belief-propagation equations. These reduced codes appear to have a nontrivial geometrical modification of the space of codewords, which makes such compression computationally feasible.

Prize-Collecting Steiner Trees

msgsteiner.tgz6.84 KB
msgsteiner-1.1.tgz10.35 KB

This is the distribution package of MSGSTEINER

The permission to use this software is granted by the authors, Alfredo
Braunstein and Riccardo Zecchina, only on the following 5 conditions:

Syndicate content