Una aproximación al problema de la Subsecuencia Común más Larga de Múltiples Secuencias usando entropía de Shannon

Autores/as

DOI:

https://doi.org/10.17268/sel.mat.2019.02.13

Palabras clave:

Algoritmo Heurístico, Subsecuencia, Subsecuencia Común, Alineamiento, Entropía

Resumen

El problema de la Subsecuencia Común más Larga de Múltiples Secuencias (SCLM), ha sido ampliamente estudiado en Ciencias de la Computación por más de 40 años, motivado principalmente por sus diversas aplicaciones en Bioinformática. En este artículo se presenta un algoritmo heurístico que estima una o más soluciones al problema SCLM, utilizando entropía de Shannon como una medida de la información para determinar alineamientos con el mayor numero de coincidencias.

Citas

Blin, G., Bulteau, L., Jiang, M., Tejada, P. J. And Vialette, S. Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012; 138–148.

Cover, T. M., and Thomas, J. A. Elements of information theory. John Wiley & Sons, 2012.

Forero, W. E. S. Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida / comparative study of algorithms for the constrained longest common subsequence problem. Magíster en ciencias de la Ingeniería de sistemas y computación, Junio 2010.

Hakata, K., and Imai, H. The longest common subsequence problem for small alphabet size between many strings. Algorithms and Computation (1992), 469–478.

Huang, K., Yang, C.-B., Tseng, K.-T., et al. Fast algorithms for finding the common subsequence of multiple sequences. In Proceedings of the International Computer Symposium, 2004; 1006–1011.

Korkin, D. A new dominant point-based parallel algorithm for multiple longest common subsequence problem. Technical Report TR01-148, Univ. of New Brunswick, Tech. Rep. 2001.

Li, Y., Li, H., Duan, T., Wang, S., Wang, Z., and Cheng, Y. A real linear and parallel multiple longest common subsequences (mlcs) algorithm. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016; ACM:1725–1734.

Maier, D. The complexity of some problems on subsequences and supersequences. Journal of the ACM (JACM), 1978; 25(2), 322–336.

Descargas

Publicado

2019-12-24

Cómo citar

Sáenz, R. M. (2019). Una aproximación al problema de la Subsecuencia Común más Larga de Múltiples Secuencias usando entropía de Shannon. Selecciones Matemáticas, 6(02), 275-282. https://doi.org/10.17268/sel.mat.2019.02.13

Número

Vol. 6 Núm. 02 (2019): Agosto-Diciembre

Sección

Articles

Licencia

Los autores/as que publiquen en esta revista aceptan las siguientes condiciones:

  1. Los autores/as conservan los derechos de autor y ceden a la revista el derecho de la primera publicación, con el trabajo registrado con la licencia de atribución de Creative CommonsAtribución 4.0 Internacional (CC BY 4.0) , que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
  2. Los autores/as pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
  3. Se permite y recomienda a los autores/as a publicar su trabajo en Internet (por ejemplo en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado(Consultar: efecto del acceso abierto).