I. Introduction
Given the primary sequence of a protein, the problem of protein structure prediction (PSP) refers to finding the protein's native configuration with minimum energy. PSP has been shown to be a NP-hard problem [4], [7] and many approximation methods and heuristics have been investigated to address it [17]. Existing computing approaches to PSP include evolutionary search [1], [3], [15], [16], ant colony optimization [14], memetic algorithms [11], tabu search [12] and Monte Carlo algorithms [9].