RNA Secondary Structure Determination and Representation Based on Constraints Satisfaction

A characteristic common to several problems of molecular biology consists in the satisfaction of a set of constraints coming from different sources of biological knowledge. In this paper, we present two problems that take advantage of a constraint satisfaction formulation. The first problem deals with the representation and visualization of RNA secondary structures. The program RNASEARCH implements an original backtracking based algorithm that evaluates at each node the satisfaction of spatial constraints with the aim at drawing a representation without overlap between secondary structural elements. The second problem addresses the determination of RNA secondary structure in accordance with data. With the program SAPSSARN, the application of classic filtering algorithm is used and we discuss a new search algorithm which computes only so called saturated secondary structures. The main result certainly is the possibility to relax the constraint of the absence of secondary structural elements forbidden in secondary structures computed with dynamic programming based approaches: pseudoknots. Finally, we show how each program takes advantage from the other through a protocol driven by constraints.