Approximation algorithms for protein folding prediction

Mauri, G; Pavesi, G; Piccolboni, A

We present a new polynomial-time algorithm for the protein folding problem in the two-dimensional HP model introduced by Dill [l], which has been recently proved to be NP-hard [2]. Our algorithm guarantees a performance ratio (i.e., the ratio between the energy of the solution found by the algorithm and the optimal one) of l/4, equalling the two best polynomial-time performance guaranteed algorithms for this problem [3]. However, experimental results on a large set of random instances have shown an average performance ratio for our algorithm of 0.67, versus 0.55 and 0.48 for the other two.

We present a new polynomial-time algorithm for the protein folding problem in the two-dimensional HP model introduced by Dill, which has been recently proved to be NP-hard. Our algorithm guarantees a performance ratio (i.e., the ratio between the energy of the solution found by the algorithm and the optimal one) of 1/4, equalling the two best polynomial-time performance guaranteed algorithms for this problem. However, experimental results on a large set of random instances have shown an average performance ratio for our algorithm of 0.67, versus 0.55 and 0.48 for the other two.

Mauri, G., Pavesi, G., Piccolboni, A. (1999). Approximation algorithms for protein folding prediction. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms (pp.945-946). New York : SIAM.