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)lookahead ---------------------- stepwhere
nis the length of the chain and
nbrsis 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
lookaheadthis is linear in
n. The bad news is that the constant is exponential in
lookaheadand 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,
lookahead 6 and
step 3 and then again
lookahead 8 and
step 4 (it takes a
fair bit longer). Don't even think about folding this one with brute
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.