On the Number of Many-to-Many Alignments of Multiple Sequences

Abstract

We count the number of alignments of $N\ge 1$ sequences when match-up types are from a specified set $S\subseteq {\mathbb{N}}^N$. Equivalently, we count the number of nonnegative integer matrices whose rows sum to a given fixed vector and each of whose columns lie in $S$. We provide a new asymptotic formula for the case $S=\{(s_1,\dots ,s_N)|1\le s_i\le 2\}$.