Algoritmos exacto y de kernelización para el problema de la subsecuencia de caracteres más próxima

Autores/as

DOI:

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

Palabras clave:

Problema de la subsecuencia de caracteres más próxima, Optimización combinatoria, Algoritmo exacto, Algoritmo de parámetro fijo, Kernelización

Resumen

En este artículo abordamos el problema de la subsecuencia de caracteres más próxima que surge en la búsqueda web, la teoría de la codificación y la biología molecular computacional. Para resolverlo debe se encontrar una subsecuencia de caracteres que minimice la distancia de Hamming máxima de un conjunto dado de subsecuencias, dicho problema está en NP-hard. Este artículo propone dos algoritmos de tiempo lineal, uno para el caso general, un algoritmo de kernelización, y el otro para tres subsecuencias de caracteres, un algoritmo de tiempo lineal llamado Algoritmo de la primera minimización (MFA). Se expresa una prueba formal para verificar la corrección y complejidad computacional de los algoritmos propuestos.

Biografía del autor/a

Omar Latorre Vilca, Facultad de Ciencias, Universidade Estadual de Mato Grosso do Sul, Cidade Universitária de Dourados, Mato Grosso do Sul-Brazil.

Doutor em Informática pelo Instituto de Computação da Universidade Federal do Amazonas (IComp/UFAM). Possui o título de mestre em Ciência da Computação na Universidade Federal do ABC. Possui graduação (Bachalerado) em Sistemas da Informação na Universidad Nacional San Antonio Abad del Cusco diploma revalidado pelo IComp/UFAM. Atualmente é professor na UEMS nos cursos de Sistemas de Informação e Ciências da Computação. 

Citas

Amir A, Paryenty H, and Roditty L. Configurations and minority in the string consensus problem. Algorithmica. 2016; 74(4):1267-1292.

Basavaraju M, Panolan F, Rai A, Ramanujan MS, Saurabh S. On the kernelization complexity of string problems. Theoretical Comp. Science. 2018; 730:21–31.

Boucher C, Brown DG, and Durocher S. On the Structure of Small Motif Recognition Instances.. Berlin Heidelberg: Springer; 2009. p.269-281.

Fomin FV, Lokshtanov D, Saurabh S, Zehavi M. Kernelization: Theory of Parameterized Preprocessing. Great Britain: Cambridge University Press; 2019. chapter 1.

Frances M and Litman A. On covering problems of codes. Theor. Comput. Syst. 1997; 30:113-119.

Gramm J, Niedermeier R, Rossmanith P. Exact solutions for closest string and related problems. In: ISAAC ’01. Proceedings of the 12th International Symposium on Algorithms and Computation; 2001. p.441-453.

Gramm J, Niedermeier R, Rossmanith P. Fixed-parameter algorithms for closest string and related problems. Algorithmica. 2003; 37(1):25-42.

Lenstra Jr HW. Integer programming with a fixed number of variables. Mathematics of Operations Research. 1983; 8(4):538-548.

Liu X, Liu S, Hao Z, Mauch H. Exact algorithm and heuristic for the closest string problem. Computers & Operations Research. 1011; 38(11):1513-1520.

Ma B, Sun X. More Efficient Algorithms for Closest String and Substring Problems. Berlin Heidelberg; Springer; 2008. p.396-409.

Storer JA. Data compression: Methods and theory. New York: Computer Science Press, Inc. 1988. chapter 1.

Vilca OL. Combinatorial Approaches for the Closest String Problem.[ Doctoral thesis]. Amazonas: Federal university of Amazonas, Computing institute. 2019. Recovered from fttps://tede.ufam.edu.br/handle/tede/7449.

Descargas

Publicado

2020-12-25

Cómo citar

Latorre Vilca, O. (2020). Algoritmos exacto y de kernelización para el problema de la subsecuencia de caracteres más próxima. Selecciones Matemáticas, 7(02), 257-266. https://doi.org/10.17268/sel.mat.2020.02.08

Número

Vol. 7 Núm. 02 (2020): 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).