Exact and kernelization algorithms for Closet String

Authors

DOI:

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

Keywords:

Closest String Problem, Combinatorial Optimization, Exact Algorithm, Fixed Parameter Algorithm, Kernelization

Abstract

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.

Author Biography

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. 

References

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.

Downloads

Published

2020-12-25

How to Cite

Latorre Vilca, O. (2020). Exact and kernelization algorithms for Closet String. Selecciones Matemáticas, 7(02), 257-266. https://doi.org/10.17268/sel.mat.2020.02.08

Issue

Vol. 7 No. 02 (2020): August - December

Section

Articles

License

The authors who publish in this journal accept the following conditions:
1. The authors retain the copyright and assign to the journal the right of the first publication, with the work registered with the Creative Commons Attribution License,Atribución 4.0 Internacional (CC BY 4.0) which allows third parties to use what is published whenever they mention the authorship of the work And to the first publication in this magazine.
2. Authors may make other independent and additional contractual arrangements for non-exclusive distribution of the version of the article published in this journal (eg, include it in an institutional repository or publish it in a book) provided they clearly state that The paper was first published in this journal.
3. Authors are encouraged to publish their work on the Internet (for example, on institutional or personal pages) before and during the review and publication process, as it can lead to productive exchanges and to a greater and more rapid dissemination Of the published work.