Enhancing Multiple Sequence Alignment with Genetic Algorithms: A Bioinformatics Approach in Biomedical Engineering
DOI:
https://doi.org/10.17488/RMIB.45.2.4Keywords:
bioinformatics, genetic algorithm, multiple sequence alignment, msaAbstract
This study aimed to create a genetic information processing technique for the problem of multiple alignment of genetic sequences in bioinformatics. The objective was to take advantage of the computer hardware's capabilities and analyze the results obtained regarding quality, processing time, and the number of evaluated functions. The methodology was based on developing a genetic algorithm in Java, which resulted in four different versions: Gp1, Gp2, Gp3 and Gp4 . A set of genetic sequences were processed, and the results were evaluated by analyzing numerical behavior profiles. The research found that algorithms that maintained diversity in the population produced better quality solutions, and parallel processing reduced processing time. It was observed that the time required to perform the process decreased, according to the generated performance profile. The study concluded that conventional computer equipment can produce excellent results when processing genetic information if algorithms are optimized to exploit hardware resources. The computational effort of the hardware used is directly related to the number of evaluated functions. Additionally, the comparison method based on the determination of the performance profile is highlighted as a strategy for comparing the algorithm results in different metrics of interest, which can guide the development of more efficient genetic information processing techniques.
Downloads
References
N. Mićić and B. Mićić, “God is Dead, Long Live DNA,” Agro-knowledge J., vol. 18, no. 2, pp. 143-146, Dec. 2017, doi: https://doi.org/10.7251/AGREN1702143M
D. Ghoshdastidar and M. Bansal, “Dynamics of physiologically relevant noncanonical DNA structures: an overview from experimental and theoretical studies,” Brief Funct. Genomics, vol. 18, no. 3, pp. 192–204, Jun. 2018, doi: https://doi.org/10.1093/bfgp/ely026
E. Arunan, “One Hundred Years After the Latimer and Rodebush Paper, Hydrogen Bonding Remains an Elephant!,” J. Indian Inst. Sci., vol. 100, no. 1, pp. 249–255, Jan. 2020, doi: https://doi.org/10.1007/s41745-019-00154-4
A. M. Fleming and C. J. Burrows, “Formation and processing of DNA damage substrates for the hNEIL enzymes,” Free Radic. Biol. Med., vol. 107, pp. 35–52, Jun. 2017, doi: https://doi.org/10.1016/j.freeradbiomed.2016.11.030
É. Leroux, C. Brosseau, B. Angers, A. Angers, and S. Breton, “Méthylation de l’ADN mitochondrial,” Med. Sci., vol. 37, no. 3, pp. 258–264, Mar. 2021, doi: https://doi.org/10.1051/medsci/2021011
E. W. Sayers, E. E. Bolton, J. R. Brister, K. Canese, et al., ‘Database resources of the national center for biotechnology information’, Nucleic Acids Res., vol. 50, no. D1, pp. D20–D26, Jan. 2022, doi: https://doi.org/10.1093/nar/gkab1112
GenBank and WGS Statistics, GenBank, 2024. [Online]. Available: https://www.ncbi.nlm.nih.gov/genbank/statistics/
M. Abdel-Basset, L. Abdel-Fatah, and A. K. Sangaiah, “Metaheuristic Algorithms: A Comprehensive Review,” in Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications, A. K. Sangaiah, M. Sheng, Z. Zhang, Eds., Catalunya, Spain: Academic Press, 2018, pp. 185–231. doi: https://doi.org/10.1016/B978-0-12-813314-9.00010-4
S. M. Almufti, A. Ahmad Shaban, Z. Arif Ali, R. Ismael Ali, and J. A. Dela Fuente, “Overview of Metaheuristic Algorithms,” PGSRT, vol. 2, no. 2, pp. 10–32, Apr. 2023, doi: https://doi.org/10.58429/pgjsrt.v2n2a144
D. Rodriguez, D. Gomez, D. Alvarez, and S. Rivera, “A Review of Parallel Heterogeneous Computing Algorithms in Power Systems,” Algorithms, vol. 14, no. 10, art. no.. 275, Sep. 2021, doi: https://doi.org/10.3390/a14100275
X. Wang and J. Liu, “Multiscale Parallel Algorithm for Early Detection of Tomato Gray Mold in a Complex Natural Environment,” Front. Plant. Sci., vol. 12, art. no. 620273, May 2021, doi: https://doi.org/10.3389/fpls.2021.620273
X. Dong, Y. Wu, Z. Wang, L. Dhulipala, Y. Gu, and Y. Sun, “High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems,” in Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, New York, NY, USA, 2023, pp. 341–353. doi: https://doi.org/10.1145/3558481.3591071
M. Kimiaei, A. Hassan Ibrahim, and S. Ghaderi, “A subspace inertial method for derivative-free nonlinear monotone equations,” Optimization, pp. 1–28, Sep. 2023, doi: https://doi.org/10.1080/02331934.2023.2252849
A. H. Kamali, E. Giannoulatou, T. Y. Chen, M. A. Charleston, A. L. McEwan, and J. W. K. Ho, “How to test bioinformatics software?,” Biophys Rev., vol. 7, no. 3, pp. 343–352, Sep. 2015, doi: https://doi.org/10.1007/s12551-015-0177-3
Y. Zhang, Q. Zhang, J. Zhou, and Q. Zou, “A survey on the algorithm and development of multiple sequence alignment,” Brief Bioinform., vol. 23, no. 3, art. no. bbac069, May 2022, doi: https://doi.org/10.1093/bib/bbac069
M. Maiolo, X. Zhang, M. Gil, and M. Anisimova, “Progressive multiple sequence alignment with indel evolution,” BMC Bioinformatics, vol. 19, no. 1, art. no. 331, Dec. 2018, doi: https://doi.org/10.1186/s12859-018-2357-1
B. Schmidt and A. Hildebrandt, “Dedicated Bioinformatics Analysis Hardware,” in Encyclopedia of Bioinformatics and Computational Biology, Sydney, Australia: Elsevier, 2019, pp. 1142–1150. doi: https://doi.org/10.1016/B978-0-12-809633-8.20186-6
R. Guo, Y. Zhao, Q. Zou, X. Fang, and S. Peng, “Bioinformatics applications on Apache Spark,” Gigascience, vol. 7, no. 8, art. no. giy098, Aug. 2018, doi: https://doi.org/10.1093/gigascience/giy098
N. A. Stover and A. R. O. Cavalcanti, “Using NCBI BLAST,” Curr. Protoc. Essent. Lab. Tech, vol. 14, no. 1, May 2017, doi: https://doi.org/10.1002/cpet.8
S. Iantorno, K. Gori, N. Goldman, M. Gil, and C. Dessimoz, “Who Watches the Watchmen? An Appraisal of Benchmarks for Multiple Sequence Alignment,” Methods Mol. Biol., vol. 1079, 2014, pp. 59–73. doi: https://doi.org/10.1007/978-1-62703-646-7_4
A. Löytynoja, “Alignment Methods: Strategies, Challenges, Benchmarking, and Comparative Overview,” Methods Mol. Biol., vol. 855, 2012, pp. 203–235. doi: https://doi.org/10.1007/978-1-61779-582-4_7
Y. He, “Research on global double sequence alignment optimization algorithm based on dynamic programming,” in Third International Conference on Computer Science and Communication Technology (ICCSCT 2022), Beijing, China, 2022, art. no. 125060L, doi: https://doi.org/10.1117/12.2662630
J.-H. Hung and Z. Weng, “Sequence Alignment and Homology Search with BLAST and ClustalW,” Cold Spring Harb. Protoc., vol. 2016, no. 11, art. no. pdb.prot093088, Nov. 2016, doi: https://doi.org/10.1101/pdb.prot093088
Q. Zou, X. Shan, and Y. Jiang, “A Novel Center Star Multiple Sequence Alignment Algorithm Based on Affine Gap Penalty and K-Band,” Phys. Procedia, vol. 33, pp. 322–327, 2012, doi: https://doi.org/10.1016/j.phpro.2012.05.069
F. Tang, J. Chao, Y. Wei, F. Yang, Y. Zhai, L. Xu, Q. Zou, “HAlign 3: Fast Multiple Alignment of Ultra-Large Numbers of Similar DNA/RNA Sequences,” Mol. Biol. Evol., vol. 39, no. 8, Aug. 2022, doi: https://doi.org/10.1093/molbev/msac166
B. Reddy and R. Fields, “Multiple Sequence Alignment Algorithms in Bioinformatics,” in Smart Trends in Computing and Communications. Lecture Notes in Networks and Systems, 2022, pp. 89–98. doi: https://doi.org/10.1007/978-981-16-4016-2_9
D. Pacheco Bautista, M. González Pérez, and I. Algredo Badillo, “From sequencing to hardware acceleration of DNA alignment software: A integral review,” Rev. Mex. Ing. Biomed., vol. 36, no. 3, pp. 257–275, Sep. 2015, doi: https://doi.org/10.17488/RMIB.36.3.6
D. Pacheco-Bautista, “ABPSE: Alineador de ADN Basado en Paralelismo a Nivel de Bit y la Estrategia Siembra y Extiende,” Rev. Mex. Ing. Biomed., vol. 40, no. 1, pp. 1–13, 2019. doi: https://doi.org/10.17488/RMIB.40.1.4
A. S. M. Aljohani, F. A. Alhumaydhi, A. Rauf, E. M. Hamad, and U. Rashid, “In Vivo Anti-Inflammatory, Analgesic, Sedative, Muscle Relaxant Activities and Molecular Docking Analysis of Phytochemicals from Euphorbia pulcherrima,” Evid. Based Complement. Alternat. Med., vol. 2022, art. no. 7495867, Apr. 2022, doi: https://doi.org/10.1155/2022/7495867
J. H. Holland, Adaptation in Natural and Artificial Systems. The MIT Press, 1992, doi: https://doi.org/10.7551/mitpress/1090.001.0001
K. Hao, J. Zhao, K. Yu, C. Li, and C. Wang, “Path Planning of Mobile Robots Based on a Multi-Population Migration Genetic Algorithm,” Sensors, vol. 20, no. 20, art. no. 5873, Oct. 2020, doi: https://doi.org/10.3390/s20205873
H. Ahrabian, M. Ganjtabesh, A. N. Dalini, and Z. R. M. Kashani, “Genetic algorithm solution for partial digest problem,” Int. J. Bioinform. Res. Appl., vol. 9, no. 6, pp. 584-594, 2013, doi: https://doi.org/10.1504/ijbra.2013.056622
M. Fernandez, J. Caballero, L. Fernandez, and A. Sarai, “Genetic algorithm optimization in drug design QSAR: Bayesian-regularized genetic neural networks (BRGNN) and genetic algorithm-optimized support vectors machines (GA-SVM),” Mol. Divers, vol. 15, no. 1, pp. 269–289, Feb. 2011, doi: https://doi.org/10.1007/s11030-010-9234-9
M. Sale and E. A. Sherer, “A genetic algorithm based global search strategy for population pharmacokinetic/pharmacodynamic model selection,” Br. J. Clin. Pharmacol., vol. 79, no. 1, pp. 28–39, Jan. 2015, doi: https://doi.org/10.1111/bcp.12179
S. H. Almanza-Ruiz, A. Chavoya, and H. A. Duran-Limon, “Parallel protein multiple sequence alignment approaches: a systematic literature review,” J. Supercomput., vol. 79, no. 2, pp. 1201–1234, Feb. 2023, doi: https://doi.org/10.1007/s11227-022-04697-9
D. Song, J. Chen, G. Chen, N. Li, et al., “Parameterized BLOSUM Matrices for Protein Alignment,” IEEE/ACM Trans. Comput. Biol. Bioinform., vol. 12, no. 3, pp. 686–694, May 2015, doi: https://doi.org/10.1109/tcbb.2014.2366126
J. S. Piña, S. Orozco-Arias, N. Tobón-Orozco, L. Camargo-Forero, R. Tabares-Soto, and R. Guyot, “G-SAIP: Graphical Sequence Alignment Through Parallel Programming in the Post-Genomic Era,” Evol. Bioinform. Online, vol. 19, art. no. 117693432211505, Jan. 2023, doi: https://doi.org/10.1177/11769343221150585
I. R. and A. Chavoya, “PaMSA: A Parallel Algorithm for the Global Alignment of Multiple Protein Sequences,” IJACSA, vol. 8, no. 4, pp. 513-522, 2017, doi: https://dx.doi.org/10.14569/IJACSA.2017.080468
T. Harada and E. Alba, “Parallel Genetic Algorithms,” ACM Comput. Surv., vol. 53, no. 4, pp. 1–39, Jul. 2021, doi: https://doi.org/10.1145/3400031
J. Zhu, G. Wang, Y. Li, Z. Duo, and C. Sun, “Optimization of hydrogen liquefaction process based on parallel genetic algorithm,” Int. J. Hydrogen Energy, vol. 47, no. 63, pp. 27038–27048, Jul. 2022, doi: https://doi.org/10.1016/j.ijhydene.2022.06.062
J. Xu, L. Pei, and R. Zhu, “Application of a Genetic Algorithm with Random Crossover and Dynamic Mutation on the Travelling Salesman Problem,” Procedia Comput. Sci., vol. 131, pp. 937–945, 2018, doi: https://doi.org/10.1016/j.procs.2018.04.230
K. R. Anil Kumar and E. R. Dhas, “Opposition based genetic optimization algorithm with Cauchy mutation for job shop scheduling problem,” Mater. Today Proc., vol. 72, pp. 3006–3011, 2023, doi: https://doi.org/10.1016/j.matpr.2022.08.263
T. D. Pham and W.-K. Hong, “Genetic algorithm using probabilistic-based natural selections and dynamic mutation ranges in optimizing precast beams,” Comput. Struct., vol. 258, art. no. 106681, Jan. 2022, doi: https://doi.org/10.1016/j.compstruc.2021.106681
Galaxy Community, “The Galaxy platform for accessible, reproducible and collaborative biomedical analyses: 2022 update,” Nucleic Acids Res., vol. 50, no. W1, pp. W345–W351, Jul. 2022, doi: https://doi.org/10.1093/nar/gkac247
A. Bonilla-Petriciolet, J. C. Tapia-Picazo, C. Soto-Becerra, and J. G. Zapiain-Salinas, “Perfiles de comportamiento numérico de los métodos estocásticos simulated annealing y very fast simulated annealing en cálculos termodinámicos,” Ing. Inv. Tecnolog., vol. 12, no. 1, pp. 51–62, Jan. 2011, doi: https://doi.org/10.22201/fi.25940732e.2011.12n1.006
R.-W. Ernesto, L.-G. Ernesto, B. Rafael, and G.-G. Yolanda, “Perfiles de comportamiento numérico de los métodos de búsqueda immune network algorithm y bacterial foraging optimization algorithm en funciones benchmark,” Ing. Inv. Tecnolog., vol. 17, no. 4, pp. 479–490, Oct. 2016, doi: https://doi.org/10.1016/j.riit.2016.11.007
E. D. Dolan and J. J. Moré, “Benchmarking optimization software with performance profiles,” Math. Program., vol. 91, no. 2, pp. 201–213, Jan. 2002, doi: https://doi.org/10.1007/s101070100263
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Revista Mexicana de Ingenieria Biomedica
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Upon acceptance of an article in the RMIB, corresponding authors will be asked to fulfill and sign the copyright and the journal publishing agreement, which will allow the RMIB authorization to publish this document in any media without limitations and without any cost. Authors may reuse parts of the paper in other documents and reproduce part or all of it for their personal use as long as a bibliographic reference is made to the RMIB. However written permission of the Publisher is required for resale or distribution outside the corresponding author institution and for all other derivative works, including compilations and translations.
