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.
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 : ACM Press.
Approximation algorithms for protein folding prediction
MAURI, GIANCARLO;
1999
Abstract
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
