On the string consensus problem and the Manhattan sequence consensus problem

DOI10.1016/J.TCS.2017.03.022zbMATH Open1387.68311arXiv1407.6144OpenAlexW2599391063MaRDI 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)

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.

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

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

zbMATH Keywords

closest string problemcenter string problemsequence consensus problem

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

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

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)