welcome: please sign in

Revision 5 as of 2011-01-20 14:26:24

Clear message
location: FinalProblemDescriptions / ReverseFolding

Reverse Folding

Contents

  1. Reverse Folding
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Example(s)
    6. Author(s)

Problem Description

This is a simplification of an important Biological problem. A string (e.g., representing a protein) composed of N consecutive elements (defined by the predicate length(N)) at a fixed unitary distance lays on a 2D (cartesian) plane. Admissible angles are 0 (straight line), .90. (left turn) and +90. (right turn). Different elements must occupy different positions. We refer to each placement of the string as a folding. A folding is represented by a predicate fold(I,X,Y) where I in {1,...,N} is the Ith element of the string, and (X,Y) are its coordinates in the plane. You can assume X and Y in {0,...,2N}.

A pivot move is defined by selecting an element i in {2,...,N-1} and its effect is to turn clockwise or counter-clockwise of 90 degrees the part of the string related to the elements i+1,...,N. A move at time t is represented by pivot(t,i,clock) or pivot(t,i,anticlock). Exactly one move occurs at a time t.

The goal is to find (if it exists) a sequence of T moves (T is defined by the predicate time(T)) such that lead the initial straight line fold

fold(1,N,N). fold(2,N,N+1). fold(2,N,N+2). ... fold(N,N,2N-1).

into the fold assigned as input.

Assume the input is: 

fold(1,9,9). 
fold(2,9,10). 
fold(3,9,11). 
fold(4,10,11). 
fold(5,11,11). 
fold(6,11,10). 
fold(7,11,9). 
fold(8,10,9). 
fold(9,10,10). 

length(9). 
time(4).

This means that the the final form of the protein is 

   _ _
  |   | 
  | |_|

Starting from the straight line fold, it is possible to reach that folding with the application of the following pivot moves (which is the expected output from the system): 

pivot(1,3,clock). 
pivot(2,5,clock). 
pivot(3,8,clock). 
pivot(4,7,clock).

Effects of pivot moves 

 | 
 | 
 | 
 | 
 | 
 |    _ _ _ _ _ _    _ _     _ _     _ _ 
 |   |              |   |   |   |   |   | 
 |   |              |   |   |   |   | |_| 
                        |      _| 
                        |

Ideas on modeling with variants of ASP can be found in:
A. Dovier, A. Formisano, E. Pontelli.
Perspectives on Logic-based Approaches for Reasoning About Actions and Change.
To appear in LNCS 6565, Essay in honour of Michael Gelfond
(paper draft available on line)

Predicates

Input format

Output format

Example(s)

Author(s)