Columns of uniform color in a rectangular array with rows having cyclically repeated color patterns (Q1613553)

The paper studies the following problem, which was motivated by the multiple sequence alignment problem of computational biology. It is far from obvious what is the exact optimization problem that multiple sequence alignment has to solve. Details of the objective function are described by scoring schemes. Solution to the problem studied here may provide ways to design better scoring schemes. Let \(p_1,\dots,p_n\) be pairwise coprime positive integers, and \(m>1\) integer. Suppose we have \(nP\) balls of each of \(m\) colors. Let \(0,1,\dots,m-1\) denote the colors. Arrange all \(mnP\) balls in rows, such that each row has \(P\) balls of each color. Let the \(i\)th row contain in cyclic succession \(p_i\) balls of color \(0\), \(p_i\) balls of color \(1\),\dots, \(p_i\) balls of color \(m-1\), \(p_i\) balls of color \(0\), etc. A column is monochromatic if only one color is present in it. The problem is to find the number of monochromatic columns and the number of \(k\) consecutive monochromatic columns of the same color. The paper solves this problem in the following special cases: (i) \(m=2\); (ii) all \(p_i\)'s are congruent modulo \(m\); \(n=2\). The main tool is the Chinese remainder theorem.