On the number of alignments of k sequences

J. R. Griggs, P. Hanlon, A. M. Odlyzko, M. S. Waterman

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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 (ck)nas n → ∞, where ck = (21/k - 1)-k. A multi-dimensional saddle-point method is used to give a more precise estimate for f(k, n).

Original languageEnglish (US)
Pages (from-to)133-146
Number of pages14
JournalGraphs and Combinatorics
Issue number2
StatePublished - Jun 1990


Dive into the research topics of 'On the number of alignments of k sequences'. Together they form a unique fingerprint.

Cite this