int lookahead int step <= lookahead while there are acids to place explore all positions for the next lookahead acids that minimize the energy of configuration so far place the first step of those lookahead acidsThe algorithm decides between ties by choosing to progress in a straight line, insofar as possible. Thus if the sequence is ...-A-B-C-... and B has been placed to the East of A then the algorithm will try to place C in direction E, NE, SE, NW or SW in that preference order on the hexagonal grid. Of course C can't be West of B since A is already there.

When lookahead = step = 1 this is a straightforward greedy algorithm. When step is greater than the length of the chain this is the brute force algorithm.

The time complexity of this algorithm is big-O of

n * (nbrs-1)where^{lookahead}---------------------- step

` n`

is the length of the chain and
` nbrs`

is the
number of neighbors of a cell on the grid. For the hex, square, cubic
and dodecahedral grids that number is 6, 4, 6, 12. The good news is
that for fixed ` step`

and ` lookahead`

this is
linear in ` n`

. The bad news is that the
constant is exponential in ` lookahead`

and can be quite large.
The actual exponent for the hexagonal grid seems to be about 4.4,
which is less than the
bound of 6-1 = 5 but not sufficiently less to make much practical
difference.
(Truth in advertising. There's really a quadratic term too, but the constant there is negligible. And I could probably rewrite that part of the code to make it linear, but it's not worth the effort.)

You might try the incremental algorithm on a random chain of length
50, seed 7676,
with ` lookahead 6`

and ` step 3`

and then again
with ` lookahead 8`

and ` step 4`

(it takes a
fair bit longer). Don't even think about folding this one with brute
force.

The larger the value of lookahead the more global information about the chain can contribute to the final folded shape.

There are biological arguments for and against the appropriateness of the incremental algorithm. Some proteins do seem to fold while they are being constructed. Others can refold themselves into their proper shape even after being completely denatured - that is, straightened out.