Filtering algorithms for sequencing constraints: Application in physical mapping

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 ∈, ⊂, ≠, = 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.