Metaheuristics on GPU graphics processor; Applicationto the Molecular Docking problem

Abstract

الملخص(بالعربية):

الالتحام الجزيئي تقنية تستخدم في صناعة الأدوية وفي عملية اكتشاف عقاقير جديدة. الهدف هو التنبؤ بوضعية الارتباط بين جزيء صغير (مرشح دواء) وهدف بروتيني( أصل المرض). نظرا لأن هذه المشكلة معقدة ومعروفة بأنها صعبة فقد تم اقتراح العديد من الخوارزميات الوصفية لحلها. مثل الخوارزميات الجينية و خوارزميات تحسين سرب الجسيمات وما إلى ذألك. إلا أن هاته الخوارزميات تتطلب قدرا كبيرا من موارد الحوسبة. في الوقت الحاضر يمكن توفير قوة الحساب هاته بواسطة وحدة معالجة الرسومات من خلال استخدام نموذج الحوسبة للأغراض العامة على وحدات معالجة الرسومات . تقدم هذه الأطروحة مقاربتين لموازاة الخوارزميات الوصفية على وحدة معالج الرسومات لحل مشكلة الالتحام الجزيئي ومن ثم تقييمها من حيث وقت الحساب الذي تم تحقيقه. أثبتت المقاربات المقترحة فعاليتها في تسريع لالتحام الجزيئي على وحدات معالجة الرسومات عند مقارنتها بوحدة المعالجة المركزية أحادية النواة أو وحدة المعالجة المركزية متعددة النواة. إلى جانب تقديم مقاربات الموازاة، نقترح أيضًا خوارزمية وصفية جديدة تعتمد على خوارزمية سرب النحل لحل مشكلة الالتحام الجزيئي كبديل للخوارزميات الوصفية التقليدية مثل الخوارزمية الجينية. ---------------------------------------------- Résumé (Français et/ou Anglais) :

Molecular Docking (MD) is a technique used in the pharmaceutical industry in theprocess of discovering new drugs. The aim is to predict the binding pose betweena small molecule (drug candidate) and a protein target (the origin of a disease).Since this problem is complex and known to be NP-hard, several metaheuristicshave been proposed to solve it, such as Genetic Algorithm (GA), and ParticleSwarm Optimization (PSO), . . . etc. Nevertheless, these metaheuristics are greedyin terms of computation time and often require a huge amount of computingresources. Nowadays, such computation power can be provided by the GraphicsProcessing Unit (GPUs) through the use of the GPGPU paradigm (General-purposecomputing on GPUs). This thesis presents two parallelization approaches of ametaheuristic on GPU to solve the molecular docking problem, and acorresponding evaluation in terms of computation time achieved on differentNVIDIA GPU architectures. The parallel metaheuristic approaches have proventheir effectiveness in accelerating MD on GPUs when compared to a single-coreCPU or multi-core CPU. Besides presenting the parallelization strategies, we alsopropose a new metaheuristic based on bees swarm optimization (BSO) algorithmto solve the MD problem as an alternative to the traditional metaheuristics suchas GA and PSO algorithms. ---------------------------------------------- L’Amarrage Moléculaire (AM) est une technique utilisée dans l’industriepharmaceutique dans le procès de découverte de nouveaux médicaments.L’objectif est de prédire la position d’interaction entre une petite molécule (substance médicale) et une protéine cible (l’origine d’une maladie). Ce problèmeest complexe et connu pour être NP-difficile. Plusieurs métaheuristiques ont étéproposées pour le résoudre, telles quel’algorithme génétique (GA), l’optimisationd’essaims de particules (PSO), etc. Néanmoins, ces métaheuristiques sontgourmandes en temps de calcul et souvent nécessitent beaucoup de ressourcesde calcul informatiques. Aujourd’hui, cette puissance peut être fournie par lescarte de traitement graphique (GPU) et grâce à l’utilisation du paradigme GPGPU (General PurposeComputing on GPU). Cette thèse présente deux approches deparallélisation des métaheuristiques sur les cartes GPU pour résoudre le problèmed’amarrage moléculaire, ainsi une évaluation adéquate en termes de temps decalcul réalisé sur différentes architectures GPUs, Les approches de parallélisationproposée ont prouvé leur efficacité dans l’accélération de AM sur les GPUs, cesrésultats ont été comparés avec un seul et multi-cœur CPU. En plus de laprésentation des stratégies de parallélisation, nous proposons également unnouvau algorithme basé sur la metaheuristique d’essaim d’abeilles (BSO) commealternative à métaheuristiques traditionnelles telles que les algorithmes GA et PSOpour résoudre le problème d’Amarrage Moléculaire.