Document Open Access Logo

Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor

Authors Itai Boneh, Dvir Fried, Adrian Miclăuş, Alexandru Popa

PDF
Thumbnail PDF

File

LIPIcs.CPM.2023.5.pdf
  • Filesize: 0.84 MB
  • 18 pages

Document Identifiers

Author Details

Itai Boneh
  • Reichman University, Herzliya, Israel
Dvir Fried
  • Bar-Ilan University, Ramat-Gan, Israel
Adrian Miclăuş
  • Faculty of Mathematics and Computer Science, University of Bucharest, Romania
Alexandru Popa
  • Faculty of Mathematics and Computer Science, University of Bucharest, Romania

Funding

This work was supported by a grant of the Ministry of Research, Innovation and Digitization, CNCS - UEFISCDI, project number PN-III-P1-1.1-TE-2021-0253, within PNCDI III.
  • Boneh, Itai: Israel Science Foundation grant 810/21.
  • Fried, Dvir: Supported in part by ISF grant no. 1926/19, by a BSF grant no. 2018364, and by an ERC grant MPM under the EU’s Horizon 2020 Research and Innovation Programme (grant no. 683064).

Cite As Get BibTex

Itai Boneh, Dvir Fried, Adrian Miclăuş, and Alexandru Popa. Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CPM.2023.5

Abstract

Hairpin completion is an operation on formal languages that has been inspired by hairpin formation in DNA biochemistry and has many applications especially in DNA computing. Consider s to be a string over the alphabet {A, C, G, T} such that a prefix/suffix of it matches the reversed complement of a substring of s. Then, in a hairpin completion operation the reversed complement of this prefix/suffix is added to the start/end of s forming a new string.
In this paper we study two problems related to the hairpin completion. The first problem asks the minimum number of hairpin operations necessary to transform one string into another, number that is called the hairpin completion distance. For this problem we show an algorithm of running time O(n²), where n is the maximum length of the two strings. Our algorithm improves on the algorithm of Manea (TCS 2010), that has running time O(n² log n). 
In the minimum distance common hairpin completion ancestor problem we want to find, for two input strings x and y, a string w that minimizes the sum of the hairpin completion distances to x and y. Similarly, we present an algorithm with running time O(n²) that improves by a O(log n) factor the algorithm of Manea (TCS 2010).

Subject Classification

ACM Subject Classification
  • Theory of computation → Pattern matching
Keywords
  • dynamic programming
  • incremental trees
  • exact algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Stephen Alstrup and Jacob Holm. Improved algorithms for finding level ancestors in dynamic trees. In Ugo Montanari, José D. P. Rolim, and Emo Welzl, editors, Automata, Languages and Programming, pages 73-84, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg. Google Scholar
  2. Michael A Bender and Martın Farach-Colton. The level ancestor problem simplified. Theoretical Computer Science, 321(1):5-12, 2004. Google Scholar
  3. Henning Bordihn, Victor Mitrana, Andrei Păun, and Mihaela Păun. Hairpin completions and reductions: Semilinearity properties. Natural Computing: An International Journal, 20(2):193-203, June 2021. Google Scholar
  4. Daniela Cheptea, Carlos Martin-Vide, and Victor Mitrana. A new operation on words suggested by DNA biochemistry: Hairpin completion. Transgressive Computing, January 2006. Google Scholar
  5. Volker Diekert and Steffen Kopecki. Complexity results and the growths of hairpin completions of regular languages (extended abstract). In Michael Domaratzki and Kai Salomaa, editors, Implementation and Application of Automata, pages 105-114, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  6. Volker Diekert and Steffen Kopecki. It is NL-complete to decide whether a hairpin completion of regular languages is regular. Computing Research Repository - CORR, 22, January 2011. URL: https://arxiv.org/abs/22.
  7. Volker Diekert, Steffen Kopecki, and Victor Mitrana. On the hairpin completion of regular languages. In Martin Leucker and Carroll Morgan, editors, Theoretical Aspects of Computing - ICTAC 2009, pages 170-184, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
  8. Volker Diekert, Steffen Kopecki, and Victor Mitrana. Deciding regularity of hairpin completions of regular languages in polynomial time. Information and Computation, 217:12-30, 2012. Google Scholar
  9. Masami Ito, Peter Leupold, Florin Manea, and Victor Mitrana. Bounded hairpin completion. Information and Computation, 209(3):471-485, 2011. Special Issue: 3rd International Conference on Language and Automata Theory and Applications (LATA 2009). Google Scholar
  10. Haim Kaplan and Nira Shafrir. Path minima in incremental unrooted trees. In Dan Halperin and Kurt Mehlhorn, editors, Algorithms - ESA 2008, pages 565-576, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  11. Lila Kari, Stavros Konstantinidis, Elena Losseva, Petr Sosík, and Gabriel Thierrin. Hairpin structures in DNA words. In Alessandra Carbone and Niles A. Pierce, editors, DNA Computing, pages 158-170, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  12. Lila Kari, Stavros Konstantinidis, Petr Sosík, and Gabriel Thierrin. On hairpin-free words and languages. In Clelia De Felice and Antonio Restivo, editors, Developments in Language Theory, pages 296-307, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  13. Lila Kari, Steffen Kopecki, and Shinnosuke Seki. Iterated hairpin completions of non-crossing words. In Mária Bieliková, Gerhard Friedrich, Georg Gottlob, Stefan Katzenbeisser, and György Turán, editors, SOFSEM 2012: Theory and Practice of Computer Science, pages 337-348, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  14. Lila Kari, Elena Losseva, Stavros Konstantinidis, Petr Sosík, and Gabriel Thierrin. A formal language analysis of DNA hairpin structures. Fundamenta Informaticae, 71(4):453-475, 2006. Google Scholar
  15. Lila Kari, Kalpana Mahalingam, and Gabriel Thierrin. The syntactic monoid of hairpin-free languages. Acta Informatica, 44(3):153-166, June 2007. Google Scholar
  16. Donald E. Knuth, James H. Morris, and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6:323-350, 1977. Google Scholar
  17. Steffen Kopecki. On iterated hairpin completion. Theoretical Computer Science, 412(29):3629-3638, 2011. Google Scholar
  18. Florin Manea. A series of algorithmic results related to the iterated hairpin completion. Theoretical Computer Science, 411(48):4162-4178, 2010. Google Scholar
  19. Florin Manea, Carlos Martín-Vide, and Victor Mitrana. Hairpin lengthening. In Fernando Ferreira, Benedikt Löwe, Elvira Mayordomo, and Luís Mendes Gomes, editors, Programs, Proofs, Processes, pages 296-306, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  20. Florin Manea, Carlos Martín-Vide, and Victor Mitrana. On some algorithmic problems regarding the hairpin completion. Discrete Applied Mathematics, 157(9):2143-2152, 2009. Optimal Discrete Structures and Algorithms. Google Scholar
  21. Florin Manea, Carlos Martín-Vide, and Victor Mitrana. Hairpin lengthening: language theoretic and algorithmic results. Journal of Logic and Computation, 25(4):987-1009, January 2013. Google Scholar
  22. Florin Manea and Victor Mitrana. Hairpin completion versus hairpin reduction. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, Computation and Logic in the Real World, pages 532-541, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  23. Florin Manea, Victor Mitrana, and Takashi Yokomori. Two complementary operations inspired by the DNA hairpin formation: Completion and reduction. Theoretical Computer Science, 410(4):417-425, 2009. Computational Paradigms from Nature. Google Scholar
  24. Florin Manea, Victor Mitrana, and Takashi Yokomori. Some remarks on the hairpin completion. In International Journal of Foundations of Computer Science, 2010. Google Scholar
  25. James D. Watson and Francis H. Crick. Molecular structure of nucleic acids: A structure for deoxyribose nucleic acid. Nature, 171:737-738, 1953. Google Scholar
  26. Peter Weiner. Linear pattern matching algorithm. Proc. 14 IEEE Symposium on Switching and Automata Theory, pages 1-11, 1973. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact