Configurations and minority in the string consensus problem

DOI10.1007/S00453-015-9996-7MaRDI QIDQ289911zbMATH OpenOpenAlexFDO

Authors Amihood Amir, Haim Paryenty, Liam Roditty

Publication date 31 May 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-015-9996-7

zbMATH Keywords

closest string problemconfiguration algorithmconsensus stringHamming distanceminority algorithm

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Review text

For the Closest String Problem we are given \(k\) strings of length \(\ell\) and asked to find a so-called consensus string minimizing the maximum Hamming distance between any of the input strings and that consensus string. The authors present two algorithms that solve this problem exactly, which they name the Configuration Algorithm and the Minority Algorithm. The former is simple, incremental (i.e., it outputs the \(i\)th letter of the consensus string after reading the \(i\)th letter of each input string) and runs in \(O (k^2 \ell^k)\) time. The latter is more complicated but allows the authors to find a consensus string for five input strings in only \(O (\ell^2)\) time. The authors note that \textit{J. Gramm} et al. [Algorithmica 37, No. 1, 25--42 (2003; Zbl 1058.68119)] already gave an algorithm that theoretically uses \(O (\ell)\) time for any constant \(k\), but that it is impractical for more than four input strings.

Recommendations

• Configurations and minority in the string consensus problem
• scientific article; zbMATH DE number 2081011
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Closest Substring Problems with Small Distances
• On the closest string and substring problems

Cites work

• A closer look at the closest string and closest substring problem
• A linear-time algorithm for the 1-mismatch problem
• Configurations and minority in the string consensus problem
• Distinguishing string selection problems.
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• scientific article; zbMATH DE number 2081011 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• More efficient algorithms for closest string and substring problems
• On covering problems of codes
• On the closest string and substring problems
• Optimal solutions for the closest-string problem via integer programming

Cited in

(6)

• Two-string consensus problem under non-overlapping inversion and transposition distance
• On the string consensus problem and the Manhattan sequence consensus problem
• Configurations and minority in the string consensus problem
• Configurations and minority in the string consensus problem
• On the string consensus problem and the Manhattan sequence consensus problem
• Parameterized complexity of submodular minimization under uncertainty

This page was built for publication: Configurations and minority in the string consensus problem

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