How many losses are suffered in the Hydrophobic-Polar protein folding model if we fold randomly?

And how many new incidences (X next to X, not connected by a line) do you see?

CoV2D project home

Folding

A loss occurs when an X is across from an O, either vertically or horizontally, without being connected to it. A win, or incidence, occurs when an X is across from an X, either vertically or horizontally, without being connected to it.

When the URL parameter "choices" is set to 3, you see a sample with the special rule that moving right is not permitted. With this rule, this model is polynomial-time computable by Dynamic Programming: remember how many points are possible for each possible "view" at each length, where a view is the segment still visible to future bits.

For choices=4, the problem: can the number of losses be below a given threshold, is shown to be NP-complete in: 

@article{CGPPY:98,
	author = {Crescenzi, Pierluigi and Goldman, Deborah and Papadimitriou, Christos and Piccolboni, Antonio and Yannakakis, Mihalis},
	year = {1998},
	month = {02},
	pages = {423-65},
	title = {On the Complexity of Protein Folding},
	volume = {5},
	journal = {Journal of Computational Biology : a journal of computational molecular cell biology},
	doi = {10.1089/cmb.1998.5.423}
}
No points can be achieved for words of length at most 3. At length 4, X??X achieves one point. For choices=3, a "local" approach suggested perhaps an optimal fold (at length 50)? (11 points indicated by ~): 
                X
                |
                O
                |
    O-O     O-O X
    | |     | | |
O-O O O O-O O O O
| | | | | | | | |
X~X~X O X~X~X~X O
| | | | | | | | |
O X~X~X~X O O X O
| | | | | | | | |
X~X-X~X O O O X O
|     | | | | | |
X     O-O X-X~X-O
But if we restrict to length 20: (2 points): 
                X
                |
                O
                |
            O-O X
            | | |
            O O O
            | | |
            X~X O
            | | |
            O X O
            | | |
            O X O
            | | |
           -X~X-O
Not optimal since we can also do a 4 points way: 
O-O X-X~X-O-X
| | | | |     
X~X~X~X O  -  
  | | | |     
  O O O O     
  | | | |     
  O-O O-O
so a better choice at length 50 is (12 points): 
    O-O      
    | |       
O-O O O O-O   
| | | | | |   
X~X~X O X~X         X
| | | | | |         |
O X~X~X~X O         O
| | | | | |         |
X~X-X~X O O O-O X-X~X
|     | | | | | | | |
X     O-O X-X~X~X~X O
              | | | |
              O O O O
              | | | |
              O-O O-O