2026-08-08T02:42:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14358 2024-03-06T10:53:58Z ddc:004 open_access

The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet Boria, Nicolas Gourvès, Laurent Paschos, Vangelis Th. Monnot, Jérôme Maximum-Duo Preservation String Mapping Bounded alphabet Polynomial Time Approximation Scheme 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Boria and Laurent Gourvès and Vangelis Th. Paschos and Jérôme Monnot 2021 Is Part Of LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2021.5 urn:nbn:de:0030-drops-143586 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.5 eng https://creativecommons.org/licenses/by/4.0/legalcode