License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2023.5
URN: urn:nbn:de:0030-drops-179592
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17959/
Boneh, Itai ;
Fried, Dvir ;
Miclăuş, Adrian ;
Popa, Alexandru
Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor
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).
BibTeX - Entry
@InProceedings{boneh_et_al:LIPIcs.CPM.2023.5,
author = {Boneh, Itai and Fried, Dvir and Micl\u{a}u\c{s}, Adrian and Popa, Alexandru},
title = {{Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor}},
booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
pages = {5:1--5:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-276-1},
ISSN = {1868-8969},
year = {2023},
volume = {259},
editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17959},
URN = {urn:nbn:de:0030-drops-179592},
doi = {10.4230/LIPIcs.CPM.2023.5},
annote = {Keywords: dynamic programming, incremental trees, exact algorithm}
}
|
Keywords: |
|
dynamic programming, incremental trees, exact algorithm |
|
Collection: |
|
34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
21.06.2023 |
