Skip Navigation

Liebert Librarian Resource Center

Mary Ann Liebert, Inc. is committed to working closely with librarians to create collections of content that fulfill the informational needs of institutions while providing excellent value.

Journal of Computational Biology

Protein Folding in the Hydrophobic-Hydrophilic (HP) Model is NP-Complete

To cite this article:
BONNIE BERGER and TOM LEIGHTON. Journal of Computational Biology. March 2009, 5(1): 27-40. doi:10.1089/cmb.1998.5.27.

Published in Volume: 5 Issue 1: March 13, 2009

Full Text PDF (1,684 KB)
Full Text PDF with Links (797.4 KB)

Author information

BONNIE BERGERTOM LEIGHTON

ABSTRACT

One of the simplest and most popular biophysical models of protein folding is the hydrophobic-hydrophilic (HP) model. The HP model abstracts the hydrophobic interaction in protein folding by labeling the amino acids as hydrophobic (H for nonpolar) or hydrophilic (P for polar). Chains of amino acids are configured as self-avoiding walks on the 3D cubic lattice, where an optimal conformation maximizes the number of adjacencies between H's. In this paper, the protein folding problem under the HP model on the cubic lattice is shown to be NP-complete. This means that the protein folding problem belongs to a large set of problems that are believed to be computationally intractable.

This paper was cited by:

Discriminating membrane proteins using the joint distribution of length sums of success and failure runs

Sotirios Bersimis, Athanasios Sachlas, Pantelis G. Bagos

Statistical Methods & Applications. Oct 2016

Studying the role of cooperative hydration in stabilizing folded protein states

David J. Huggins

Journal of Structural Biology. Sep 2016

A New Heuristic Algorithm for Protein Folding in the HP Model

Metodi Traykov, Slav Angelov, Nicola Yanev

Journal of Computational Biology. Aug 2016, Vol. 23, No. 8: 662-668

Abstract | Full Text PDF or HTML | Reprints | Permissions | Download Metadata

A Multiagent Ab Initio Protein Structure Prediction Tool for Novices and Experts

Thiago Lipinski-Paes, Michele dos Santos da Silva Tanus, José Fernando Ruggiero Bachega, Osmar Norberto de Souza

. Jan 2016: 163-174

Approximation Algorithms for Three Dimensional Protein Folding

Dipan Lal Shaw, A. S. M. Shohidull Islam, Shuvasish Karmaker, M. Sohel Rahman

. Jan 2016: 274-285

Adaptive free energy sampling in multidimensional collective variable space using boxed molecular dynamics

Mike O'Connor, Emanuele Paci, Simon McIntosh-Smith, David R. Glowacki

Faraday Discuss.. Jan 2016

Emergence and Fundamentality in a Pancomputationalist Universe

Mark Pexton

Minds and Machines. Nov 2015, Vol. 25, No. 4: 301-320

Effect of surface attractive strength on structural transitions of a confined HP lattice protein

Busara Pattanasiri, Ying Wai Li, Thomas Wust, David P Landau

Journal of Physics: Conference Series. Sep 2015, Vol. 640: 012015

An efficient approach for solving the HP protein folding problem based on UEGO

J. M. García-Martínez, E. M. Garzón, J. M. Cecilia, H. Pérez-Sánchez, P. M. Ortigosa

Journal of Mathematical Chemistry. Mar 2015, Vol. 53, No. 3: 794-806

TOPOFOLD, the designed modular biomolecular folds: polypeptide-based molecular origami nanostructures following the footsteps of DNA

Vid Kočar, Sabina Božič Abram, Tibor Doles, Nino Bašić, Helena Gradišar, Tomaž Pisanski, Roman Jerala

Wiley Interdisciplinary Reviews: Nanomedicine and Nanobiotechnology. Mar 2015, Vol. 7, No. 2: 218-237

Emergent Protein Folding Modeled with Evolved Neural Cellular Automata Using the 3D HP Model

José Santos, Pablo Villot, Martin Diéguez

Journal of Computational Biology. Nov 2014, Vol. 21, No. 11: 823-845

Abstract | Full Text PDF or HTML | Reprints | Permissions | Download Metadata

Complete RNA inverse folding: computational design of functional hammerhead ribozymes

I. Dotu, J. A. Garcia-Martin, B. L. Slinger, V. Mechery, M. M. Meyer, P. Clote

Nucleic Acids Research. Oct 2014, Vol. 42, No. 18: 11752-11762

Heuristic ant colony optimization algorithm for predicting the structures of 2D HP model proteins

Zhaoxia Liu, Zaiqiang Yang

. Oct 2014: 719-723

Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice

Catherine C. McGeoch

Synthesis Lectures on Quantum Computing. Jul 2014, Vol. 5, No. 2: 1-93

Boxelization

Yahan Zhou, Shinjiro Sueda, Wojciech Matusik, Ariel Shamir

ACM Transactions on Graphics. Jul 2014, Vol. 33, No. 4: 1-8

MASTERS: A General Sequence-based MultiAgent System for Protein TERtiary Structure Prediction

Thiago Lipinski-Paes, Osmar Norberto de Souza

Electronic Notes in Theoretical Computer Science. Jul 2014, Vol. 306: 45-59

A Novel Offspring Selection Strategy in GAs for Protein Structure Prediction

Shih Chieh Su, Jyh Jong Tsay

. Jun 2014: 1171-1174

A Study on the Energy Transition of All-α Proteins by Molecular Dynamics Simulation

Jiang Zhou-ting, Sun Ting-ting, Wang Ya-nan, Chen Yu-dong, He Zhi-xing, Xu Peng

Acta Polymerica Sinica. Apr 2014, Vol. 014, No. 1: 80-87

Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing

Ryan Babbush, Alejandro Perdomo-Ortiz, Bryan O'Gorman, William Macready, Alan Aspuru-Guzik

. Apr 2014: 201-244

A Firefly-Inspired Method for Protein Structure Prediction in Lattice Models

Brian Maher, Andreas Albrecht, Martin Loomes, Xin-She Yang, Kathleen Steinhöfel

Biomolecules. Mar 2014, Vol. 4, No. 1: 56-75

A multiple minima genetic algorithm for protein structure prediction

Fábio Lima Custódio, Helio J.C. Barbosa, Laurent Emmanuel Dardenne

Applied Soft Computing. Feb 2014, Vol. 15: 88-99

Protein folding and de novo protein design for biotechnological applications

George A. Khoury, James Smadbeck, Chris A. Kieslich, Christodoulos A. Floudas

Trends in Biotechnology. Feb 2014, Vol. 32, No. 2: 99-109

Protein secondary structure optimization using an improved artificial bee colony algorithm based on AB off-lattice model

Bai Li, Ya Li, Ligang Gong

Engineering Applications of Artificial Intelligence. Jan 2014, Vol. 27: 70-79

On Macroscopic Quantum Phenomena in Biomolecules and Cells: From Levinthal to Hopfield

Dejan Raković, Miroljub Dugić, Jasmina Jeknić-Dugić, Milenko Plavšić, Stevo Jaćimovski, Jovan Šetrajčić

BioMed Research International. Jan 2014, Vol. 2014: 1-9

A Parallel Framework for Multipoint Spiral Search in ab Initio Protein Structure Prediction

Mahmood A. Rashid, Swakkhar Shatabda, M. A. Hakim Newton, Md Tamjidul Hoque, Abdul Sattar

Advances in Bioinformatics. Jan 2014, Vol. 2014: 1-17

Computational and Theoretical Methods for Protein Folding

Mario Compiani, Emidio Capriotti

Biochemistry. Dec 2013, Vol. 52, No. 48: 8601-8624

Lattice models with asymmetric propensity matrices for locationally informed protein structure prediction

Colin Kern, Li Liao

. Dec 2013: 90-93

A mathematical model for secondary structure in proteins

Alexey Nikolaev, Saad Mneimneh

. Nov 2013: 1-6

On the performance of internal feedback artificial bee colony algorithm (IF-ABC) for protein secondary structure prediction

Bai Li, Ligang Gong, Yuan Yao

. Oct 2013: 33-38

An Effective Exact Algorithm and a New Upper Bound for the Number of Contacts in the Hydrophobic-Polar Two-Dimensional Lattice Model

Emanuele Giaquinta, Laura Pozzi

Journal of Computational Biology. Aug 2013, Vol. 20, No. 8: 593-609

Abstract | Full Text PDF or HTML | Reprints | Permissions | Download Metadata

Clustered Memetic Algorithm With Local Heuristics for Ab Initio Protein Structure Prediction

Md. Kamrul Islam, Madhu Chetty

IEEE Transactions on Evolutionary Computation. Aug 2013, Vol. 17, No. 4: 558-576

Stability of Proteins Inside a Hydrophobic Cavity

Mithun Radhakrishna, Joseph Grimaldi, Georges Belfort, Sanat K. Kumar

Langmuir. Jul 2013, Vol. 29, No. 28: 8922-8928

Collaborative Parallel Local Search for Simplified Protein Structure Prediction

Mahmood A. Rashid, M.A. Hakim Newton, Md. Tamjidul Hoque, Abdul Sattar

. Jul 2013: 966-973

Amoeba-Inspired Nanoarchitectonic Computing: Solving Intractable Computational Problems Using Nanoscale Photoexcitation Transfer Dynamics

Masashi Aono, Makoto Naruse, Song-Ju Kim, Masamitsu Wakabayashi, Hirokazu Hori, Motoichi Ohtsu, Masahiko Hara

Langmuir. Jun 2013, Vol. 29, No. 24: 7557-7564

A local search embedded genetic algorithm for simplified protein structure prediction

Mahmood A Rashid, M.A.Hakim Newton, Md Tamjidul Hoque, Abdul Sattar

. Jun 2013: 1091-1098

Handling constraints in the HP model for protein structure prediction by multiobjective optimization

Mario Garza-Fabre, Gregorio Toscano-Pulido, Eduardo Rodriguez-Tello

. Jun 2013: 2728-2735

Molecular Self-Assembly of Multifunctional Nanoparticle Composites with Arbitrary Shapes and Functions: Challenges and Strategies

Jin-Woo Kim, Russell Deaton

Particle & Particle Systems Characterization. Feb 2013, Vol. 30, No. 2: 117-132

Protein Kolam: An Artistic Rendition of Molecular Structure Data

S. Balaji, S. Neela

Leonardo. Feb 2013, Vol. 46, No. 1: 24-29

An effective evolutionary algorithm for protein folding on 3D FCC HP model by lattice rotation and generalized move sets

Jyh-Jong Tsay, Shih-Chieh Su

Proteome Science. Jan 2013, Vol. 11, No. Suppl 1: S19

Spiral search: a hydrophobic-core directed local search for simplified PSP on 3D FCC lattice

Mahmood A Rashid, MA Hakim Newton, Md Tamjidul Hoque, Swakkhar Shatabda, Duc Pham, Abdul Sattar

BMC Bioinformatics. Jan 2013, Vol. 14, No. Suppl 2: S16

Generic folding and transition hierarchies for surface adsorption of hydrophobic-polar lattice model proteins

Ying Wai Li, Thomas Wüst, David P. Landau

Physical Review E. Jan 2013, Vol. 87, No. 1

Detailed folding structures of M-lycotoxin-Hc1a and its mutageneses using 2D HP model

Shaomin Yan, Guang Wu

Molecular Simulation. Sep 2012, Vol. 38, No. 10: 809-822

Finding low-energy conformations of lattice protein models by quantum annealing

Alejandro Perdomo-Ortiz, Neil Dickson, Marshall Drew-Brook, Geordie Rose, Alán Aspuru-Guzik

Scientific Reports. Aug 2012, Vol. 2

WANG–LANDAU SIMULATIONS OF ADSORBED AND CONFINED LATTICE PROTEINS

BUSARA PATTANASIRI, YING WAI LI, DAVID P. LANDAU, THOMAS WÜST

International Journal of Modern Physics C. Aug 2012, Vol. 23, No. 08: 1240008

Particle swarm optimization with backtracking in protein structure prediction problem

Nanda Dulal Jana, Jaya Sil

. Aug 2012: 734-738

Heuristic energy landscape paving for protein folding problem in the three-dimensional HP lattice model

Jingfa Liu, Gang Li, Jun Yu, Yonglei Yao

Computational Biology and Chemistry. Jun 2012, Vol. 38: 17-26

Protein structure prediction based on optimal hydrophobic core formation

Rumana Nazmul, Madhu Chetty, Ram Samudrala, David Chalmers

. Jun 2012: 1-9

Parallelism, hybridism and coevolution in a multi-level ABC-GA approach for the protein structure prediction problem

César Manuel Vargas Benitez, Rafael Stubs Parpinelli, Heitor Silvério Lopes

Concurrency and Computation: Practice and Experience. Apr 2012, Vol. 24, No. 6: 635-646

Analysis on folding of misgurin using two-dimensional HP model

Shaomin Yan, Guang Wu

Proteins: Structure, Function, and Bioinformatics. Mar 2012, Vol. 80, No. 3: 764-773

Optimized Wang-Landau sampling of lattice polymers: Ground state search and folding thermodynamics of HP model proteins

Thomas Wüst, David P. Landau

The Journal of Chemical Physics. Jan 2012, Vol. 137, No. 6: 064903

Enhanced Wang Landau sampling of adsorbed protein conformations

Mithun Radhakrishna, Sumit Sharma, Sanat K. Kumar

The Journal of Chemical Physics. Jan 2012, Vol. 136, No. 11: 114114

2-Dimensional HP Folding Structures of Caerin

何健王

Hans Journal of Computational Biology. Jan 2012, Vol. 02, No. 04: 34-41

On Lattice Protein Structure Prediction Revisited

I. Dotu, M. Cebrian, P. Van Hentenryck, P. Clote

IEEE/ACM Transactions on Computational Biology and Bioinformatics. Nov 2011, Vol. 8, No. 6: 1620-1632

Deliver Bioinformatics Services in Public Cloud: Challenges and Research Framework

Xi Sun, Liya Fan, Linlin Yan, Lei Kong, Yang Ding, Changjie Guo, Wei Sun

. Oct 2011: 352-357

Protein-folding simulations of the hydrophobic-hydrophilic model by combining pull moves with energy landscape paving

Jingfa Liu, Gang Li, Jun Yu

Physical Review E. Sep 2011, Vol. 84, No. 3

Monte Carlo simulations of the HP model (the “Ising model” of protein folding)

Ying Wai Li, Thomas Wüst, David P. Landau

Computer Physics Communications. Sep 2011, Vol. 182, No. 9: 1896-1899

Unraveling the Beautiful Complexity of Simple Lattice Model Polymers and Proteins Using Wang-Landau Sampling

T. Wüst, Y. W. Li, D. P. Landau

Journal of Statistical Physics. Aug 2011, Vol. 144, No. 3: 638-651

Comparing alternative energy functions for the HP model of protein structure prediction

Mario Garza-Fabre, Eduardo Rodriguez-Tello, Gregorio Toscano-Pulido

. Jun 2011: 2307-2314

A New Branch and Bound Method for the Protein Folding Problem Under the 2D-HP Model

Sun-Yuan Hsieh, De-Wei Lai

IEEE Transactions on NanoBioscience. Jun 2011, Vol. 10, No. 2: 69-75

Simulating Chemistry Using Quantum Computers

Ivan Kassal, James D. Whitfield, Alejandro Perdomo-Ortiz, Man-Hong Yung, Alán Aspuru-Guzik

Annual Review of Physical Chemistry. May 2011, Vol. 62, No. 1: 185-207

Twin Removal in Genetic Algorithms for Protein Structure Prediction Using Low-Resolution Model

Md Tamjidul Hoque, M Chetty, A Lewis, A Sattar

IEEE/ACM Transactions on Computational Biology and Bioinformatics. Jan 2011, Vol. 8, No. 1: 234-245

Hysteretic Optimization for Protein Folding on the Lattice

Juan Zha, Guo-Qiang Zeng, Yong-Zai Lu

. Dec 2010: 1-4

Extremal optimization for the 3D protein folding based on the lattice model

Juan Zha, Guo-Qiang Zeng, Yong-Zai Lu

. Dec 2010: 246-249

DFS-generated pathways in GA crossover for protein structure prediction

Md Tamjidul Hoque, Madhu Chetty, Andrew Lewis, Abdul Sattar, Vicky M. Avery

Neurocomputing. Aug 2010, Vol. 73, No. 13-15: 2308-2316

A Hybrid EDA for Protein Folding Based on HP Model

Benhui Chen, Jinglu Hu

IEEJ Transactions on Electrical and Electronic Engineering. Jul 2010, Vol. 5, No. 4: 459-466

An adaptive niching EDA based on clustering analysis

Benhui Chen, Jinglu Hu

. Jul 2010: 1-7

Clustered memetic algorithm for protein structure prediction

Md. Kamrul Islam, Madhu Chetty

. Jul 2010: 1-8

Uphill unfolding of native protein conformations in cubic lattices

A.A. Albrecht, L. Kapsokalivas, K. Steinhöfel

Journal of Computational Science. May 2010, Vol. 1, No. 1: 6-12

Protein structure prediction with the 3D-HP side-chain model using a master–slave parallel genetic algorithm

César Manuel Vargas Benítez, Heitor Silvério Lopes

Journal of the Brazilian Computer Society. May 2010, Vol. 16, No. 1: 69-78

Generalized lattice graphs for 2D-visualization of biological information

H. González-Díaz, L.G. Pérez-Montoto, A. Duardo-Sanchez, E. Paniagua, S. Vázquez-Prieto, R. Vilas, M.A. Dea-Ayuela, F. Bolas-Fernández, C.R. Munteanu, J. Dorado, J. Costas, F.M. Ubeira

Journal of Theoretical Biology. Nov 2009, Vol. 261, No. 1: 136-147

Population-based local search for protein folding simulation in the MJ energy model and cubic lattices

L. Kapsokalivas, X. Gan, A.A. Albrecht, K. Steinhöfel

Computational Biology and Chemistry. Aug 2009, Vol. 33, No. 4: 283-294

Study of peptide fingerprints of parasite proteins and drug–DNA interactions with Markov-Mean-Energy invariants of biopolymer molecular-dynamic lattice networks

Lázaro Guillermo Pérez-Montoto, María Auxiliadora Dea-Ayuela, Francisco J. Prado-Prado, Francisco Bolas-Fernández, Florencio M. Ubeira, Humberto González-Díaz

Polymer. Jul 2009, Vol. 50, No. 15: 3857-3870

Inverse Protein Folding in 3D Hexagonal Prism Lattice under HPC Model

Alireza Hadj Khodabakhshi, Ján Maňuch, Arash Rafiey, Arvind Gupta

Journal of Computational Biology. Jun 2009, Vol. 16, No. 6: 769-802

Abstract | Full Text PDF | Reprints | Permissions | Download Metadata

Extremal Optimization for protein folding simulations on the lattice

Hengyun Lu, Genke Yang

Computers & Mathematics with Applications. Jun 2009, Vol. 57, No. 11-12: 1855-1861

A novel EDAs based method for HP model protein folding

Benhui Chen, Long Li, Jinglu Hu

. May 2009: 309-315

Monte Carlo simulations of systems with complex energy landscapes

T. Wüst, D.P. Landau, C. Gervais, Y. Xu

Computer Physics Communications. Apr 2009, Vol. 180, No. 4: 475-479

CPSP-web-tools: a server for 3D lattice protein studies

M. Mann, C. Smith, M. Rabbath, M. Edwards, S. Will, R. Backofen

Bioinformatics. Mar 2009, Vol. 25, No. 5: 676-677

Stable Structure-Approximating Inverse Protein Folding in 2D Hydrophobic-Polar-Cysteine (HPC) Model

Alireza Hadj Khodabakhshi, Ján Maňuch, Arash Rafiey, Arvind Gupta

Journal of Computational Biology. Jan 2009, Vol. 16, No. 1: 19-30

Abstract | Full Text PDF | Reprints | Permissions | Download Metadata

Extended HP Model for Protein Structure Prediction

Tamjidul Hoque, Madhu Chetty, Abdul Sattar

Journal of Computational Biology. Jan 2009, Vol. 16, No. 1: 85-103

Abstract | Full Text PDF | Reprints | Permissions | Download Metadata

Solving 2D HP Protein Folding Problem by Parallel Ant Colonies

Haijuan Guo, Qiang Lu, Jinzhen Wu, Xu Huang, Peide Qian

. Jan 2009: 1-5

A novel clustering based niching EDA for protein folding

Benhui Chen, Jinglu Hu

. Jan 2009: 748-753

A gradient-directed Monte Carlo method for global optimization in a discrete space: Application to protein sequence design and folding

Xiangqian Hu, David N. Beratan, Weitao Yang

The Journal of Chemical Physics. Jan 2009, Vol. 131, No. 15: 154117

Classifying proteinlike sequences in arbitrary lattice protein models using LatPack

Martin Mann, Daniel Maticzka, Rhodri Saunders, Rolf Backofen

HFSP Journal. Dec 2008, Vol. 2, No. 6: 396-404

A New Algorithm for 2D Hydrophobic-Polar Model: An Algorithm Based on Hydrophobic Core in Square Lattice

Wang Wei, Tang Yanlin

Pakistan Journal of Biological Sciences. Dec 2008, Vol. 11, No. 14: 1815-1819

QSAR model for alignment-free prediction of human breast cancer biomarkers based on electrostatic potentials of protein pseudofolding HP-lattice networks

Santiago Vilar, Humberto González-Díaz, Lourdes Santana, Eugenio Uriarte

Journal of Computational Chemistry. Dec 2008, Vol. 29, No. 16: 2613-2622

MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING

BIN FU, SORINEL A. OPRISAN, LIZHE XU

International Journal of Computational Geometry & Applications. Oct 2008, Vol. 18, No. 05: 389-413

Ant colony system approach for protein folding

Stefka Fidanova, Ivan Lirkov

. Oct 2008: 887-891

HP-Lattice QSAR for dynein proteins: Experimental proteomics (2D-electrophoresis, mass spectrometry) and theoretic study of a Leishmania infantum sequence

María Auxiliadora Dea-Ayuela, Yunierkis Pérez-Castillo, Alfredo Meneses-Marcel, Florencio M. Ubeira, Francisco Bolas-Fernández, Kuo-Chen Chou, Humberto González-Díaz

Bioorganic & Medicinal Chemistry. Aug 2008, Vol. 16, No. 16: 7770-7776

Protein Folding in Simplified Models With Estimation of Distribution Algorithms

R. Santana, P. Larranaga, J.A. Lozano

IEEE Transactions on Evolutionary Computation. Aug 2008, Vol. 12, No. 4: 418-438

Stochastic protein folding simulation in the three-dimensional HP-model

A.A. Albrecht, A. Skaliotis, K. Steinhöfel

Computational Biology and Chemistry. Aug 2008, Vol. 32, No. 4: 248-255

Construction of model Hamiltonians for adiabatic quantum computation and its application to finding low-energy conformations of lattice protein models

Alejandro Perdomo, Colin Truncik, Ivan Tubert-Brohman, Geordie Rose, Alán Aspuru-Guzik

Physical Review A. Jul 2008, Vol. 78, No. 1

The HP model of protein folding: A challenging testing ground for Wang–Landau sampling

T. Wüst, D.P. Landau

Computer Physics Communications. Jul 2008, Vol. 179, No. 1-3: 124-127

Differentiation between two-state and multi-state folding proteins based on sequence

Ji-Tao Huang, Jin-Pei Cheng

Proteins: Structure, Function, and Bioinformatics. Jul 2008, Vol. 72, No. 1: 44-49

Classification of voltage-gated K+ ion channels from 3D pseudo-folding graph representation of protein sequences using genetic algorithm-optimized support vector machines

Michael Fernández, Leyden Fernández, Jose Ignacio Abreu, Miguel Garriga

Journal of Molecular Graphics and Modelling. Jun 2008, Vol. 26, No. 8: 1306-1314

Advances on protein folding simulations based on the lattice HP models with natural computing

Xinchao Zhao

Applied Soft Computing. Mar 2008, Vol. 8, No. 2: 1029-1040

Proteomics, networks and connectivity indices

Humberto González-Díaz, Yenny González-Díaz, Lourdes Santana, Florencio M. Ubeira, Eugenio Uriarte

PROTEOMICS. Feb 2008, Vol. 8, No. 4: 750-778

FITTING PROTEIN CHAINS TO CUBIC LATTICE IS NP-COMPLETE

JÁN MAŇUCH, DAYA RAM GAUR

Journal of Bioinformatics and Computational Biology. Feb 2008, Vol. 06, No. 01: 93-106

TA-PFP: A Transgenetic Algorithm to Solve the Protein Folding Problem

Carolina P. Almeida, Richard A. Goncalves, Marco C. Goldbarg, Elizabeth F. G. Goldbarg, Myriam R. Delgado

. Oct 2007: 163-168

Protein folding prediction in 3D FCC HP lattice model using genetic algorithm

Md Tamjidul Hoque, Madhu Chetty, Abdul Sattar

. Sep 2007: 4138-4145

Relating time complexity of protein folding simulation to approximations of folding time

K. Steinhöfel, A. Skaliotis, A.A. Albrecht

Computer Physics Communications. Apr 2007, Vol. 176, No. 7: 465-470

The inverse protein folding problem on 2D and 3D lattices

Piotr Berman, Bhaskar DasGupta, Dhruv Mubayi, Robert Sloan, György Turán, Yi Zhang

Discrete Applied Mathematics. Apr 2007, Vol. 155, No. 6-7: 719-732

An Immune Algorithm for Protein Structure Prediction on Lattice Models

Vincenzo Cutello, Giuseppe Nicosia, Mario Pavone, Jonathan Timmis

IEEE Transactions on Evolutionary Computation. Feb 2007, Vol. 11, No. 1: 101-117

Biopolymer structure simulation and optimization via fragment regrowth Monte Carlo

Jinfeng Zhang, S. C. Kou, Jun S. Liu

The Journal of Chemical Physics. Jan 2007, Vol. 126, No. 22: 225101

Routes are trees: The parsing perspective on protein folding

Julia Hockenmaier, Aravind K. Joshi, Ken A. Dill

Proteins: Structure, Function, and Bioinformatics. Jan 2007, Vol. 66, No. 1: 1-15

Geometric Separators and Their Applications to Protein Folding in the HP-Model

Bin Fu, Wei Wang

SIAM Journal on Computing. Jan 2007, Vol. 37, No. 4: 1014-1029

EFFECTIVE COMPUTATIONAL REUSE FOR ENERGY EVALUATIONS IN PROTEIN FOLDING

EUNICE E. SANTOS, EUGENE SANTOS

International Journal on Artificial Intelligence Tools. Oct 2006, Vol. 15, No. 05: 725-739

Non-Isomorphic Coding in Lattice Model and its Impact for Protein Folding Prediction Using Genetic Algorithm

Md Tamjidul Hoque, Madhu Chetty, Laurence S. Dooley

. Sep 2006: 1-8

Preliminary Steps Towards Protein Folding Prediction Using Reconfigurable Computing

Nilton Armstrong, Heitor Lopes, Carlos Erig Lima

. Sep 2006: 1-7

Ab initio protein fold prediction using evolutionary algorithms: Influence of design and control parameters on performance

Dusan P. Djurdjevic, Mark J. Biggs

Journal of Computational Chemistry. Aug 2006, Vol. 27, No. 11: 1177-1195

Exploring the lower part of discrete polymer model energy landscapes

Michael T Wolfinger, Sebastian Will, Ivo L Hofacker, Rolf Backofen, Peter F Stadler

Europhysics Letters (EPL). May 2006, Vol. 74, No. 4: 726-732

The simulation of the three-dimensional lattice hydrophobic-polar protein folding

Yu-zhen Guo, En-min Feng

The Journal of Chemical Physics. Jan 2006, Vol. 125, No. 23: 234703

Exploration of two-dimensional hydrophobic-polar lattice model by combining local search with elastic net algorithm

Yu-Zhen Guo, En-Min Feng, Yong Wang

The Journal of Chemical Physics. Jan 2006, Vol. 125, No. 15: 154102

A study of density of states and ground states in hydrophobic-hydrophilic protein folding models by equi-energy sampling

S. C. Kou, Jason Oh, Wing Hung Wong

The Journal of Chemical Physics. Jan 2006, Vol. 124, No. 24: 244903

Structure-Approximating Inverse Protein Folding Problem in the 2D HP Model

Arvind Gupta, Ján Maňuch, Ladislav Stacho

Journal of Computational Biology. Dec 2005, Vol. 12, No. 10: 1328-1345

Abstract | Full Text PDF | Reprints | Permissions | Download Metadata

Application of tabu search strategy for finding low energy structure of protein

Jacek Błażewicz, Piotr Łukasiak, Maciej Miłostan

Artificial Intelligence in Medicine. Sep 2005, Vol. 35, No. 1-2: 135-145

An Efficient Algorithm to Compute the Landscape of Locally Optimal RNA Secondary Structures with Respect to the Nussinov–Jacobson Energy Model

P. Clote

Journal of Computational Biology. Feb 2005, Vol. 12, No. 1: 83-101

Abstract | Full Text PDF | Reprints | Permissions | Download Metadata

Exact sequence analysis for three-dimensional hydrophobic-polar lattice proteins

Reinhard Schiemann, Michael Bachmann, Wolfhard Janke

The Journal of Chemical Physics. Jan 2005, Vol. 122, No. 11: 114705

Opportunities for Combinatorial Optimization in Computational Biology

Harvey J. Greenberg, William E. Hart, Giuseppe Lancia

INFORMS Journal on Computing. Aug 2004, Vol. 16, No. 3: 211-231

The complexity of checking consistency of pedigree information and related problems

Luca Aceto, Jens A. Hansen, Anna Ingólfsdóttir, Jacob Johnsen, John Knudsen

Journal of Computer Science and Technology. Jan 2004, Vol. 19, No. 1: 42-59

References

. Oct 2003

Mixed search algorithm for protein folding

Huang Jing, Shi Feng, Zhou Huai-bei

Wuhan University Journal of Natural Sciences. Sep 2003, Vol. 8, No. 3: 765-768

Long proteins with unique optimal foldings in the H-P model

Oswin Aichholzer, David Bremner, Erik D. Demaine, Henk Meijer, Vera Sacristán, Michael Soss

Computational Geometry. May 2003, Vol. 25, No. 1-2: 139-159

Approximate protein folding in the HP side chain model on extended cubic lattices

Volker Heun

Discrete Applied Mathematics. Apr 2003, Vol. 127, No. 1: 163-177

The algorithmics of folding proteins on lattices

Vijay Chandru, Abhi DattaSharma, V.S Anil Kumar

Discrete Applied Mathematics. Apr 2003, Vol. 127, No. 1: 145-161

Protein folding simulations of the hydrophobic–hydrophilic model by combining tabu search with genetic algorithms

Tianzi Jiang, Qinghua Cui, Guihua Shi, Songde Ma

The Journal of Chemical Physics. Jan 2003, Vol. 119, No. 8: 4592

A Combinatorial Toolbox for Protein Sequence Design and Landscape Analysis in the Grand Canonical Model

James Aspnes, Julia Hartling, Ming-Yang Kao, Junhyong Kim, Gauri Shah

Journal of Computational Biology. Oct 2002, Vol. 9, No. 5: 721-741

Abstract | Full Text PDF | Reprints | Permissions | Download Metadata

A new sequential importance sampling method and its application to the two-dimensional hydrophobic–hydrophilic model

Junni L. Zhang, Jun S. Liu

The Journal of Chemical Physics. Jan 2002, Vol. 117, No. 7: 3492

Chapter 20. Bioinformatics in the drug discovery process

Sarah Pollock, Hershel M. Safer

. Jan 2001: 201-210

Evolutionary Monte Carlo for protein folding simulations

Faming Liang, Wing Hung Wong

The Journal of Chemical Physics. Jan 2001, Vol. 115, No. 7: 3374

Circular dichroic constrained structure optimization of homoalanine peptides

Bernd Mayer, Giancarlo Marconi

Journal of Computational Chemistry. Mar 2000, Vol. 21, No. 4: 270-281

Spatial Codes and the Hardness of String Folding Problems

ASHWIN NAYAK, ALISTAIR SINCLAIR, URI ZWICK

Journal of Computational Biology. Jan 1999, Vol. 6, No. 1: 13-36

Abstract | Full Text PDF | Reprints | Permissions | Download Metadata

Algorithmic aspects of protein structure similarity

D. Goldman, S. Istrail, C.H. Papadimitriou

. : 512-521

A Guided Genetic Algorithm for Protein Folding Prediction Using 3D Hydrophobic-Hydrophilic Model

M.T. Hoque, M. Chetty, L.S. Dooley

. : 2339-2346

Visualization of Lattice-Based Protein Folding Simulations

S. Potzsch, G. Scheuermann, P.F. Stadler, M.T. Wolfinger, C. Flamm

. : 89-94

Partially Computed Fitness Function Based Genetic Algorithm for Hydrophobic-Hydrophilic Model

T. Hoque, M. Chetty, L.S. Dooley

. : 291-296

Reducing the computational load of energy evaluations for protein folding

E.E. Santos, E. Santos

. : 79-86

A New Guided Genetic Algorithm for 2D Hydrophobic-Hydrophilic Model to Predict Protein Folding

Md. Tamjidul Hoque, M. Chetty, L.S. Dooley

. : 259-266

An Efficient Algorithm for Computing the Fitness Function of a Hydrophobic-Hydrophilic Model

T. Hoque, M. Chetty, L.S. Dooley

. : 285-290

Inverse protein folding in 2D HP model

A. Gupta, J. Manuch, L. Stacho

. : 302-309

Study of fitness landscapes for the hp model of protein structure prediction

S.D. Flores, J. Smith

. : 2338-2345

Protein structure prediction with co-evolving memetic algorithms

J.E. Smith

. : 2346-2353

Parallel Ant Colony Optimization for 3D Protein Structure Prediction using the HP Lattice Model

D. Chu, M. Till, A. Zomaya

. : 193b-193b

About This Journal... | Subscribe... | Buy Article...

Users who read this article also read

No Access

On the Complexity of Protein Folding

PIERLUIGI CRESCENZI, DEBORAH GOLDMAN, CHRISTOS PAPADIMITRIOU, ANTONIO PICCOLBONI, MIHALIS YANNAKAKIS

Journal of Computational Biology. Mar 2009: 423-465.

Abstract | Full Text PDF | Reprints | Permissions

No Access

Fast Protein Folding in the Hydrophobic–Hydrophilic Model within Three-Eighths of Optimal

WILLIAM E. HART, SORIN C. ISTRAIL

Journal of Computational Biology. Apr 2009: 53-96.

Abstract | Full Text PDF | Reprints | Permissions

No Access

Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model

RICHA AGARWALA, SERAFIM BATZOGLOU, VLADO DANČÍK, SCOTT E. DECATUR, SRIDHAR HANNENHALLI, MARTIN FARACH, S. MUTHUKRISHNAN, STEVEN SKIENA

Journal of Computational Biology. Apr 2009: 275-296.

Abstract | Full Text PDF | Reprints | Permissions

No Access

Robust Proofs of NP-Hardness for Protein Folding: General Lattices and Energy Potentials

WILLIAM E. HART, SORIN ISTRAIL

Journal of Computational Biology. Apr 2009: 1-22.

Abstract | Full Text PDF | Reprints | Permissions

No Access

Extended HP Model for Protein Structure Prediction

Tamjidul Hoque, Madhu Chetty, Abdul Sattar

Journal of Computational Biology. Jan 2009: 85-103.

Abstract | Full Text PDF | Reprints | Permissions

No Access

On the Complexity of Multiple Sequence Alignment

LUSHENG WANG, TAO JIANG

Journal of Computational Biology. Jun 2009: 337-348.

Abstract | Full Text PDF | Reprints | Permissions

Publication Tools

Share & Recommend

Related content in Liebert Online