Garg, Shilpa ;
Mömke, Tobias
A QPTAS for Gapless MEC
Abstract
We consider the problem Minimum Error Correction (MEC). A MEC instance is an n x m matrix M with entries from {0,1,}. Feasible solutions are composed of two binary mbit strings, together with an assignment of each row of M to one of the two strings. The objective is to minimize the number of mismatches (errors) where the row has a value that differs from the assigned solution string. The symbol "" is a wildcard that matches both 0 and 1. A MEC instance is gapless, if in each row of M all binary entries are consecutive.
GaplessMEC is a relevant problem in computational biology, and it is closely related to segmentation problems that were introduced by {[}KleinbergPapadimitriouRaghavan STOC'98{]} in the context of data mining.
Without restrictions, it is known to be UGhard to compute an O(1)approximate solution to MEC. For both MEC and GaplessMEC, the best polynomial time approximation algorithm has a logarithmic performance guarantee. We partially settle the approximation status of GaplessMEC by providing a quasipolynomial time approximation scheme (QPTAS). Additionally, for the relevant case where the binary part of a row is not contained in the binary part of another row, we provide a polynomial time approximation scheme (PTAS).
BibTeX  Entry
@InProceedings{garg_et_al:LIPIcs:2018:9497,
author = {Shilpa Garg and Tobias M{\"o}mke},
title = {{A QPTAS for Gapless MEC}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {34:134:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9497},
URN = {urn:nbn:de:0030drops94978},
doi = {10.4230/LIPIcs.ESA.2018.34},
annote = {Keywords: approximation algorithms, QPTAS, minimum error correction, segmentation, computational biology}
}
2018
Keywords: 

approximation algorithms, QPTAS, minimum error correction, segmentation, computational biology 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 