A Central Limit Theorem for the Optimal Alignments Score in Multiple Random Words

Let ${\mathbf{X}}_n^{(1)},\dots ,{\mathbf{X}}_n^{(m)}$, where ${\mathbf{X}}_n^{(i)}=(X_1^{(i)},\dots ,X_n^{(i)})$, $i=1,\dots ,m$, be $m$ independent sequences of independent and identically distributed random variables taking their values in a finite alphabet $\mathcal{A}$. Let the score function $S$, defined on ${\mathcal{A}}^m$, be non-negative, bounded, permutation-invariant, and satisfy a bounded differences condition. Under a variance lower-bound assumption, a central limit theorem is proved for the optimal alignments score of the $m$ random words.