Abstract

This paper addresses the problem of predicting the tertiary structure of a protein given its amino acid sequence, which has been reported to belong to the NP-Complete class of problems. We design an ad-hoc distributed memetic algorithm (DMA) and evaluate several algorithm configurations in terms of different distributed population structures, ad-hoc local search strategies and the combination of two energy functions. The algorithm uses an asynchronous hierarchical population of agents that exchange solutions along the execution of the algorithm. Extensive computational experiments were carried out in order to test: (1) the impact of the communication on different population structures, (2) the combination of the energy functions used for fitness calculations, (3) the scalability of the algorithm for structures with a larger number of agents, (4) the performance of the different approaches proposed for local search and diversity calculations, (5) the biological significance of the predicted structures and (6) to compare the best performing configuration of the DMA with other algorithms from the literature. The algorithm was tested on 20 sequences of different size, and the analysis was performed regarding both computational quality and biological significance of the predicted structures. Results show that the combination of energy functions and the proposed Distributed Memetic Algorithm allows the prediction of structures that are similar to the experimental ones. Performance analysis shows that increasing parallelism improves the execution times, without worsening the quality of the solutions. (C) 2020 Elsevier B.V. All rights reserved.