Protein Structure Prediction Using Bee Colony Optimization Metaheuristic | Journal of Mathematical Modelling and Algorithms in Operations Research Skip to main content

Advertisement

Springer Nature Link
Log in

Protein Structure Prediction Using Bee Colony Optimization Metaheuristic

  • Published:
Journal of Mathematical Modelling and Algorithms

Abstract

Predicting the native structure of proteins is one of the most challenging problems in molecular biology. The goal is to determine the three-dimensional structure from the one-dimensional amino acid sequence. De novo prediction algorithms seek to do this by developing a representation of the proteins structure, an energy potential and some optimization algorithm that finds the structure with minimal energy. Bee Colony Optimization (BCO) is a relatively new approach to solving optimization problems based on the foraging behaviour of bees. Several variants of BCO have been suggested in the literature. We have devised a new variant that unifies the existing and is much more flexible with respect to replacing the various elements of the BCO. In particular, this applies to the choice of the local search as well as the method for generating scout locations and performing the waggle dance. We apply our BCO method to generate good solutions to the protein structure prediction problem. The results show that BCO generally finds better solutions than simulated annealing which so far has been the metaheuristic of choice for this problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abbass, H.A.: MBO: marriage in honey bees optimization—a haplometrosis polygynous swarming approach. In: Proceedings of the 2001 Congress on Evolutionary Computation CEC2001, pp. 207–214 (2001)

  2. Bahamish, H.A.A., Abdullah, R., Salam, R.A.: Protein conformational search using Bees Algorithm. In: Asia International Conference on Modelling and Simulation, pp. 911–916 (2008)

  3. Boberg, J., Salakoski, T., Vihinen, M.: Selection of a representative set of structures from Brookhaven protein data bank. Proteins 14(2), 265–76 (1992)

    Article  Google Scholar 

  4. Chothia, C., Lesk, A.M.: The relation between the divergence of sequence and structure in proteins. EMBO J. 5, 823–826 (1986)

    Google Scholar 

  5. Hamelryck, T.: An amino acid has two sides: a new 2D measure provides a different view of solvent exposure. J. Proteins Struct. Funct. Bioinf. 59(1), 38–48 (2005)

    Article  Google Scholar 

  6. Hamelryck, T., Kent, J.T., Krogh, A.: Sampling realistic protein conformations using local structural bias. PLOS Computat. Biol. 2, e131 (2006)

    Article  Google Scholar 

  7. Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning. Oper. Res. 37(6), 865–892 (1989)

    Article  MATH  Google Scholar 

  8. Karaboga, D.: An idea based on honey bee swarm for numerical optimization. Technical Report TR06, Erciyes Univ., Engineering Faculty, Computer Engineering Department (2005)

  9. Karaboga, D., Basturk, B.: A powerful and efficient algorithm for numerical function optimization: Artificial Bee Colony (ABC) algorithm. J. Glob. Optim. 39(3), 459–471 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  10. Kryshtafovych, A., Fidelis, K., Moult, J.: Progress from CASP6 to CASP7. Proteins Struct. Funct. Bioinf. 69(S8), 194–207 (2007)

    Article  Google Scholar 

  11. Li, Z., Scheraga, H.A.: Monte Carlo-minimization approach to the multiple-minima problem in protein folding. Proc. Natl. Acad. Sci. 84(19), 6611–6615 (1987)

    Article  MathSciNet  Google Scholar 

  12. Mayuko, T.S., Daisuke, T., Chieko, C., Hirokazu, T., Hideaki, U.: Protein structure prediction in structure based drug design. Curr. Med. Chem. 11(5), 551–558 (2004)

    Article  Google Scholar 

  13. McGuffin, L.J., Bryson, K., Jones, D.T.: The PSIPRED protein structure prediction server. Bioinformatics 16(4), 404–405 (2000)

    Article  Google Scholar 

  14. Paluszewski, M., Hamelryck, T., Winter, P.: Reconstructing protein structure from solvent exposure using tabu search. In: Algorithms for Molecular Biology (ALMOB) (2006)

  15. Paluszewski, M., Winter, P.: EBBA: efficient branch and bound algorithm for protein decoy generation. Technical report. Department of Computer Science, Univ. of Copenhagen, vol. 08(08) (2008)

  16. Paluszewski, M., Winter, P.: Protein decoy generation using branch and bound with efficient bounding. In: Proc. of the 8th Int. Workshop, WABI 2008, LNBI 5251, pp. 382–393 (2008)

  17. Pham, D., Koc, E., Ghanbarzadeh, A., Otri, S., Rahim, S., Zaidi, M., Phrueksanant, J., Lee, J., Sahran, S., Sholedolu, M., Ridley, M., Mahmuddin, M., Al-Jabbouli, H., Darwish, A.H., Soroka, A., Packianather, M., Castellani, M.: The Bees Algorithm—a novel tool for optimisation problems. In: Proceedings of IPROMS 2006 Conference, pp. 454–461 (2006)

  18. Pham, D.T., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S., Zaidi, M.: The Bees Algorithm. Technical report, MEC, Cardiff University, UK (2005)

  19. Rohl, C.A., Strauss, C.E., Misura, K.M., Baker, D.: Protein structure prediction using Rosetta. Methods Enzymol. 383, 66–93 (2004)

    Article  Google Scholar 

  20. Sayle, R.: RasMol v2.5 a molecular visualisation program. Biomol. Struc. Glaxo Research and Development Greenford. Roger Sayle and Biomol. Struct. (1994)

  21. Simons, K.T., Kooperberg, C., Huang, E., Baker, D.: Assembly of protein tertiary structures from fragments with similar local sequences using simulated annealing and Bayesian scoring functions. J. Mol. Biol. 268(1), 209–25 (1997)

    Article  Google Scholar 

  22. Skolnick, J., Kolinski, A., Ortiz, A.R.: MONSSTER: a method for folding globular proteins with a small number of distance restraints. J. Mol. Biol. 265, 217–241 (1997)

    Article  Google Scholar 

  23. Song, J., Takemoto, K., Akutsu, T.: HSEpred: predict half-sphere exposure from protein sequences. Bioinformatics 24, 1489–1497 (2008)

    Article  Google Scholar 

  24. Vilhjalmsson, B., Hamelryck, T.: Predicting a new type of solvent exposure. In: ECCB, Computational Biology Madrid 05, P-C35, Poster (2005)

  25. Yuan, Z.: Better prediction of protein contact number using a support vector regression analysis of amino acid sequence. BMC Bioinf. 6(1), 248 (2005)

    Article  Google Scholar 

  26. Zemla, A., Venclovas, C., Moult, J., Fidelis, K.: Processing and analysis of CASP3 protein structure predictions. Proteins Suppl 3, 22–29 (1999)

    Article  Google Scholar 

  27. Zhang, Y.: I-TASSER server for protein 3D structure prediction. BMC Bioinf. 9(1), 40 (2008)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Copenhagen, Copenhagen, Denmark

    Rasmus Fonseca & Pawel Winter

  2. The Bioinformatics Centre, University of Copenhagen, Copenhagen, Denmark

    Martin Paluszewski

Authors
  1. Rasmus Fonseca
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin Paluszewski
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pawel Winter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rasmus Fonseca.

Additional information

Partially supported by a grant from the Danish Research Counsil (51-00-0336).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fonseca, R., Paluszewski, M. & Winter, P. Protein Structure Prediction Using Bee Colony Optimization Metaheuristic. J Math Model Algor 9, 181–194 (2010). https://doi.org/10.1007/s10852-010-9125-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10852-010-9125-1

Keywords

Search

Navigation