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.WABI.2021.5
URN: urn:nbn:de:0030-drops-143586
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14358/
Boria, Nicolas ;
Gourvès, Laurent ;
Paschos, Vangelis Th. ;
Monnot, Jérôme
The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet
Abstract
Given two strings A and B such that B is a permutation of A, the max duo-preservation string mapping (MPSM) problem asks to find a mapping π between them so as to preserve a maximum number of duos. A duo is any pair of consecutive characters in a string and it is preserved by π if its two consecutive characters in A are mapped to same two consecutive characters in B. This problem has received a growing attention in recent years, partly as an alternative way to produce approximation algorithms for its minimization counterpart, min common string partition, a widely studied problem due its applications in comparative genomics. Considering this favored field of application with short alphabet, it is surprising that MPSM^?, the variant of MPSM with bounded alphabet, has received so little attention, with a single yet impressive work that provides a 2.67-approximation achieved in O(n) [Brubach, 2018], where n = |A| = |B|. Our work focuses on MPSM^?, and our main contribution is the demonstration that this problem admits a Polynomial Time Approximation Scheme (PTAS) when ? = O(1). We also provide an alternate, somewhat simpler, proof of NP-hardness for this problem compared with the NP-hardness proof presented in [Haitao Jiang et al., 2012].
BibTeX - Entry
@InProceedings{boria_et_al:LIPIcs.WABI.2021.5,
author = {Boria, Nicolas and Gourv\`{e}s, Laurent and Paschos, Vangelis Th. and Monnot, J\'{e}r\^{o}me},
title = {{The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet}},
booktitle = {21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
pages = {5:1--5:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-200-6},
ISSN = {1868-8969},
year = {2021},
volume = {201},
editor = {Carbone, Alessandra and El-Kebir, Mohammed},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14358},
URN = {urn:nbn:de:0030-drops-143586},
doi = {10.4230/LIPIcs.WABI.2021.5},
annote = {Keywords: Maximum-Duo Preservation String Mapping, Bounded alphabet, Polynomial Time Approximation Scheme}
}
Keywords: |
|
Maximum-Duo Preservation String Mapping, Bounded alphabet, Polynomial Time Approximation Scheme |
Collection: |
|
21st International Workshop on Algorithms in Bioinformatics (WABI 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
22.07.2021 |