Bioinformatics
Institute of Computer Science
University Freiburg
de

Constraint-based Methods in Bioinformatics

Constraints are an extremely successful technology that has a vast application area throughout informatics. Due to our expertise in both areas, constraint technology and bioinformatics, we are especially interested in the application of constraints to biological problems. In the area of Bioinformatics, constraints already were succesfully applied to problems related to All these problems can be naturally formalized using constraints over finite domains or intervals of reals.

Recently, we showed how the fundamental bioinformatics problem of sequence alignment can be solved by modern inference based constraint methods. The in-depth study of constrained-based protein structure prediction by our group promoted the development of new search strategies and, in particular, general symmetry breaking.

Constrained alignment using constraint-based inference

In this area, we investigate the application of constraint techniques to the alignment problem. Our focus is to allow for a more declarative form in order to incorporate biological knowledge.

Recently, we succeeded in constructing a constraint-model for sequence alignment that can be efficiently evaluated using the inference-based constraint solving strategy of Cluster Tree Elimination. At the same time the model can be extended by additional constraints (in order to incorporate biolgical prior knowledge) and is still efficiently solved.

Current Status

Hitherto, our work results in a general framework for constrained alignment where almost arbitrary constraints can be imposed and even combined arbitrarily. Possible constraints range from all the constraints that were discussed for sequence alignment before up to complex structural constraints.

A web server for constrained alignment is in preparation.

Contributing group members

Main Publications

Funding

Related Research Topics

General Symmetry Breaking

In constraint programming as well as in bioinformatics, solving search problems that contain lots of symmetries is a frequent task. (For example, in protein folding, symmetries are rotations, reflections and translation of a conformation). These symmetries blow up the search tree and search times. We first encountered the problem of breaking the symmetries in protein structure prediction. In this project we are interested in general schemes for symmetry breaking and identifying interesting sub-classes of symmetries. Furthermore we are interested in applying symmetry breaking to problems of bioinformatics.

Current Status

We have developed the first general method for breaking arbitrary symmetries. This method is based on dynamic insertion of symmetry breaking constraints during constraint-based search.

nqueens

Breaking a 90 degree rotation in 4-queens.

Besides handling geometrical symmetries and permutation symmetries, we identified the subclass of partial symmetries and showed how the approach can break them too.

Contributing group members

Main Publications

Related Research Topics

Dynamic decomposition during search

The counting of solutions of a given Constraint Satisfaction Problem (CSP) is much more complex than deciding on satisfiability and gained much interest in the last time. The solving of a CSP is in general NP-complete, whereby counting all solutions is even harder and in the complexity class #P.
Standard solving methods in constraint programming like Depth-First Search (DFS) combined with constraint propagation are well suited for determining one solution, but leave room for saving redundant work when counting all solutions. Here, we present a method that is especially tailored for this case.

DDFS example

Basically, our new method dynamically decomposes the constraint (sub-)problems that emerge during the search into independent partial problems along connected components of the problem’s associated constraint graph. Separate counting in the partial problems still allows to infer the number of solutions of the complete problem. This technique is known as AND/OR-search and was introduced by Dechter et al.
Instead of statically exploiting only properties of the initial constraint graph, dynamic strategies analyze the emerging constraint graphs during the search and employ their features. We believe this is a major advantage in many constraint problems. In particular, if the initial constraint network is very dense (as in our structure prediction problem), static methods don’t make an impact.

Current Status

We have integrated AND/OR-search into a full features constraint programming system utilizing the benefits of global constraints and dynamic search heuristics. It was implemented using the free constraint programming library Gecode and will be part of the official release.

Contributing group members

Main Publications

Funding

Related Research Topics