Enhancing search space diversity in multi-objective evolutionary drug molecule design using niching

ABSTRACT

There exist several applications of multi-objective evolutionary algorithms for drug design, however, a common drawback in recent approaches is that the diversity of resulting molecule populations is relatively low. This paper seeks to overcome this problem by introducing niching as a technique to enhance search space diversity. A single population approach with dynamic niche identification is studied in the application domain. In order to apply niching in molecular spaces a metric for measuring the dissimilarity of molecules will be introduced. The approach will be validated in case studies and compared with results of an NSGA-II algorithm without niching in the search space.

REFERENCES

• 1: Bender, A., Glen, R.C.: Molecular similarity: a key technique in molecular informatics. Organic and Biomolecular Chemistry, 2: 3204--3218, 2004.
• 2: Daylight Chemical Information Systems, Inc. 120 Vantis -- Suite 550 -- Aliso Viejo, CA 92656 http://www.daylight.com/dayhtml/doc/theory/, Retreived Wednesday January 14, 2009.
• 3: Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6: 182--197, 2002.
• 4: Gower, J.C., Legendre P.: Metric and Euclidean Properties of Dissimilarity Coefficients. Journal of Classification, 3: 5--48, 1986.
• 5: Holliday, J.D., Hu, C-Y., Willett, P.: Grouping of Coefficients for the Calculation of Inter-Molecular Similarity and Dissimilarity using 2D Fragment Bit-Strings. Combinatorial Chemistry and High Throughput Screening, 5: 155--166, 2002.
• 6: Irwin, J.J., Shoichet, B.K.: ZINC--a free database of commercially available compounds for virtual screening. J. Chem. Inf. Model., 45(1):177--82, 2005.
• 7: Johannes W. Kruisselbrink , Thomas Bäck , Ad P. IJzerman , Eelke van der Horst, Evolutionary algorithms for automated drug design towards target molecule properties, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389393]
• 8: Johannes W. Kruisselbrink , Michael T. Emmerich , Thomas Bäck , Andreas Bender , Ad P. Ijzerman , Eelke Horst, Combining Aggregation with Pareto Optimization: A Case Study in Evolutionary Molecular Design, Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization, April 07-10, 2009, Nantes, France [doi>10.1007/978-3-642-01020-0_36]
• 9: Lameijer, E.-W., Kok, J.N., Baeck, T., IJzerman, A.P.: The molecule evoluator: An interactive evolutionary algorithm for the design of drug-like molecules. J. Chem. Inf. Model., 46(2):545--552, 2006.
• 10: Lipinski, C., Lombardo, F., Dominy, B., Feeney, P.: Experimental and computational approaches to estimate solubility and permeability in drug discovery and developments settings. Advanced Drug Delivery Reviews, 46(1--3):3--26, 2001.
• 11: Miller, B., Shaw, M.: Genetic Algorithms with Dynamic Niche Sharing for Multimodal Function Optimization, 1996 IEEE Conference on Evolutionary Computation, New York, USA, 1996, pp.786--791
• 12: Nicolaou, C. A., Brown, N., Pattichis, C. Molecular optimization using computational multi-objective methods. Curr. Opin. Drug Discov. Dev., 10(3), 316--24, 2007.
• 13: Nicolaou, C.A., Pattichis, C.S.: Multi-objective de novo drug design using evolutionary graphs. Chem. Cent. J., 2008, 2(1): 7, 2007.
• 14: Mike Preuss , Lutz Schönemann , Michael Emmerich, Counteracting genetic drift and disruptive recombination in (μpluskommaλ)-EA on multimodal fitness landscapes, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068155]
• 15: http://pubchem.ncbi.nlm.nih.gov/, Retrieved Wednesday January 14, 2009.
• 16: Schneider, G.; Fechner, U.: Computer-based de novo design of druglike molecules. Nat. Rev. Drug Discov. 4(8), 649--663, 2005.
• 17: SciTegic, Inc. 10188 Telesis Court, Suite 100, San Diego, CA 92121, USA. http://accelrys.com/products/scitegic/, Retrieved Wednesday January 14, 2009.
• 18: Sharma, B., Parmee, I.C., Whittaker, M., and Sedwell, A.: Drug discovery: exploring the utility of cluster oriented genetic algorithms in virtual library design. Congress on Evolutionary Computation (CEC), Edinburgh, UK, 668--675, 2005.
• 19: Shir, O.M.: Niching in Derandomized Evolution Strategies and its Applications in Quantum Control; A Journey from Organic Diversity to Conceptual Quantum Designs. PhD Thesis, LIACS, Universiteit Leiden, The Netherlands, 2008.
• 20: Ofer M. Shir , Mike Preuss , Boris Naujoks , Michael Emmerich, Enhancing Decision Space Diversity in Evolutionary Multiobjective Algorithms, Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization, April 07-10, 2009, Nantes, France [doi>10.1007/978-3-642-01020-0_12]
• 21: Wishart, D.S., Knox, C., Guo, A.C., Cheng, D., Shrivastava, S., Tzur, D., Gautam, B., Hassanali, M.: DrugBank: a knowledgebase for drugs, drug actions and drug targets. Nucleic Acids Res. 2008; 36:D901--6.
• 22: Wishart, D.S., Tzur, D., Knox, C., Eisner, R., Guo, A.C., Young, N., Cheng, D., Jewell, K., Arndt, D., Sawhney, S., Fung, C., Nikolai, L., Lewis, M., Coutouly, M.A., Forsythe, I., Tang, P., Shrivastava, S., Jeroncic, K., Stothard, P., Amegbey, G., Block, D., Hau, D.D., Wagner, J., Miniaci, J., Clements, M., Gebremedhin, M., Guo, N., Zhang, Y., Duggan, G.E., Macinnis, G.D., Weljie, A.M., Dowlatabadi, R., Bamforth, F., Clive, D., Greiner, R., Li, L., Marrie, T., Sykes, B.D., Vogel, H.J., Querengesser, L.: HMDB: the Human Metabolome Database. Nucleic Acids Res. 2007; 35:D521--6.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Chemistry

General Terms:
Algorithms, Design, Experimentation

Keywords:
drug design, evolutionary algorithms, molecules