Finding Patterns in Biochemical Networks
Stéphane Zampelli, Yves Deville, Pierre Dupont · Digital Access to Libraries (Université catholique de Louvain (UCL), l'Université de Namur (UNamur) and the Université Saint-Louis (USL-B)) · 2004
Graph pattern matching is a central problem in many application fields, and may be associated with problems in bioinformatics, such as finding patterns in biochemical networks. This problem can be view as a particular case of labelled subgraph isomorphism (SGI). In this paper, we focus on a constraint programming approach. Two new constraints are introduced to solve this problem. We consider labelled graphs, especially suited for representing biochemical networks, and we propose a constraint exploiting this information. Another constraint considers neighbors within k steps, generalizing the simple neighbor constraint. Experimental results show the potential benefit of the constraints when integrated in a backtracking-based constraint system.