Published January 1, 2020
| Version v1
Publication
Open
An Efficient-Assembler Whale Optimization Algorithm for DNA Fragment Assembly Problem: Analysis and Validations
Creators
- 1. Zagazig University
- 2. Australian Defence Force Academy
Description
The study of deoxyribonucleic acid (DNA) is crucial in many fields, including medicine, biology, zoology, agriculture, and forensics.Since reading a DNA sequence is onerous because of its massive length, it is common in many DNA analysis applications to divide DNA strands into small segments or fragments which, after analysis, must be reassembled.Since this reassembly takes a non-specific polynomial time to solve, the DNA fragment assembly problem (DFAP) is NP-hard.This paper proposes a new assembler for tackling the DFAP based on the overlap-layout-consensus (OLC) approach.The proposed assembler adapts a discrete whale optimization algorithm (DWOA) using standard operators adopted from evolutionary algorithms to simulate the strategy adopted by humpback whales when searching for prey.For the first time, we formulate the behaviors of whales to be applied directly to any discrete optimization problem based on three primary operations: a swap-based best-position operator, an ordered crossover operator, and selection of a random whale operation to perform the exploitation and exploration phases of the algorithm.These operations were carefully designed to preserve the methodology of the original whale algorithm.DFAP is a multi-objective problem that seeks to reach the optimal order of segments that maximizes the overlap score and minimizes the number of contigs (set of overlapping DNA segments) to compose a one-contig DNA strand.Existing local search methods, such as problem aware local search (PALS) many non-conflicting movements (PALS2-many), suffer from being trapped in local optima.Hence, the integration of DWOA with PALS2-many improves the search capability for finding the optimal order of fragments.In addition, we propose a new variation of PALS2-many that achieves simultaneously the two objectives of DFAP.Our proposed DWOA was compared with a number of the most recent robust assemblers: a hybrid crow search algorithm for solving the DFAP (CSA-P2M*Fit), P2M*Fit, and a hybrid genetic algorithm (GA-P2M*Fit).The experimental results and statistical analyses of the proposed DWOA on thirty benchmark instances show that DWOA significantly outperforms those algorithms in reaching fewer contigs, in addition to being competitive with CSA-P2M*Fit and superior to P2M*Fit and GA-P2M*Fit for the overlap score.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تعد دراسة الحمض النووي الريبي منزوع الأكسجين (DNA) أمرًا بالغ الأهمية في العديد من المجالات، بما في ذلك الطب والبيولوجيا وعلم الحيوان والزراعة والطب الشرعي. نظرًا لأن قراءة تسلسل الحمض النووي مرهق بسبب طوله الهائل، فمن الشائع في العديد من تطبيقات تحليل الحمض النووي تقسيم خيوط الحمض النووي إلى أجزاء صغيرة أو شظايا يجب إعادة تجميعها بعد التحليل. نظرًا لأن إعادة التجميع هذه تستغرق وقتًا متعدد الحدود غير محدد لحلها، فإن مشكلة تجميع شظايا الحمض النووي (DFAP) صعبة للغاية. تقترح هذه الورقة أداة تجميع جديدة لمعالجة DFAP بناءً على إجماع التخطيط المتداخل (OLC) النهج. يقوم المجمع المقترح بتكييف خوارزمية تحسين الحيتان المنفصلة (DWOA) باستخدام مشغلات قياسية معتمدة من الخوارزميات التطورية لمحاكاة الاستراتيجية التي تعتمدها الحيتان الحدباء عند البحث عن الفريسة. لأول مرة، نقوم بصياغة سلوكيات الحيتان ليتم تطبيقها مباشرة على أي مشكلة تحسين منفصلة بناءً على ثلاث عمليات أساسية: مشغل أفضل موقع قائم على المبادلة، ومشغل تقاطع مرتب، واختيار عملية حوت عشوائية لأداء مراحل الاستغلال والاستكشاف للخوارزمية. تم تصميم هذه العمليات بعناية للحفاظ على منهجية الخوارزمية الأصلية خوارزمية الحوت .DFAP هي مشكلة متعددة الأهداف تسعى إلى الوصول إلى الترتيب الأمثل للشرائح التي تزيد من درجة التداخل إلى أقصى حد وتقلل من عدد المتجاورات (مجموعة من شرائح الحمض النووي المتداخلة) لتكوين جديلة DNA أحادية التلامس. طرق البحث المحلية الموجودة، مثل البحث المحلي المدرك للمشاكل (PALS) العديد من الحركات غير المتضاربة (PALS2 - many)، تعاني من الوقوع في فخ الأمثلية المحلية .Hence، يؤدي دمج DWOA مع PALS2 - many إلى تحسين قدرة البحث للعثور على الترتيب الأمثل للشظايا. بالإضافة إلى ذلك، نقترح تباينًا جديدًا لـ PALS2 - many يحقق في وقت واحد هدفي DFAP.Our المقترح DWOA تمت مقارنة DWA مع عدد من أحدث أجهزة التجميع القوية: خوارزمية بحث غراب هجينة هجينة لحل DFAP (CSA - P2M *Fit)، P2M *Fit، وخوارزمية وراثية هجينة (GA - P2M *Fit). النتائج والتحليلات الإحصائية لـ DWA المقترحة على ثلاثين حالة مرجعية أن DWA تؤدي بشكل كبير إلى تلك الخوارزميات التي تصل إلى عدد أقل، بالإضافة إلى كونها تنافسية مع CSA - P2M *Fit و P2 Fit *Fit *Fit.Translated Description (French)
L'étude de l'acide désoxyribonucléique (ADN) est cruciale dans de nombreux domaines, notamment la médecine, la biologie, la zoologie, l'agriculture et la criminalistique. Étant donné que la lecture d'une séquence d'ADN est onéreuse en raison de sa longueur massive, il est courant dans de nombreuses applications d'analyse d'ADN de diviser les brins d'ADN en petits segments ou fragments qui, après analyse, doivent être réassemblés. Étant donné que ce réassemblage prend un temps polynomial non spécifique à résoudre, le problème d'assemblage des fragments d'ADN (DFAP) est NP-difficile. Cet article propose un nouvel assembleur pour s'attaquer au DFAP sur la base du consensus de superposition (L'assembleur proposé adapte un algorithme d'optimisation discret des baleines (DWOA) en utilisant des opérateurs standard adoptés à partir d'algorithmes évolutifs pour simuler la stratégie adoptée par les baleines à bosse lors de la recherche de proies. Pour la première fois, nous formulons les comportements des baleines à appliquer directement à tout problème d'optimisation discret basé sur trois opérations principales : un opérateur de meilleure position basé sur l'échange, un opérateur de croisement ordonné et la sélection d'une opération aléatoire des baleines pour effectuer les phases d'exploitation et d'exploration de l'algorithme. Ces opérations ont été soigneusement conçues pour préserver la méthodologie de l'original. algorithmm.DFAP est un problème multi-objectif qui cherche à atteindre l'ordre optimal des segments qui maximise le score de chevauchement et minimise le nombre de contigs (ensemble de segments d'ADN qui se chevauchent) pour composer un brin d'ADN d'un contig.Les méthodes de recherche locale existantes, telles que la recherche locale consciente des problèmes (PALS) de nombreux mouvements non conflictuels (PALS2-many), souffrent d'être piégés dans optima.Hence locale, l'intégration de DWOA avec PALS2-many améliore la capacité de recherche pour trouver l'ordre optimal des fragments.En outre, nous proposons une nouvelle variation de PALS2-many qui atteint simultanément les deux objectifs de DFAP.Our DWOA proposé a été comparé à un certain nombre des assembleurs robustes les plus récents : un algorithme de recherche hybride Crow pour résoudre le DFAP (CSA-P2M *Fit), P2M*Fit, et un algorithme génétique hybride (GA-P2M *Fit). Les résultats expérimentaux et les analyses statistiques du DWOA proposé sur trente instances de référence montrent que DWOA surpasse considérablement ces algorithmes en atteignant moins de contigs, en plus d'être compétitif avec CSA-P2M *Fit et supérieur à P2M*Fit et GA-P2M *Fit pour le score de chevauchement.Translated Description (Spanish)
El estudio del ácido desoxirribonucleico (ADN) es crucial en muchos campos, incluidos la medicina, la biología, la zoología, la agricultura y la medicina forense. Dado que la lectura de una secuencia de ADN es onerosa debido a su longitud masiva, es común en muchas aplicaciones de análisis de ADN dividir las cadenas de ADN en pequeños segmentos o fragmentos que, después del análisis, deben volver a ensamblarse. Dado que este reensamblaje tarda un tiempo polinómico no específico en resolverse, el problema de ensamblaje de fragmentos de ADN (DFAP) es NP-hard. Este documento propone un nuevo ensamblador para abordar el DFAP basado en el consenso de diseño de superposición (OLC). El ensamblador propuesto adapta un algoritmo de optimización discreta de ballenas (DWOA) utilizando operadores estándar adoptados a partir de algoritmos evolutivos para simular la estrategia adoptada por las ballenas jorobadas en la búsqueda de presas. Por primera vez, formulamos los comportamientos de las ballenas que se aplicarán directamente a cualquier problema de optimización discreta en función de tres operaciones principales: un operador de mejor posición basado en swaps, un operador de cruce ordenado y la selección de una operación aleatoria de ballenas para realizar las fases de explotación y exploración del algoritmo. Estas operaciones se diseñaron cuidadosamente para preservar la metodología del El algoritmo de ballena.DFAP es un problema multiobjetivo que busca alcanzar el orden óptimo de los segmentos que maximiza la puntuación de superposición y minimiza el número de cóntigos (conjunto de segmentos de ADN superpuestos) para componer una cadena de ADN de un cóntigo. Los métodos de búsqueda local existentes, como la búsqueda local consciente de problemas (PALS), muchos movimientos no conflictivos (PALS2-many), sufren de quedar atrapados en óptimos locales. Por lo tanto, la integración de DWOA con PALS2-many mejora la capacidad de búsqueda para encontrar el orden óptimo de los fragmentos. Además, proponemos una nueva variación de PALS2-many que logra simultáneamente los dos objetivos de DFAP.Our DWOA propuesto se comparó con una serie de los ensambladores robustos más recientes: un algoritmo de búsqueda Crow híbrido para resolver el DFAP (CSA-P2M *Fit), P2M*Fit y un algoritmo genético híbrido (GA-P2M *Fit). Los resultados experimentales y los análisis estadísticos del DWOA propuesto en treinta instancias de referencia muestran que DWOA supera significativamente a esos algoritmos para alcanzar menos cóntigos, además de ser competitivo con CSA-P2M *Fit y superior a P2M*Fit y GA-P2M *Fit para la puntuación de superposición.Files
09293303.pdf.pdf
Files
(245 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:b225ad514e13234a302662742ad5b7c1
|
245 Bytes | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- خوارزمية تحسين كفاءة تجميع الحيتان لمشكلة تجميع شظايا الحمض النووي: التحليل والتحقق من الصحة
- Translated title (French)
- Un algorithme d'optimisation de baleine d'assemblage efficace pour le problème d'assemblage de fragments d'ADN : analyse et validations
- Translated title (Spanish)
- Un algoritmo de optimización de ballenas de ensamblaje eficiente para el problema de ensamblaje de fragmentos de ADN: análisis y validaciones
Identifiers
- Other
- https://openalex.org/W3112072862
- DOI
- 10.1109/access.2020.3044857
References
- https://openalex.org/W1497903270
- https://openalex.org/W1531340660
- https://openalex.org/W1543559221
- https://openalex.org/W1939090090
- https://openalex.org/W1965434026
- https://openalex.org/W1972315233
- https://openalex.org/W1974046777
- https://openalex.org/W2010502318
- https://openalex.org/W2017708378
- https://openalex.org/W2026827093
- https://openalex.org/W2042253843
- https://openalex.org/W2046832190
- https://openalex.org/W2055110643
- https://openalex.org/W2058283730
- https://openalex.org/W2069416257
- https://openalex.org/W2076766584
- https://openalex.org/W2082999850
- https://openalex.org/W2104190341
- https://openalex.org/W2121720324
- https://openalex.org/W2132181343
- https://openalex.org/W2166265186
- https://openalex.org/W2170525931
- https://openalex.org/W2170633363
- https://openalex.org/W2232317135
- https://openalex.org/W2290883490
- https://openalex.org/W2317781305
- https://openalex.org/W2327843728
- https://openalex.org/W2508245841
- https://openalex.org/W2511742229
- https://openalex.org/W2603422842
- https://openalex.org/W2605396865
- https://openalex.org/W2612473079
- https://openalex.org/W2762451727
- https://openalex.org/W2782136875
- https://openalex.org/W2793274903
- https://openalex.org/W2801536506
- https://openalex.org/W2805076621
- https://openalex.org/W2808867322
- https://openalex.org/W2887088548
- https://openalex.org/W2896457000
- https://openalex.org/W2898113355
- https://openalex.org/W2905608407
- https://openalex.org/W2907487157
- https://openalex.org/W2912567266
- https://openalex.org/W2914133936
- https://openalex.org/W2923707764
- https://openalex.org/W2928669038
- https://openalex.org/W2947350869
- https://openalex.org/W2955693036
- https://openalex.org/W2965837582
- https://openalex.org/W2974664996
- https://openalex.org/W2980973518
- https://openalex.org/W2991234881
- https://openalex.org/W2991555241
- https://openalex.org/W2999911359
- https://openalex.org/W3008740910
- https://openalex.org/W3011104345
- https://openalex.org/W3014974411
- https://openalex.org/W3015395776
- https://openalex.org/W3023846105
- https://openalex.org/W3034427160
- https://openalex.org/W3034653956
- https://openalex.org/W3038102268
- https://openalex.org/W3043211958
- https://openalex.org/W3043561841
- https://openalex.org/W3056359467
- https://openalex.org/W3083328146
- https://openalex.org/W3084996758
- https://openalex.org/W3089911346
- https://openalex.org/W39578891
- https://openalex.org/W4241184565
- https://openalex.org/W4241671256
- https://openalex.org/W653530142
- https://openalex.org/W654916370