Syracuse

Application of maximal constraint satisfaction problems to RNA folding

Archive ouverte

Gaspin, Christine | Régin, J.C.

Edité par CCSD -

* INRA - Unité de Biométrie, Centre de Toulouse (FRA) Diffusion du document : INRA - Unité de Biométrie, Centre de Toulouse (FRA). International audience. 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.

• Description
• Sujet/Public
• Outil
• Outil d'anticipation
• Mémoire et thèse
• Gestion