Constrained Path Finding in Biochemical Networks: a Constraint Programming Approach

The analysis of biochemical networks is mainly done using relational or procedural languages. Combining or designing new analyses requires lot of programming effort that cannot be reused for other analyses. To overcome these limitations, we introduce CP(BioNet) a new constraint programming domain for the analysis of biochemical networks. Analyses are formulated using constraints over graph domain variables. The constraints are then solved by a constraint solver designed for biochemical networks. This provides a flexible and powerful approach as simple analyses can then easily be combined to form complex ones. We focus here on constrained path finding, finding a path from node A to node B in a graph with additional constraints, such as requiring this path to include a predefined set of mandatory intermediate nodes. Constraints for path finding are introduced and their implementation (propagators) is described. A prototype is presented and constrained path finding experiments are performed and analyzed to illustrate the benefits of this new approach