Application of maximal constraint satisfaction problems to RNA folding
Résumé
The formalism of constraint satisfaction problems (CSP) applies very well in a number of various applications. However, when it is not possible to compute a complete assignment of variables, Partial CSP or dynamic CSP solving is the alternative. Generally, Branch Bound based algorithms allow to compute solutions maximizing requirements when a cost functiong is available. In this paper, we propose an efficient algorithm allowing to compute all the partial solutions of a CSP in which all the constraints are satisfied when a cost functiong is not available and a given subset of variables must appear in the final assignment. The algorithm is described and experimental results are given for RNA structure determination.