We present a comprehensive survey of combinatorial algorithms and theorems about
lattice protein folding models obtained in the almost 15 years since the publication in 1995 of the
first protein folding approximation algorithm with mathematically guaranteed error bounds.
The results presented here are mainly about the HP-protein folding model introduced by Ken Dill
in 1985. The main topics of this survey include: approximation algorithms for linear-chain and
side-chain lattice models, as well as off-lattice models, NP-completeness theorems about a variety of
protein folding models, contact map structure of self-avoiding walks and HP-folds, combinatorics and
algorithmics for side-chain models, bi-sphere packing and the Kepler conjecture, and the protein sidechain
self-assembly conjecture. As an appealing bridge between the hybrid of continuous mathematics
and discrete mathematics, a cornerstone of the mathematical difficulty of the protein folding problem,
we show how work on 2D self-avoiding walks contact-map decomposition can build upon the
exact RNA contacts counting formula by Mike Waterman and collaborators leading to renewed
hope for analytical closed-form approximations for statistical mechanics of protein folding in lattice
models. We also include in this paper a few new results, research directions within reach of rigorous
results, and a set of open problems that merit future exploration.