Stephane Zampelli, Martin Mann, Yves Deville, Rolf Backofen
Technical Report, Universite catholique de Louvain, 2008
In the constraint programming framework, state-of-the-art static and dynamic decomposition techniques are hard to apply to prob- lems with complete initial constraint graphs. For such problems, we pro- pose a hybrid approach of these techniques in the presence of global constraints. In particular, we solve the subgraph isomorphism problem. Further we design specific heuristics for this hard problem, exploiting its special structure to achieve decomposition. The underlying idea is to pre- compute a static heuristic on a subset of its constraint network, to follow this static ordering until a first problem decomposition is available, and to switch afterwards to a fully propagated, dynamically decomposing search. Experimental results show that, for sparse graphs, our decom- position method solves more instances than dedicated, state-of-the-art matching algorithms or standard constraint programming approaches.
Stephane Zampelli, Martin Mann, Yves Deville, R. Backofen
In: Proc. of the 4th Journées Francophones de Programmation par Contraintes (JFPC'08), 2008
French article about the use of Decomposition During Search (DDS) when solving the subgraph monomorphism problem with CP. An english version of the article is available at http://arxiv.org/abs/0805.1030v1
Andreas S. Richter, Sebastian Will, Rolf Backofen
In: Antonios Kyriakopoulos, Bernhard Michalke, Alexandra Graebert, Gabriele Beschnidt, Proceedings of the European Conference on Metallobiolomics (HMI Berlin, Germany, 2007), 2008, 27-38
The folding of biopolymers is crucially determined by the properties and the topology of the underlying energy landscape. A reduced representation of these energy landscapes is provided by barrier trees, which can be used to study the dynamical behavior of the folding. We presented a generic, problem-independent approach for the generation of barrier trees of discrete biopolymer models. In contrast to previous studies, the approach used does not rely on enumeration, which is limited to smaller molecules due to the amount of available memory. The algorithm has been applied to RNA and a lattice protein. The results show that the approach can be used to compute both all local minima and the exact barrier tree of an energy landscape. The presented method does not restrict the investigated conformation space to certain regions.
Martin Mann, Guido Tack, Sebastian Will
Technical Report, ALU Freiburg, 2007
We describe decomposition during search (DDS), an inte- gration of and/or tree search into propagation-based constraint solvers. The presented search algorithm dynamically decomposes sub-problems of a constraint satisfaction problem into independent partial problems, avoiding redundant work. The paper discusses how DDS interacts with key features that make propagation-based solvers successful: constraint propagation, especially for global constraints, and dynamic search heuristics. We have implemented DDS for the Gecode constraint programming li- brary. Two applications, solution counting in graph coloring and protein structure prediction, exemplify the benefits of DDS in practice.
Martin Mann, Guido Tack, Sebastian Will
Technical Report, ALU Freiburg, 2007
We describe decomposition during search (DDS) as a novel search algorithm for counting the solutions of a CSP. DDS enhances standard tree search by dynamically decomposing sub-problems into independent problems, avoiding redundant work. The paper provides formal definitions and analysis of the introduced method. We integrate DDS into a modern constraint programming system, using Gecode as an example. Two applications, graph coloring and protein structure prediction, show the potential for huge benefits of DDS in practice.
Rolf Backofen
In: Companion Volume to the Proceedings of the 39th Annual Meeting of the Association for Computational Linguistic (ACL), 2001
No Abstract available
Rolf Backofen, David Gilbert
In: Constraints, 2001, 6, 141-156
This article introduces the topic of bioinformatics to an audience of computer scientists. We discuss the definition of bioinformatics, give a classification of the problem areas which bioinformatics addresses, and illustrate these in detail with examples. We highlight those areas which we believe to be suitable for the application of constraint solving techniques, or where similar techniques are already used. Finally, we give some advice for computer scientists who are considering getting involved in bioinformatics, and provide a resource list and a reading list. Keywords: bioinformatics, computational biology, molecular biology, constraints, databases, algorithms, classification, alignment, comparison, patterns, genome, DNA, RNA, proteins, metabolic pathways, regulatory networks, phylogenetic trees
Rolf Backofen, Sebastian Will
Technical Report 9810, Ludwig-Maximilians-Universität München, Institut für Informatik, 1998
In this paper, we describe an exact algorithm for solving the structure prediction problem for the HPNX-alphabet. To our knowledge, our algorithm is the first exact one for finding the minimal conformation of an lattice protein in a lattice model with an alphabet more complex than HP.
Rolf Backofen, Peter Clote
Bericht 9609, Institut für Informatik, LMU, December 1996
Given a finite set K of lethal genes, a starting genome x and a desired target genome y, is there a sequence of base insertions, deletions, and substitutions, which from x produces the desired genome y, and such that no intermediate genome contains a lethal gene. The main result of this paper is that, appropriately formulated, this problem is undecidable, even when the underlying alphabet has only 2 symbols (e.g. two of the bases A,C,G,T). We prove that asexual evolutionary systems form a universal computation engine, in the sense that for any reversible Turing machine M and input x, there is a finite set K of lethal genes, which can guide the computation, so that all intermediate genomes are prefixes of (encodings of) configurations in the computation of M. Since reversible Turing machines retain the history of their entire computation, and are essentially encoded by evolutionary systems, this suggests a encoding mechanism by which phylogeny recapitulates ontogeny.
H. Alshawi, D. J. Arnold, R. Backofen, D. M. Carter, J. Lindop, K. Netter, S. G. Pulman, J. Tsujii, H. Uszkoreit
Final Report, SRI International, 1991
No Abstract available