A knowledge-based initial population generation in memetic algorithm for protein structure prediction
- Authors: Nazmul, Rumana , Chetty, Madhu
- Date: 2013
- Type: Text , Conference paper
- Relation: 20th International Conference, ICONIP 2013 p. 546-553
- Full Text: false
- Reviewed:
- Description: Predicting the minimum energy protein structure from its amino acid sequence, even under the rather simplified HP lattice model, continues to be an important and challenging problem in computational biology. In this paper, we propose a novel initial population generation strategy for evolutionary algorithm incorporating domain knowledge based on the concept of maximum hydrophobic core formation for Protein structure prediction (PSP) problem. The proposed technique helps the optimization process to commence with diverse seeds and thereby aids in converging to the global solution quickly. The experimental results, conducted on PSP problem using HP benchmark sequences for 2D square and 3D cubic lattice model, demonstrate that the proposed evolutionary algorithm with new core-based population initialization technique is very effective in improving the optimization process in terms of convergence as well as in achieving the optimal energy.
A priority based parental selection method for genetic algorithm
- Authors: Nazmul, Rumana , Chetty, Madhu
- Date: 2013
- Type: Text , Conference paper
- Relation: GECCO '13 , Amsterdam, July 6th-10th, 2013 ; published in Proceedings of the 15th annual conference companion on Genetic and evolutionary computation pg.125-126
- Full Text: false
- Reviewed:
- Description: Selection is an important and critical aspect in evolutionary computation. This paper presents a novel parental selection technique that includes the advantages of both the deterministic and the stochastic selection techniques and helps to reduce the loss of diversity by distributing the reproduction opportunity among all the members of the population. Moreover, the proposed selection strategy promotes the concept of non-random mating by clustering the population into groups according to the fitness values and then by persuading the mating between individuals from different groups based on performance determined dynamically over the evolution. Computational results using widely used benchmark functions show significant improvements in the convergence characteristics of the proposed selection method over two well-known selection techniques.
An adaptive strategy for assortative mating in genetic algorithm
- Authors: Nazmul, Rumana , Chetty, Madhu
- Date: 2013
- Type: Text , Conference paper
- Relation: 2013 IEEE Congress on Evolutionary Computation p. 2237-2244
- Full Text: false
- Reviewed:
- Description: In any traditional Genetic Algorithm (GA), recombination is a dominant search operator and capable of exploring the search space by sharing genetic information among the individuals in the population. However, a simple application of recombination alone is insufficient to guide convergence to an optimal solution. The selection of parents for recombination operation has a significant role in guiding the evolution towards the optimal solution and also for maintaining genetic diversity to avoid getting trapped in local minima. A non-random mating mimics the mechanism of reproduction in nature and is effective in maintaining diversity in population. This paper proposes a new strategy for selection of mating pairs based on a type of non-random mating called as assortative mating. The proposed mate selection scheme conserves the merits of both positive and negative assortative mating in a controlled manner by allowing mating between individuals having both similar and dissimilar phenotypes. For effective cross-over, it maintains genetic diversity in population by distributing the recombination among dissimilar individuals. Furthermore, it ensures the preservation and propagation of useful genetic information to the later stages of search by the selection of mates having similar phenotypes. Experimental results, using not only the five widely used benchmark functions but also twenty newly developed modified functions, are reported. The results show significant improvements in the convergence characteristics of the proposed mating strategy over existing nonrandom mating techniques.
An improved memetic approach for protein structure prediction incorporating maximal hydrophobic core estimation concept
- Authors: Nazmul, Rumana , Chetty, Madhu , Chowdhury, Ahsan
- Date: 2021
- Type: Text , Journal article
- Relation: Knowledge-Based Systems Vol. 219, no. (2021), p. 104395
- Full Text: false
- Reviewed:
- Description: Protein Structure Prediction (PSP) from the primary amino acid sequence, even using a simplified Hydrophobic-Polar (HP) lattice model, continues to be extremely challenging. Finding an optimal conformation, even for a small sequence, by any of the currently known evolutionary approaches is computationally extensive and time consuming. Although Memetic Algorithms (MAs) have shown success in finding the optimal solution for PSP, no significant work on the incorporation of domain or problem specific knowledge into the search process to significantly improve their performance is reported. In this paper, we present an approach to incorporate such knowledge into the initial population to enhance the effectiveness of MA for PSP. The domain knowledge we propose to use is based on the concept of maximal ‘core’ formation by exploiting the fundamental property of the H residues to be at the core of the minimum energy optimal protein structure. A generic technique is proposed for estimating the maximal Hydrophobic core (H-core) in a protein sequence for 2D Square, 3D Cubic and a more complex and realistic 3D FCC (Face Centered Cubic) lattice models. Subsequently, the knowledge of this estimated core is incorporated in an MA. The experiments conducted using HP benchmark sequences for 2D Square, 3D Cubic and 3D FCC lattice models show that the proposed MA with the new core-based population initialization technique has superior performance to the existing methods in terms of convergence speed as well as minimal energy. © 2018 Elsevier B.V.
Multimodal memetic framework for low-resolution protein structure prediction
- Authors: Nazmul, Rumana , Chetty, Madhu , Chowdhury, Ashan
- Date: 2020
- Type: Text , Journal article
- Relation: Swarm and Evolutionary Computation Vol. 52, no. (Feb 2020), p. 14
- Full Text: false
- Reviewed:
- Description: In this paper, we propose a systematic design of evolutionary optimization, namely Multimodal Memetic Framework (MMF), to effectively search the vast complex energy landscape. Our proposed memetic framework is implemented in hierarchical stages with the optimization of each stage performed in parallel in three different states: Exploratory, Exploitative and Central. Each state, with its own set of sub-populations, either explores or exploits by beneficial mixing of potential solutions to direct the search towards a global solution. Instead of implementing identical genetic operators, the proposed approach employs different selection and survival criteria in each state according to their designated task. The Exploratory state employs a knowledge-based initial population generation technique with appropriately tuned genetic operators to guide the search to the "nearest peak". The Exploitative state fine-tunes the individuals representing different regions by applying a building block based local search. Finally, by utilizing the imbibed knowledge from different peaks, the Central state carries out information-exchange among the highly fit solutions for exploring the undiscovered regions. The information exchange employs a novel non-random parental selection technique to distribute the reproduction opportunity intelligently among the individuals for making cross-over more effective. The method has been tested on a set of various benchmark protein sequences for 2D and 3D lattice models. The experimental results demonstrate the superiority of the proposed method over other state-of-the-art algorithms.
Protein structure prediction based on optimal hydrophobic core formation
- Authors: Nazmul, Rumana , Chetty, Madhu , Samudrala, Ram , Chalmers, David
- Date: 2012
- Type: Text , Conference paper
- Relation: 2012 IEEEE World Congress on Computational Intelligence Intelligence, Piscataway, NJ 10th-15th June 2012 p.1856-1864
- Full Text: false
- Reviewed:
- Description: The prediction of a minimum energy protein structure from its amino acid sequence represents an important and challenging problem in computational biology. In this paper, we propose a novel heuristic approach for protein structure prediction (PSP) based on the concept of optimal hydrophobic core formation. Using 2D HP model, a well-known set of substructures analogous to the secondary structures are obtained. Some sub-conformations are appropriately classified and then incorporated as prior knowledge. Unlike most of the popular PSP approaches which are stochastic in nature, the proposed method is deterministic. The effectiveness of the proposed algorithm is evaluated by well-known benchmark as well as non-benchmark sequences commonly used with 2D HP model. Maintaining similar accuracy as other core based and population based algorithms our method is significantly faster and reduces the computation time as it avoids blind search within the hydrophobic core (H-Core).
Protein structure prediction with a new composite measure of diversity and memory-based diversification strategy
- Authors: Nazmul, Rumana , Chetty, Madhu
- Date: 2013
- Type: Text , Conference paper
- Relation: 20th International Conference, ICONIP 2013 Daegu, Korea, November 3-7 th 2013;In Neural Information Processing. ( Lecture Notes in Computer Science), vol 8227. pg 649-656
- Full Text: false
- Reviewed:
- Description: Protein structure prediction (PSP) problem is a multimodal problem that can be tackled efficiently by evolutionary algorithms. However, evolutionary algorithms often fail to find the global optima due to genetic drift while solving the complex problems with a lot of peaks in the fitness landscape. Therefore, the need to efficiently measure as well as maintaining population diversity has significant effects in performance of evolutionary algorithms. In this paper, we introduce a composite measure of population diversity by hybridizing the phenotypic properties along with the distribution of individuals in a population over the fitness landscape. We further propose a memory-based diversification technique for the maintenance and promotion of diversity to prevent occurrence of stuck condition in multimodal problems such as PSP. Experiments conducted on protein structure prediction with HP benchmark sequences for 3D cubic lattice model illustrate that the proposed techniques are useful in improving the optimization process in terms of convergence as well as for achieving the optimal energy