Incidencia de los estudios sobre reordenamiento genómico en la secuenciación del genoma humano
DOI:
https://doi.org/10.5377/farem.v12i46.16490Palabras clave:
Ordenamiento de permutaciones, algoritmos heurísticos, algoritmos metaheurísticos, genoma humanoResumen
En este artículo de revisión se muestran los principales aportes de la literatura científica relacionados con el problema SBPR (Sorting Permutations By Prefix Reversals, en español, Ordenamiento de permutaciones con reversión de prefijos) realizados en los últimos 47 años que han servido como base en la secuenciación completa del genoma humano. De hecho, este estudio tiene como propósito describir los principales antecedentes del problema desde sus orígenes hasta su aplicación final en la secuenciación del genoma humano. La metodología utilizada está basada en la revisión documental, la cual permitió construir una matriz y un grafo, en donde se resumen todas las interconexiones bibliográficas posibles. Sin embargo, los principales hallazgos demuestran que los años 90 fueron claves para desarrollar una teoría sólida en cuanto a construcción y verificación en lo que refiere a algoritmos. Finalmente, se brindan las conclusiones y perspectivas a futuro de los principales resultados obtenidos.
Descargas
Citas
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
Publicado
Número
Sección
Licencia
Derechos de autor 2023 Revista Científica de FAREM-Estelí
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
