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

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 (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
Volume6
Issue number2
DOIs
StatePublished - Jun 1990

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

Cite this