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

• Sáenz, Ross Mary ^[1]
  1. [1] Universidad Nacional de Colombia

     Universidad Nacional de Colombia

     Colombia

     
• Localización: Selecciones Matemáticas, ISSN-e 2411-1783, Vol. 6, Nº. 2, 2019 (Ejemplar dedicado a: Agosto-Diciembre), págs. 275-282
• Idioma: español
• DOI: 10.17268/sel.mat.2019.02.13
• Títulos paralelos:
  • An approximation to the Longest Common Subsequence for Multiple Sequences problem using Shannon’s Entropy
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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.

  • English

    The Longest Common Subsequence for Multiples Sequences problem (LCSM), has been studied for more than 40 years, mainly motivated by its multiple applications in Bioinformatics. In this article we present a heuristic algorithm that estimates one or more solutions to the LCSM problem, using the Shannon’s Entropy as a measure of information in order to determine alignments with the greatest number of matches.

• Referencias bibliográficas
  • Blin, G., Bulteau, L., Jiang, M., Tejada, P. J. And Vialette, S. Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths....
  • 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...
  • Hakata, K., and Imai, H. The longest common subsequence problem for small alphabet size between many strings. Algorithms and Computation (1992),...
  • Huang, K., Yang, C.-B., Tseng, K.-T., et al. Fast algorithms for finding the common subsequence of multiple sequences. In Proceedings of the...
  • Korkin, D. A new dominant point-based parallel algorithm for multiple longest common subsequence problem. Technical Report TR01-148, Univ....
  • Li, Y., Li, H., Duan, T., Wang, S., Wang, Z., and Cheng, Y. A real linear and parallel multiple longest common subsequences (mlcs) algorithm....
  • Maier, D. The complexity of some problems on subsequences and supersequences. Journal of the ACM (JACM), 1978; 25(2), 322–336.