Configurations and minority in the string consensus problem (Q289911)

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.