The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *

DOI10.4230/LIPICS.WABI.2021.5MaRDI QIDQ6133865zbMATH OpenOpenAlexFDO

Authors Nicolas Boria, Laurent Gourvès, Vangelis Th. Paschos, Jérôme Monnot

Publication date 24 July 2023

Full work available at URL https://hal.science/hal-03435225

zbMATH Keywords

polynomial time approximation schememaximum-duo preservation string mappingbounded alphabet

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08)

Recommendations

• Improved approximation for the maximum duo-preservation string mapping problem
• Further improvement in approximating the maximum duo-preservation string mapping problem
• A family of approximation algorithms for the maximum duo-preservation string mapping problem
• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem
• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant

Cited in

(8)

• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem
• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• Improved approximation for the maximum duo-preservation string mapping problem
• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
• Approximating weighted duo-preservation in comparative genomics
• Solving the maximum duo-preservation string mapping problem with linear programming
• Further improvement in approximating the maximum duo-preservation string mapping problem

This page was built for publication: The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133865)