The physical mapping is a crucial tool in the analysis of the genomic sequences. Algorithms for the mapping process are based on NP-complete combinatorial optimizations. The problem of reconstructing the probe order is equivalent to the consecutive ones problem. PQ-trees have been extensively used as a suitable data structure to test the consecutive ones property (COP) in the hybridization matrix. This paper presents PQR-trees, an extension of PQ-trees. PQR-trees can advantageously handle partial order information on probes. Moreover, we embed PQR-trees in the more general framework of Constraint Programming (CP). CP is an emergent software technology for declarative description and effective solving of large, particularly combinatorial, problems. We introduce Sequences a new data structure in CP and present filtering algorithms for checking the consistency of sequence constraints based on PQR-trees. We present a canonical form that characterizes a family of sequential arrangements of a given set. The relations we are dealing with are classical sets relations isin, sub, ne, = besides sequencing relations such as group, order, and metric constraints. The filtering algorithms are based on incremental consistency techniques used to reduce the PQR-trees and hence, prune the inconsistencies before the labeling phase. We claim that the sequence structure introduces a flexibility criterion on CP which renders it a suitable tool for solving NP-complete combinatorial optimizations such as physical mapping problem.

By focusing on the families of assignment and permutation problems (such as graph colouring and n-Queens), we show how to adapt D.R. Smith's (1990) KIDS approach for the synthesis of constraint programs (with implicit constraint satisfaction code), rather than applicative Refine programs with explicit constraint propagation and pruning code. Synthesis is guided by a global search schema and can be fully automated with little effort, due to some innovative ideas. CLP (Sets) programs are equivalent in expressiveness to our input specifications. The synthesised CLP (FD) programs would be, after optimising transformations, competitive with carefully hand-crafted ones.

This paper deals with consistency techniques over sequences constraints embedded in Constraint Logic Programming CLPS. CLP Sequences constraints are defined over Hereditarily Homogeneous Finite Sets HHFS built on atomic elements to characterise a family of admissible sequences. The relations we are dealing with are classical sets relations (/spl isin/,/spl sub/,=,/spl ne/) and sequencing relations as potential, metric and range constraints. We define the semantics of these relations with a characteristic range function. The consistency techniques used are incremental reduction of the normal form based on a tree like representation called P-Q-R trees. This allows us to reduce the set of admissible sequences before generating solutions.>