Abstract
Currently, determining DNA motifs or consensus plays an indispensable role in bioinformatics. Many postulates have been proposed for finding a consensus. Postulate 2-Optimality is essential for this task. A consensus satisfying postulate 2-Optimality is the best representative of a profile, and its distances to the profile members are uniform. However, this postulate has not been widely investigated in identifying a DNA motif or consensus for a DNA motif profile. The HDC algorithm is the best at this task in the literature. This study focuses on determining DNA motifs that satisfy postulate 2-Optimality. We propose a new hybrid genetic (HG1) algorithm based on the elitism strategy and local search. Subsequently, a novel elitism strategy and longest distance strategy are introduced to maintain the balance of exploration and exploitation. A new hybrid genetic (HG2) algorithm is developed based on the proposed exploration and exploitation balance approach. The simulation results show that these algorithms provide a high-quality DNA motif. The HG2 algorithm provides a DNA motif with the best quality.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Eren K, Murrell B (2018) RIFRAF: A Frame-resolving Consensus Algorithm. Bioinformatics 34(22):3817–3824
Popa O, Oldenburg E, Ebenhöh O (2020) From sequence to information. Phil Trans R Soc B 375:20190448. https://doi.org/10.1098/rstb.2019.0448
Pradhan M (2008) Motif discovery in biological sequences. San Jose State University, San Jose
Compeau P, Pevzner P (2015) Bioinformatics algorithms: an active learning approach. Active Learning Publisher, USA
Nguyen NT (2008) Advanced methods for inconsistent knowledge management. Springer London, London
Nguyen NT (2001) Using distance functions to solve representation choice problems. Fundam Inform 48:295–314
Dang DT, Phan HT, Nguyen NT, Hwang D (2021) Determining 2-Optimality consensus for DNA structure. In: IEA/AIE, vol 2021, pp 427–438
Workbench (2016) Manual for CLC genomics workbench. Workbench
Holland JH (1975) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan Press
Yang XS (2020) Nature-Inspired Optimization Algorithms. Academic Press
Dang D-C, et al. (2018) Escaping local optima using crossover with emergent diversity. IEEE Trans Evol Comput 22(3):484– 497
Benito-Parejo M, Merayo MG, Nunez M (2020) An Evolutionary Technique for Supporting the Consensus Process of Group Decision Making. In: IEEE SMC 2020, pp 2201–2206
Felling T (2021) Development of a Genetic Algorithm and its Application to a Bi-Level Problem of System Cost Optimal Electricity Price Zone Configurations. Energy Econ 101:105422. https://doi.org/10.1016/j.eneco.2021.105422
Husbands P, et al. (2021) Recent Advances in Evolutionary and Bio-inspired Adaptive Robotics: Exploiting Embodied Dynamics. Appl Intell 51(9):6467–6496
Kabir R, Islam R (2019) Chemical reaction optimization for RNA structure prediction. Appl Intell 49(2):352–375
Dumitrescu D, Lazzerini B, Jain LC, Dumitrescu A (2000) Evolutionary Computation. CRC Press
Maxim AD (2020) Archived elitism in evolutionary computation: Towards improving solution quality and population diversity. Int J Bio-Inspir Com 15(3):135–146
Eiben AE, Schippers CA (1998) On evolutionary exploration and exploitation. Fundam Informaticae 35(1-4):35–50
Črepinšek M, Liu S-H, Mernik M (2013) Exploration and exploitation in evolutionary algorithms. ACM Comput Surv 45(3):1–33
Herrera F, Lozano M (1996) Adaptation of genetic algorithm parameters based on fuzzy logic controllers. Genetic algorithms and soft computing. Physica, Heidelberg, pp 95–125
Maleszka M, Nguyen NT (2015) Integration computing and collective intelligence. Expert Syst Appl 42(1):332–340
Ji L, Tong S, Li H (2021) Dynamic Group Consensus for Delayed Heterogeneous Multi-agent Systems in Cooperative-competitive Networks via Pinning Control. Neurocomputing 433:1–11
Boeck KD, Castellani C, Elborn JS (2014) Medical consensus, guidelines, and position papers: a policy for the ECFS. J Cyst Fibros 13(5):495–498
Dang DT, Nguyen NT, Hwang D (2020) A Quick Algorithm to Determine 2-Optimality Consensus for Collectives. IEEE Access 8:221794–221807
Ilinkin I, Ye J, Janardan R (2010) Multiple structure alignment and consensus identification for proteins. BMC Bioinform 11(1):71–90
Felsenstein J (1997) An alternating least squares approach to inferring phylogenies from pairwise distances. Syst. Biol. 46(1):101–111
Amir A, Landau GM, Na JC, Park H, Park K, Sim JS (2011) Efficient Algorithms for Consensus String Problems Minimizing both Distance Sum and Radius. Theor Comput Sci 412(39):5239–5246
Hashim FA, Mabrouk MS, Al-Atabany W (2019) Review of different sequence motif finding algorithms. Avicenna J Med Biotechnol 11(2):130–148
Lawrence CE, Reilly AA (1990) An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned biopolymer sequences. Proteins Struct Funct Genet 7 (1):41–51
Tran NTL, Huang C-H (2014) A survey of motif finding web tools for detecting binding site motifs in chIP-seq data. Biol Direct 9(1). https://doi.org/10.1186/1745-6150-9-4
Zare-Mirakabad F, Ahrabian H, Sadeghi M, Hashemifar S, Nowzari-Dalini A, Goliaei B (2009) Genetic algorithm for dyad pattern finding in DNA sequences. Genes Genet Syst 84(1):81–93
Eskin E, Pevzner PA (2002) Finding composite regulatory patterns in DNA sequences. Bioinformatics 18(1):354–363
Bin Ashraf F, Shafi MSR (2020) MFEA: An evolutionary approach for motif finding in DNA sequences. Inform Med Unlocked 21:1–9
Koumousis VK, Katsaras CP (2006) A Saw-tooth Genetic Algorithm Combining the Effects of Variable Population Size and Reinitialization to Enhance Performance. IEEE Trans Evol Comput 10(1):19–28
Lozano M, Herrera F, Cano JR (2008) Replacement strategies to preserve useful diversity in Steady-State genetic algorithms. Inf Sci 178(23):4421–4433
Hutter M, Legg S (2006) Fitness uniform optimization. IEEE Trans Evol Comput 10(5):568–589
Shojaedini E, Majd M, Safabakhsh R (2019) Novel adaptive genetic algorithm sample consensus. Appl Soft Comput J 77:635–642
Srinivas M, Patnaik LM (1994) Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans Syst Man Cybern 24(4):656–667
Amor HB, Rettinger A (2005) Intelligent exploration for genetic algorithms: Using Self-Organizing maps in evolutionary computation. In: GECCO, vol 2005, pp 1531–1538
Chow CK, Yuen SY (2011) An evolutionary algorithm that makes decision based on the entire previous search history. IEEE Trans Evol Comput 15(6):741–769
Rani S, Suri B, Goyal R (2019) On the effectiveness of using elitist genetic algorithm in mutation testing. Symmetry 11(9):1145. https://doi.org/10.3390/sym11091145
Anton VE (2018) On proportions of fit individuals in population of Mutation-Based evolutionary algorithm with tournament selection. Evol Comput 26(2):269–297
Chu TH, Nguyen QU, O’Neill M (2018) Semantic tournament selection for genetic programming based on statistical analysis of error vectors. Inf Sci 436–437:352–366
Du H, Wang Z, Zhan W, Guo J (2018) Elitism and distance strategy for selection of evolutionary algorithms. IEEE Access 6:44531–44541
Author information
Authors and Affiliations
Corresponding authors
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This article belongs to the Topical Collection: Emerging Topics in Artificial Intelligence Selected from IEA/AIE2021 Guest Editors: Ali Selamat and Jerry Chun-Wei Lin
Rights and permissions
About this article
Cite this article
Dang, D.T., Nguyen, N.T. & Hwang, D. Hybrid genetic algorithms for the determination of DNA motifs to satisfy postulate 2-Optimality. Appl Intell 53, 8644–8653 (2023). https://doi.org/10.1007/s10489-022-03491-7
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-022-03491-7