The Workshop on Constraint-based methods for Bioinformatics (WCB) has reached its seventh consecutive edition. This year’s edition was held in the medieval town of Perugia, Italy on the 12th of September as satellite workshop of the CP’11 conference.
By looking at the corpus of contributions gathered in these years (more than fifty papers), we can draw some observations about trends and connections between the constraint area and the modern biology.
In the “Omics” era, the availability of large amount of biological data is made possible by modern experimental techniques and recent advances in the biochemical research area. Non-trivial techniques are required in order to analyze, mine and combine this large piece of information.
Constraint techniques showed to be a valid methodology to tackle the challenge presented by biology. The various papers presented throughout the years at WCB cover different topics that are challenging because of either the large amount of data involved (networks and genes) or the intrinsic complexity (structural problem).
We can identify at least five main categories in which most of the contributions to WCB fall:
- sequence alignment (DNA classification, gene prediction, module identification, etc.),
- RNA secondary structure prediction,
- biological networks (pathways, metabolic and gene regulatory networks, analysis of biological systems, etc.),
- haplotype inference and related problems,
- and protein structure prediction (secondary structure prediction, tertiary structure prediction on-lattice and off-lattice, quaternary structure prediction).
It is also interesting, from the Computer Science point of view, to note that different flavors of constraint-related techniques have been exploited during the recent years. For instance, we mention the use of different popular constraint solvers (such as CLP(FD), Gecode, Comet), as well as the proposals relying on other general logic programming frameworks (such as Answer Set Programming, SAT solvers and Integer Linear Programming solvers, Inductive Logic Programming). At the same time, several search heuristics have been proposed and adopted within approaches based on local search and local neighboring search. From the point of view of programming languages, various applications of Prolog have been employed: BProlog for PRISM applied to Hidden Markov Models, Prolog
for Biochamm and Stochastics Concurrent Constraint Programming to model networks evolution. Moreover, some dedicated constraint solvers have been designed and implemented for specialized constraint handling (Chemera and COLA are significant examples).
The regular contributions were split in three sections and the workshop was opened by an interesting invited talk about mutated genes expressed in tumors titled “Inferring gene pathways controlling clonal outgrowth by high-throughput insertional mutagenesis screens”.
The speaker was Alessandro Brozzi, a biologist of the stituto Europeo di Oncologia in Milan.
Seven papers have been accepted for inclusion in the WCB’11 Proceedings. In the tradition of previous editions of WCB, this contributions emphasize how constraints-based approaches have successful application in a variety of sub-fields of Bioinformatics. More specifically, the first talk was “Petri Nets for Integrated Models of Metabolic and Gene Regulatory Networks”, where Alexander Bockmayr explained how Petri nets can be exploited as a basis for developing a systematic method to support the integrated modeling of metabolic and gene regulation networks.
The second section of the workshop included three talks. Namely, the talk “A New Local Move Operator for Reconstructing Gene Regulatory Networks”, given by Jimmy Vandel, which dealt with the problem of learning the structure of a Bayesian network, in view of potential application to the case of regulatory networks.
Steven Gay gave the talk “A Constraint Program For Subgraph Epimorphisms with Application to Identifying Model Reductions in Systems Biology”, showing how a constraint-based approach to the subgraph epimorphism problem can be used in the biological context to identify meaningful relationships between biochemical reaction graphs.
Finally, in the talk “Declarative Merging of and Reasoning about Decision Diagrams”, Christoph Redl proposed a modular framework to merge decision diagrams in a transparent and declarative way.
An application of the proposed approach, that is based on Answer Set Programming, to the problem of DNA classification is addressed by the contribution.
The remaining three papers composed the last section of the workshop. The first of them was
“Constraints and Global Optimization for Gene Prediction Overlap Resolution”, by Christian Theil Have, and illustrated how to apply Constraint Handling Rules and global optimization to solve the problem of restricting overlapping of gene predictions. Then the talk “Improving Multiple Sequence Alignments with Constraint Programming and Local Search” by Fabio Madeira described a method for a repairing MSA by exploiting constraint programming and local search. The last speaker, Federico Campeotto, reported on the work of a numerous research team working on FIASCO, a declarative constraint-based framework designed to support chemists, biologists, and computer scientists in their analysis of protein conformations. The talk was titled”Introducing FIASCO: Fragment-based Interactive Assembly for protein Structure prediction with COnstraints”.
In conclusion, we would like to thank all colleagues that accepted to serve as members of the Program Committee or as external reviewers and that dedicated their precious time in the reviewing phase. We also would like to thank the Dipartimento di Matematica e Informatica in Perugia for hosting the event and the Committees of the CP conference. In particular, we mention Christian Schulte, the workshops and tutorials chair of CP’11, as well as the conference chair Stefano Bistarelli and the local organization team in Perugia. Finally, we express our gratitude to all the authors that submitted their papers to WCB’11 and to the invited speaker Alessandro Brozzi.
Proceedings, pictures, and other details can be found here: http://www.dmi.unipg.it/WCB11/