Randomly Sampling HP-Protein Conformations: Mission Impossible?

Creating random individuals for the HP-protein folding is very hard, if not impossible. This has a big impact on the applicability of genetic algorithms, seemingly making it an intractable method for folding. We will demonstrate this by sampling up to 176,000,000 proteins of lengths on lattice dimensions for two experiments. In the first, we randomly sample conformations until a valid one is found. For the second, we inferred distributions from sampled conformations, which capture the probability of sampling zero-collision conformations. Both results show how the probability of randomly sampling a valid individual decreases exponentially with instance size. This immediately prohibits resampling and the usage of repair mechanisms. One way of creating a valid random individual is through backtracking in exponential time, which is everything but suitable. It is hardly surprising that previous studies only use small instances and fail to report how (often) random samples are created. We will also show how these problems are nonexistent for the Traveling Salesman Problem (TSP), which is also -hard.