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:
[img]
Preview
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (213Kb)
Google Scholar: Look up in Google Scholar

Abstract

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
Interdisciplinary Research Centre: Centre for Research in Computing (CRC)
Item ID: 10558
Depositing User: Laurence Dooley
Date Deposited: 10 Apr 2008
Last Modified: 02 Jan 2014 14:58
URI: http://oro.open.ac.uk/id/eprint/10558
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk