The Open UniversitySkip to content

Fast Computation of the Fitness Function for Protein Folding Prediction in a 2D Hydrophobic-Hydrophilic Model

Houqe, M. T.; Chetty, M. and Dooley, L. (2005). Fast Computation of the Fitness Function for Protein Folding Prediction in a 2D Hydrophobic-Hydrophilic Model. International Journal of Simulation Systems, Science & Technology, 6(10-11) pp. 27–37.

Full text available as:
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (213Kb)
Google Scholar: Look up in Google Scholar


Protein Folding Prediction (PFP) is essentially an energy minimization problem formalised by the definition of a fitness function. Several PFP models have been proposed including the Hydrophobic-Hydrophilic (HP) model, which is widely used as a test-bed for evaluating new algorithms. The calculation of the fitness is the major computational task in determining the native conformation of a protein in the HP model and this paper presents a new efficient search algorithm (ESA) for deriving the fitness value requiring only O(n) complexity in contrast to the full search approach, which takes O(n2). The improved efficiency of ESA is achieved by exploiting some intrinsic properties of the HP model, with a resulting reduction of more than 50% in the overall time complexity when compared with the previously reported Caching Approach, with the added benefit that the additional space complexity is linear instead of quadratic.

Item Type: Journal Article
ISSN: 1473-804X
Extra Information: Special Issue on: Soft Computing for Modeling and Simulation
Keywords: HP Model; Fitness Function; Improved Computation; Relative Distance and Polarity;
Academic Unit/Department: Mathematics, Computing and Technology > Computing & Communications
Mathematics, Computing and Technology
Interdisciplinary Research Centre: Centre for Research in Computing (CRC)
Item ID: 10558
Depositing User: Laurence Dooley
Date Deposited: 10 Apr 2008
Last Modified: 23 Feb 2016 22:19
Share this page:

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

▼ Automated document suggestions from open access sources

Actions (login may be required)

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340