On the Number of Many-to-Many Alignments of Multiple Sequences
arXiv:1511.00622v22 citations
Originality Synthesis-oriented
AI Analysis
This work addresses a theoretical problem in computational biology or sequence analysis, but it appears incremental as it focuses on a specific mathematical case.
The paper tackles the problem of counting the number of many-to-many alignments for multiple sequences, providing a new asymptotic formula for a specific case where match-up types are limited to values between 1 and 2.
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,\ldots,s_N) \:|\: 1\le s_i\le 2\}$.