Impact of genomic reordering studies on human genome sequencing
DOI:
https://doi.org/10.5377/farem.v12i46.16490Keywords:
Permutation ordering, heuristic algorithms, metaheuristic algorithms, human genomeAbstract
This review article shows the main contributions of the scientific literature related to the SBPR problem (Sorting Permutations By Prefix Reversals) carried out in the last 47 years that have served as the basis for the complete sequencing of the human genome. In fact, the purpose of this study is to describe the main background of the problem from its origins to its final application in human genome sequencing. The methodology used is based on the documentary review, which allowed the construction of a matrix and a graph, where all possible bibliographic interconnections are summarized. However, the main findings show that the 1990s were key to develop a solid theory in terms of construction and verification of algorithms. Finally, conclusions and future perspectives of the main results obtained are given.
Downloads
References
Al Daoud, E. (2014). An Improved Ant Colony Algorithm for Genome Rearrangements [Algoritmo mejorado de colonias de hormigas para reordenaciones genómicas]. International Journal of Bioengineering and Life Sciences, 8(5), 768–771.
Baase, S., Van Gelder, A., & García, R. L. E. (2002). Algoritmos computacionales: Introducción al análisis y diseño. Pearson Educación.
Bafna, V., & Pevzner, P. A. (1996). Genome rearrangements and sorting by reversals. [Reordenación del genoma y clasificación por inversiones] SIAM Journal on Computing, 25(2), 272–289. https://doi.org/10.1137/S0097539793250627
Blum, C. (2005). Ant colony optimization: Introduction and recent trends [Optimización mediante colonias de hormigas: Introducción y tendencias recientes] Physics of Life Reviews, 2(4), 353–373. https://doi.org/10.1016/j.plrev.2005.10.001
Bóna, M. (2012). Combinatorics of permutations [Combinatoria de permutaciones]. (2nd ed.). Chapman and Hall/CRC. https://doi.org/10.1201/b12210
Bouzy, B. (2015). An experimental investigation on the pancake problem [Una investigación experimental sobre el problema de los panqueques]. In Computer Games (pp. 30–43). Springer. https://doi.org/10.1007/978-3-319-39402-2_3
Brito, K. L., Oliveira, A. R., Dias, U., & Dias, Z. (2019). Heuristics for the reversal and transposition distance problem [Heurísticas para el problema de la distancia de inversión y transposición]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 17(1), 2–13. https://doi.org/10.1109/TCBB.2019.2945759
Bulteau, L. (2013). Algorithmic aspects of genome rearrangements [Aspectos algorítmicos de los reordenamientos genómicos]. Université de Nantes.
Bulteau, L., Fertin, G., & Rusu, I. (2012). Pancake flipping is hard [Volterar panqueques es difícil] Proceedings of the 37th International Conference on Mathematical Foundations of Computer Science, 247–258. https://doi.org/10.1016/j.jcss.2015.02.003
Caprara, A., Lancia, G., & Ng, S.-K. (1999). A column-generation based branch-and-bound algorithm for sorting by reversals [Algoritmo branch-and-bound basado en la generación de columnas para la clasificación por inversiones] (Vol. 47). https://doi.org/10.1090/dimacs/047
Chitturi, B., Fahle, W., Meng, Z., Morales, L., Shields, C. O., Sudborough, I. H., & Voit, W. (2009). An (18/11) n upper bound for sorting by prefix reversals [Un límite superior de (18/11) n para la ordenación por inversión de prefijos]. Theoretical Computer Science, 410(36), 3372–3390. https://doi.org/10.1016/j.tcs.2008.04.045
Christie, D. A. (1998). A 3/2-approximation algorithm for sorting by reversals. [Algoritmo de aproximación 3/2 para la clasificación por inversiones] Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 244–252.
da Silveira, L. A., Soncco-Álvarez, J. L., & Ayala-Rincón, M. (2017). Parallel genetic algorithms with sharing of individuals for sorting unsigned genomes by reversals [Algoritmos genéticos paralelos con compartición de individuos para ordenar genomas sin signo mediante inversiones]. 2017 IEEE Congress on Evolutionary Computation (CEC), 741–748.
da Silveira, L. A., Soncco-Alvarez, J. L., de Lima, T. A., & Ayala-Rincon, M. (2018). Parallel multi-island genetic algorithm for sorting unsigned genomes by reversals [Algoritmo genético paralelo multi-islas para ordenar genomas sin signo por inversiones]. 2018 IEEE. Congress on Evolutionary Computation (CEC), 1–8.
Dias, U., Galvão, G. R., Lintzmayer, C. N., & Dias, Z. (2014). A general heuristic for genome rearrangement problems [Una heurística general para los problemas de reordenación del genoma]. Journal of Bioinformatics and Computational Biology, 12(03), 1450012. https://doi.org/10.1142/S0219720014500127
Dias, Z., & Dias, U. (2015). Sorting by prefix reversals and prefix transpositions [Clasificación por inversión de prefijos y transposición de prefijos]. Discrete Applied Mathematics, 181, 78–89. https://doi.org/10.1016/j.dam.2014.09.004
Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey [Teoría de optimización de colonias de hormigas: Un estudio]. Theoretical Computer Science, 344(2–3), 243–278. https://doi.org/10.1016/j.tcs.2005.05.020
Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents [Sistema de hormigas: optimización mediante una colonia de agentes cooperantes]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29–41. https://doi.org/10.1109/3477.484436
Du, K.-L., & Swamy, M. (2016). Search and Optimization by Metaheuristics: Techniques and Algorithms Inspired by Nature [Búsqueda y Optimización por Metaheurísticas: Técnicas y Algoritmos Inspirados en la Naturaleza]. Birkhäuser. https://doi.org/10.1007/978-3-319-41192-7
Dweighter, H. (1975). American Mathematical Monthly [Boletín Mensual de Matemáticas]. The Mathematical Association of America, 150, 1010.
Dweighter, H., Garey, M. R., Johnson, D. S., & Lin, S. (1977). E2569. The American Mathematical Monthly [Boletín Mensual de Matemáticas], 84(4), 296–296.
Fertin, G., Labarre, A., Rusu, I., Vialette, S., & Tannier, E. (2009). Combinatorics of genome rearrangements [Combinatoria de reordenaciones genómicas]. MIT press.
Fischer, J., & Ginzinger, S. W. (2005). A 2-approximation algorithm for sorting by prefix reversals [Algoritmo de aproximación a 2 para la ordenación por inversión de prefijos]. European Symposium on Algorithms, 415–425. https://doi.org/10.1007/11561071_38
Gates, W. H., & Papadimitriou, C. H. (1979). Bounds for sorting by prefix reversal [Límites para la clasificación por inversión de prefijos]. Discrete Mathematics, 27(1), 47–57. https://doi.org/10.1016/0012-365X(79)90068-2
Helmert, M. (2010). Landmark heuristics for the pancake problem [Heurística de referencia para el problema de los panqueques]. Third Annual Symposium on Combinatorial Search. https://doi.org/10.1609/socs.v1i1.18176
Heydari, M. H., & Sudborough, I. H. (1992). On sorting by prefix reversals and the diameter of pancake networks [Sobre la clasificación por inversión de prefijos y el diámetro de las redes panqueque]. Heinz Nixdorf Symposium at the University of Paderborn, 218–227. https://doi.org/10.1007/3-540-56731-3_21
Kaplan, H., Shamir, R., & Tarjan, R. E. (1997). Faster and simpler algorithm for sorting signed permutations by reversals [Algoritmo más rápido y sencillo para ordenar permutaciones con signo por inversiones]. Proceedings of the First Annual International Conference on Computational Molecular Biology, 163.
Kramer, O. (2017). Genetic algorithms [Algoritmos genéticos]. In Genetic algorithm essentials (pp. 11–19). Springer.
Lintzmayer, C. N. (2016). The Problem of Sorting Permutations by Prefix and Suffix Rearrangements [El problema de ordenar permutaciones mediante reordenamientos de prefijos y sufijos]. PhD thesis, University of Campinas, Institute of Computing, 2016. In English.
Nurk, S., Koren, S., Rhie, A., Rautiainen, M., V. Bzikadze, A., Mikheenko, A., R. Vollger, M., Altemose, N., Uralsky, L., Gershman, A., Aganezov, S., J. Hoyt, S., Diekhans, M., A. Logsdon, G., Alonge, M., E. Antonarakis, S., Borchers, M., G. Bouffard, G., Y. Brooks, S., … M. Phillippy, A. (2022). The complete sequence of a human genome [La secuencia completa del genoma humano]. Science, 376(6588), 44–53. https://doi.org/10.1126/science.abj6987
Sharmin, M., Yeasmin, R., & Hasan, M. (2008). Sorting by Prefix Reversals and Prefix Transpositions with Forward March [Clasificación por inversiones de prefijos y transposiciones de prefijos con marcha adelante]. ArXiv Preprint ArXiv:0812.3933.
Soncco-Álvarez, J. L., Almeida, G. M., Becker, J., & Ayala-Rincon, M. (2013). Parallelization and virtualization of genetic algorithms for sorting permutations by reversals [Paralelización y virtualización de algoritmos genéticos para ordenar permutaciones por inversiones]. 2013 World Congress on Nature and Biologically Inspired Computing, 29–35. https://doi.org/10.1109/NaBIC.2013.6617871
Soncco-Álvarez, J. L., & Ayala-Rincón, M. (2012). A genetic approach with a simple fitness function for sorting unsigned permutations by reversals [Un enfoque genético con una función de adecuación sencilla para ordenar permutaciones sin signo por inversiones]. 2012 7th Colombian Computing Congress (CCC), 1–6. https://doi.org/ 10.1109/ColombianCC.2012.6398025
Soncco-Álvarez, J. L., & Ayala-Rincón, M. (2013). Sorting permutations by reversals through a hybrid genetic algorithm based on breakpoint elimination and exact solutions for signed permutations [Ordenación de permutaciones por inversiones mediante un algoritmo genético híbrido basado en la eliminación de puntos de ruptura y soluciones exactas para permutaciones con signo]. Electronic Notes in Theoretical Computer Science, 292, 119–133. https://doi.org/10.1016/j.entcs.2013.02.009
Soncco-Álvarez, J. L., & Ayala-Rincón, M. (2014). Memetic algorithm for sorting unsigned permutations by reversals [Algoritmo memético para ordenar permutaciones sin signo por inversiones]. 2014 IEEE Congress on Evolutionary Computation (CEC), 2770–2777. https://doi.org/10.1109/CEC.2014.6900398
Zhongxi, M., & Tao, Z. (2006). An improved genetic algorithm for problem of genome rearrangement [Un algoritmo genético mejorado para problemas de reordenación del genoma]. Wuhan University Journal of Natural Sciences, 11(3), 498–502. https://doi.org/10.1007/BF02836651
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Revista Científica de FAREM-Esteli
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
