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

Abstract

Let \(\mathbf{X}^{(1)}_{n},\ldots,\mathbf{X}^{(m)}_{n}\), where \(\mathbf{X}^{(i)}_{n}=(X^{(i)}_{1},\ldots,X^{(i)}_{n})\), \(i=1,\ldots,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.