WCB on Wednesday, July 21st

09:00‑10:00 Invited Talk
Chair: Agostino Dovier
Location: AT 2.14
09:00 Alexander Bockmayr
Constraint-based modeling in systems biology
10:30‑12:30 Session I
Chair: Agostino Dovier
Location: AT 2.14
10:30 Pedro Barahona
Minimizing enzymes to diferenciate between species

A large number of species cannot be distinguished via standard non genetic analysis in the lab. In this paper we address the problem of finding a minimum set of restriction enzymes that unequivocally identify an yeast (among a set of possibilities) by analysing the size of the fragments obtained in a set of gel electrophoresis experiments. Although the problem is solved by mapping it into a set covering problem, and the data sets used are relatively small, larger data sets may turn this problem quite difficult to solve, especially in a number of variants discussed in the conclusion. The problem has already raised the interest of our biologist partners, and may become a benchmark for the application of Constraint Programming techniques to Bioinformatics.

11:00 James Cussens
Maximum likelihood pedigree reconstruction using integer programming

The problem of finding the most probable pedigree (`family tree') for a group of related individuals has many applications. In this work pedigrees are encoded as Bayesian networks and then inferred from genetic data using integer programming. Initial results are promising even for large problems as long as reasonable 'extra' constraints are used.

11:30 Aurélie Favier, Jean-Michel Elsen, Simon de Givry and Andrés Legarra
Optimal haplotype reconstruction in half-sib families

In the goal of genetic improvement of livestock by marker assisted selection, we aim at reconstructing the haplotypes of sires from their offspring. We reformulate this problem into a weighted binary constraint satisfaction problem with only equality and disequality soft constraints. Our results show these problems have a small treewidth and can be solved optimally, improving haplotype reconstruction compared to previous approaches especially for small families (<10 descendants).

12:00 Alessandro Dal Palu, Mathias Möhl and Sebastian Will
Alignnment of RNA with Structures of Unlimited Complexity

Sequence-structure alignment of RNAs with arbitrary secondary structures is Max-SNP-hard. Therefore, the problem of RNA alignment is commonly restricted to nested structure, where dynamic programming yields efficient solutions. However, nested structure cannot model pseudoknots or even more complex structural dependencies. Nevertheless those dependencies are essential and conserved features of many RNAs. Only few existing approaches deal with crossings of limited complexity or arbitrary crossing structures. Here, we present a constraint approach for alignment of structures in the even more general class of structures with unlimited complexity. Our central contribution is a new RNA alignment propagator. It is based on an efficient $O(n^2)$ relaxation of the RNA alignment problem. Specifically, our approach Carna solves the alignment problem for sequences with given input structure of unlimited complexity. Carna is implemented using Gecode.

14:00‑15:00 Session II
Chair: Sebastian Will
Location: AT 2.14
14:00 Martin Mann and Alessandro Dal Palu'
Lattice model refinement of protein structures

In this paper we model and implement a Constraint Programming method to rene a lattice tting of a protein structure produced by a greedy search. We show that the model is able to provide better quality solutions. The prototype is implemented in COLA and it is based on a limited discrepancy approach. Finally, some promising extensions based on local search are discussed.

14:30 Alejandro Arbelaez, Youssef Hamadi and Michele Sebag
Building Portfolios for the Protein Structure Prediction Problem

This paper, concerned with the protein structure prediction problem, aims at automatically selecting the Constraint Satisfaction algorithm best suited to the problem instance at hand. The contribution is twofold. Firstly, the selection criterion is the quality (minimal cost) in expectation of the solution found after a fixed amount of time, as opposed to the expected runtime. Secondly, the presented approach, based on supervised Machine Learning algorithms, considers the original description of the protein structure problem, as opposed to the features related to the SAT or CSP encoding of the problem.

15:30‑17:00 Session III
Chair: Alessandro Dal Palù
Location: AT 2.14
15:30 Corinna Heldt and Alexander Bockmayr
Geometric Constraints for the Phase Problem in X-Ray Crystallography

X-ray crystallography is one of the main methods to establish the three-dimensional structure of biological macromolecules. In an X-ray experiment, one can measure only the magnitudes of the complex Fourier coefficients of the electron density distribution under study, but not their phases. The problem of recovering the lost phases is called the phase problem. Building on earlier work by Lunin/Urzhumtsev/Bockmayr, we extend their constraint-based approach to the phase problem by adding additional integer linear programming constraints. These constraints describing topological properties of proteins increase the quality of the solutions of the constraint system. The approach has been implemented using SCIP and CPLEX, first computational results are presented here.

16:00 Takehide Soh and Katsumi Inoue
Finding Minimal Reaction Sets in Large Metabolic Pathways

In systems biology, identifying vital functions like glycolysis from a given metabolic pathway is important to understand living organisms. In this paper, we particularly focus on the problem of finding minimal sub-pathways producing target metabolites from source metabolites. We represent laws of biochemical reactions in propositional formulas and use a state-of-the-art SAT solver as a minimal model generator to solve the problem efficiently. An advantage of our method is that it can treat reversible reactions represented by cycles. Moreover recent advances of SAT technologies enables us to obtain solutions for large pathways. We have applied our method to a whole Escherichia coli pathway. As a result, we found 5 sets of reactions including the conventional glycolysis sub-pathway described in a biological database EcoCyc.

16:30 Luca Bortolussi and Alberto Policriti
Perspectives on Constraints, Process Algebras, and Hybrid Systems

Building on a technique for associating Hybrid Systems (HS) to stochastic programs written in a stochastic extension of Concurrent Constraint Programming (sCCP), we will discuss several aspects of performing such association. In particular, as we proved an sCCP program can be mapped in a HS varying in a lattice at a level depending on the amount of actions to be simulated continuously, we will discuss what are the problems involved in a semi-automatic choice of such level. Decidability, semantic, and efficiency issues will be taken into account, with special emphasis on their links with biological applications. We will also discuss about the role of constraints and of the constraint store is this construction.