poster

Random-walk: a stagnation recovery technique for simplified protein structure prediction

Authors:

Abdul SattarAuthors Info & Claims

BCB '12: Proceedings of the ACM Conference on Bioinformatics, Computational Biology and Biomedicine

Pages 620 - 622

https://doi.org/10.1145/2382936.2383043

Published: 07 October 2012 Publication History

Get Access

Abstract

Protein structure prediction is a challenging optimisation problem to the computer scientists. A large number of existing (meta-)heuristic search algorithms attempt to solve the problem by exploring possible structures and finding the one with minimum free energy. However, these algorithms often get stuck in local minima and thus perform poorly on large sized proteins. In this paper, we present a random-walk based stagnation recovery approach. We tested our approach on tabu-based local search as well as population based genetic algorithms. The experimental results show that, random-walk is very effective for escaping from local minima for protein structure prediction on face-centred-cubic lattice and hydrophobic-polar energy model.

References

[1]

Adam Smith. Protein Misfolding. Nature Reviews Drug Discovery, 426(6968):78--102, December 2003.

Google Scholar

[2]

C. B. Anfinsen. The Principles that Govern the Folding of Protein Chains. Science, 181(4096):223--230, 1973.

Google Scholar

[3]

B. Berger and T. Leightont. Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. Journal of Computational Biology, 5(1):27--40, 1998.

Crossref

Google Scholar

[4]

M. Cebrián, I. Dotú, P. Van Hentenryck, and P. Clote. Protein structure prediction on the face centered cubic lattice by local search. In National Conference on Artificial Intelligence - Volume 1, pages 241--246, 2008.

Digital Library

Google Scholar

[5]

K. A. Dill. Theory for the folding and stability of globular proteins. Biochemistry, 24(6):1501--1509, 1985.

Crossref

Google Scholar

[6]

C. M. Dobso. Protein folding and misfolding. Nature, 426(6968):884--890, 2003.

Crossref

Google Scholar

[7]

T. Hales. A proof of the Kepler conjecture. The Annals of Mathematics, 162(3):1065--1185, 2005.

Crossref

Google Scholar

[8]

M. T. Hoque, M. Chetty, A. Lewis, and A. Sattar. Twin Removal in Genetic Algorithms for Protein Structure Prediction using Low-Resolution Model. Transactions on Computational Biology and Bioinformatics, 8(1):234--245, 2011.

Digital Library

Google Scholar

[9]

N. Lesh, M. Mitzenmacher, and S. Whitesides. A complete and effective move set for simplified protein folding. In Research in Comp. Mol. Biology (RECOMB), 2003.

Digital Library

Google Scholar

[10]

C. Levinthal. Are there pathways for protein folding? Journal of Medical Physics, 65(1):44--45, 1968.

Google Scholar

[11]

The Science Editorial. So Much More to Know. The Science, 309(5731):78--102, July 2005.

Crossref

Google Scholar

Cited By

View all

Newton MZaman RMataeimoghadam FRahman JSattar A(2022)Constraint Guided Beta-Sheet Refinement for Protein Structure PredictionComputational Biology and Chemistry10.1016/j.compbiolchem.2022.107773101:COnline publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1016/j.compbiolchem.2022.107773
Mufassirin MNewton MSattar A(2022)Artificial intelligence for template-free protein structure prediction: a comprehensive reviewArtificial Intelligence Review10.1007/s10462-022-10350-x56:8(7665-7732)Online publication date: 17-Dec-2022
https://doi.org/10.1007/s10462-022-10350-x
Shahriar FNesar AMahbub NShatabda S(2017)EGAGP: An enhanced genetic algorithm for producing efficient graph partitions2017 4th International Conference on Networking, Systems and Security (NSysS)10.1109/NSYSS2.2017.8267792(1-9)Online publication date: Dec-2017
https://doi.org/10.1109/NSYSS2.2017.8267792
Show More Cited By

Index Terms

Random-walk: a stagnation recovery technique for simplified protein structure prediction
1. Applied computing
  1. Life and medical sciences
2. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Protein structure prediction using diversity controlled self-adaptive differential evolution with local search

In this paper, Protein Structure Prediction problem is solved using Diversity Controlled Self-Adaptive Differential Evolution with Local search (DCSaDE-LS). DCSaDE-LS, an improved version of Self-Adaptive Differential Evolution (SaDE), use simple fuzzy ...
Research article: Heuristic-based tabu search algorithm for folding two-dimensional AB off-lattice model proteins

The protein structure prediction problem is a classical NP hard problem in bioinformatics. The lack of an effective global optimization method is the key obstacle in solving this problem. As one of the global optimization algorithms, tabu search (TS) ...
Off-lattice protein structure prediction with homologous crossover
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Ab-initio structure prediction refers to the problem of using only knowledge of the sequence of amino acids in a protein molecule to find spatial arrangements, or conformations, of the amino-acid chain capturing the protein in its biologically-active or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

BCB '12: Proceedings of the ACM Conference on Bioinformatics, Computational Biology and Biomedicine

October 2012

725 pages

ISBN:9781450316705

DOI:10.1145/2382936

General Chair:
Sanjay Ranka
University of Florida
,
Program Chairs:
Tamer Kahveci
University of Florida
,
Mona Singh
Princeton University

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

BCB' 12

Sponsor:

SIGBio

BCB' 12: ACM International Conference on Bioinformatics, Computational Biology and Biomedicine

October 7 - 10, 2012

Florida, Orlando

Acceptance Rates

BCB '12 Paper Acceptance Rate 33 of 159 submissions, 21%;

Overall Acceptance Rate 254 of 885 submissions, 29%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
105
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Newton MZaman RMataeimoghadam FRahman JSattar A(2022)Constraint Guided Beta-Sheet Refinement for Protein Structure PredictionComputational Biology and Chemistry10.1016/j.compbiolchem.2022.107773101:COnline publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1016/j.compbiolchem.2022.107773
Mufassirin MNewton MSattar A(2022)Artificial intelligence for template-free protein structure prediction: a comprehensive reviewArtificial Intelligence Review10.1007/s10462-022-10350-x56:8(7665-7732)Online publication date: 17-Dec-2022
https://doi.org/10.1007/s10462-022-10350-x
Shahriar FNesar AMahbub NShatabda S(2017)EGAGP: An enhanced genetic algorithm for producing efficient graph partitions2017 4th International Conference on Networking, Systems and Security (NSysS)10.1109/NSYSS2.2017.8267792(1-9)Online publication date: Dec-2017
https://doi.org/10.1109/NSYSS2.2017.8267792
Hasanat MHasan MAhmed IChowdhury MFerdous JShatabda S(2016)An ant colony optimization algorithm for load shedding minimization in smart grids2016 5th International Conference on Informatics, Electronics and Vision (ICIEV)10.1109/ICIEV.2016.7759991(176-181)Online publication date: May-2016
https://doi.org/10.1109/ICIEV.2016.7759991
Ferdous JShatabda SHuda M(2015)A tabu-based heuristic optimization algorithm for load shedding minimization2015 International Conference on Advances in Electrical Engineering (ICAEE)10.1109/ICAEE.2015.7506862(332-335)Online publication date: Dec-2015
https://doi.org/10.1109/ICAEE.2015.7506862
Ullah AAhmed NPappu SShatabda SUllah ARahman M(2015) Efficient conformational space exploration in ab initio protein folding simulation Royal Society Open Science10.1098/rsos.1502382:8(150238)Online publication date: Aug-2015
https://doi.org/10.1098/rsos.150238
Rashid MPolash MNewton MHoque MSattar A(2014)Amino Acids Pattern-Biased Spiral Search for Protein Structure PredictionPRICAI 2014: Trends in Artificial Intelligence10.1007/978-3-319-13560-1_12(143-156)Online publication date: 2014
https://doi.org/10.1007/978-3-319-13560-1_12
Rashid MNewton MHoque MShatabda SPham DSattar A(2013)Spiral search: a hydrophobic-core directed local search for simplified PSP on 3D FCC latticeBMC Bioinformatics10.1186/1471-2105-14-S2-S1614:S2Online publication date: 21-Jan-2013
https://doi.org/10.1186/1471-2105-14-S2-S16
Rashid MNewton MHoque MSattar A(2013)Collaborative Parallel Local Search for Simplified Protein Structure PredictionProceedings of the 2013 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications10.1109/TrustCom.2013.118(966-973)Online publication date: 16-Jul-2013
https://dl.acm.org/doi/10.1109/TrustCom.2013.118
Rashid MNewton MHoque MSattar A(2013)A local search embedded genetic algorithm for simplified protein structure prediction2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557688(1091-1098)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557688

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Protein structure prediction using diversity controlled self-adaptive differential evolution with local search

Research article: Heuristic-based tabu search algorithm for folding two-dimensional AB off-lattice model proteins

Off-lattice protein structure prediction with homologous crossover