SweConsNet'04 Invited talk

CLP(BioNet) : Towards a CLP framework for the analysis of Biochemical Networks
Yves Deville, Université catholique Louvain (Belgium)

Abstract

Biochemical networks such as metabolic, regulatory or signal transduction pathways can be viewed as interconnected processes forming an intricate network of functional and physical interactions between molecular species in the cell. The amount of information available in such networks is increasing very rapidly. This is offering the possibility of performing various analyses on the structure of the full network of pathways for one organism as well as across different organisms, and has therefore generated interest in developing databases for storing this information, and methods for analyzing such networks. Analyzing these networks remains however far from straight forward due to the nature of the biological networks, which are often very large, heterogeneous, incomplete, or inconsistent. The analysis of biological networks is hence a challenging problem in systems biology, in bioinformatics, and in computer science.

Various forms of data models have been devised for the representation and for the analysis of biochemical networks (e.g. bipartite graphs). An object-oriented model, which is the basis of the aMAZE database for the representation of biochemical processes, will be presented. A biochemical network represented in this framework can then be transformed into a generalized graph, where nodes and arcs have attributes. Such graphs can be used for the visualization of the network as well as for its analysis.

The constraint programming framework is an attractive framework for the analysis of biochemical networks because most of the analyses can be expressed as a set of basic constraints on (extended) graphs, and various domain expertise can also be described by constraints. CLP(BioNet) is a first attempt to explicitly propose biological networks, represented by a specific form of graphs, as the underlying domain of a constraint system. Constraints, such as PathConstraint, form the basic constraints of the system. A specific analysis can then be expressed by combining basic constraints.

A first prototype of CLP(BioNet) is being developed. It is implemented in Oz. It uses finite domains and ideas from finite sets. Different graph algorithms are used to ensure the incrementality and the propagation of the constraints. This approach is also tested on real biochemical networks. The specification of analysis criteria as well as the analysis of the results is done in collaboration with biologists.