Exact and kernelization algorithms for Closet String

• Latorre Vilca, Omar ^[1]
  1. [1] Facultad de Ciencias, Universidade Estadual de Mato Grosso do Sul, Cidade Universitária de Dourados, Mato Grosso do Sul-Brazil.
• Localización: Selecciones Matemáticas, ISSN-e 2411-1783, Vol. 7, Nº. 2, 2020 (Ejemplar dedicado a: August - December), págs. 257-266
• Idioma: inglés
• DOI: 10.17268/sel.mat.2020.02.08
• Títulos paralelos:
  • Algoritmos exacto y de kernelización para el problema de la subsecuencia de caracteres más próxima
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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.

  • English

    In this paper we address CLOSEST STRING problem that arises in web searching, coding theory and computational molecular biology. To solve it is to find a string that minimizes the maximum Hamming distance from a given set of strings. CLOSEST STRING is an NP-hard problem. This paper proposes two linear-time algorithms, one for the general case, a kernelization algorithm, and the other for three-strings, a linear-time algorithm called Minimization First Algorithm (MFA). A formal proof of the correctness and the computational complexity of the proposed algorithms are given.

• Referencias bibliográficas
  • 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;...
  • 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;...
  • 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...
  • 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...