On the number of alignments of k sequences

Abstract

Numerous studies by molecular biologists concern the relationships between several long DNA sequences, which are listed in rows with some gaps inserted and with similar positions aligned vertically. This motivates our interest in estimating the number of possible arrangements of such sequences. We say that a k sequence alignment of size n is obtained by inserting some (or no) 0's into k sequences of n 1's so that every sequence has the same length and so that there is no position which is 0 in all k sequences. We show by a combinatorial argument that for any fixed k ≥1, the number f(k, n) of k alignments of length n grows like ( c k ) n as n → ∞ , where c k = (2 1/ k − 1) -k . A multi-dimensional saddle-point method is used to give a more precise estimate for f(k, n).