Una aproximación al problema de la Subsecuencia Común más Larga de Múltiples Secuencias usando entropía de Shannon
DOI:
https://doi.org/10.17268/sel.mat.2019.02.13Palavras-chave:
Algoritmo Heurístico, Subsecuencia, Subsecuencia Común, Alineamiento, EntropíaResumo
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.Referências
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.
Publicado
Como Citar
Edição
Seção
Licença
Os autores que publicam nesta revista aceitam as seguintes condições:
Os autores mantêm os direitos autorais e atribuem à revista o direito da primeira publicação, com o trabalho registrado com a licença de atribuição Creative Commons Atribución 4.0 Internacional (CC BY 4.0), que permite que terceiros usem o material publicado sempre que mencionarem a autoria do trabalho e os direitos autorais. Primeira publicação nesta revista.
Os autores podem fazer outros acordos contratuais independentes e adicionais para a distribuição não exclusiva da versão do artigo publicada nesta revista (por exemplo, incluí-la em um repositório institucional ou publicá-la em um livro), desde que afirme claramente que o trabalho Foi publicado nesta revista.
É permitido e recomendado aos autores que publiquem seus trabalhos na Internet (por exemplo, em páginas institucionais ou pessoais) antes e durante o processo de revisão e publicação, pois isso pode levar a trocas produtivas e a uma disseminação maior e mais rápida do trabalho. publicado (Consultar: efeito do acesso aberto).
