On the string consensus problem and the Manhattan sequence consensus problem

DOI10.1016/J.TCS.2017.03.022zbMATH Open1387.68311OpenAlexW2599391063MaRDI QIDQ1698720FDOQ1698720

Authors Tomasz Kociumaka, Jakub W. Pachocki, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń 

Publication date 16 February 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.6144

zbMATH Keywords

closest string problemcenter string problemsequence consensus problem

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Abstract: In the Manhattan Sequence Consensus problem (MSC problem) we are given $k$ integer sequences, each of length $l$, and we are to find an integer sequence $x$ of length $l$ (called a consensus sequence), such that the maximum Manhattan distance of $x$ from each of the input sequences is minimized. For binary sequences Manhattan distance coincides with Hamming distance, hence in this case the string consensus problem (also called string center problem or closest string problem) is a special case of MSC. Our main result is a practically efficient $O(l)$-time algorithm solving MSC for $kle5$ sequences. Practicality of our algorithms has been verified experimentally. It improves upon the quadratic algorithm by Amir et al. (SPIRE 2012) for string consensus problem for $k=5$ binary strings. Similarly as in Amir's algorithm we use a column-based framework. We replace the implied general integer linear programming by its easy special cases, due to combinatorial properties of the MSC for $kle5$. We also show that for a general parameter $k$ any instance can be reduced in linear time to a kernel of size $k!$, so the problem is fixed-parameter tractable. Nevertheless, for $kge4$ this is still too large for any naive solution to be feasible in practice.

Recommendations

• On the string consensus problem and the Manhattan sequence consensus problem
• On the hardness of the consensus string problem
• Configurations and minority in the string consensus problem
• Configurations and minority in the string consensus problem
• Two-string consensus problem under non-overlapping inversion and transposition distance
• Consensus strings with small maximum distance and small distance sum
• Consensus strings with small maximum distance and small distance sum
• The consensus string problem for a metric is NP-complete
• Efficient algorithms for consensus string problems minimizing both distance sum and radius

Cites Work

• scientific article; zbMATH DE number 1305456 (Why is no real title available?)
• Algorithms - ESA 2003
• An application of simultaneous diophantine approximation in combinatorial optimization
• An efficient, exact, and generic quadratic programming solver for geometric optimization
• Approximate clustering via core-sets
• Approximate minimum enclosing balls in high dimensions using core-sets
• Configurations and minority in the string consensus problem
• Finding the longest isometric cycle in a graph
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Integer Programming with a Fixed Number of Variables
• Introduction to algorithms.
• Long packing and covering codes
• Minkowski's Convex Body Theorem and Integer Programming
• More efficient algorithms for closest string and substring problems
• On covering problems of codes
• On the closest string and substring problems
• On the covering radius of codes
• On the hardness of the consensus string problem
• On the string consensus problem and the Manhattan sequence consensus problem

Cited In (3)

• Efficient algorithms for consensus string problems minimizing both distance sum and radius
• On the string consensus problem and the Manhattan sequence consensus problem
• Two-string consensus problem under non-overlapping inversion and transposition distance

Uses Software

• Miniball

This page was built for publication: On the string consensus problem and the Manhattan sequence consensus problem

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