The number of standard and of effective multiple alignments

被引：5

作者：

Dress, A ^{[1
]}

Morgenstern, B

Stoye, J

机构：

[1] Univ Bielefeld, Fak Math, D-33501 Bielefeld, Germany

[2] GSF, Natl Res Ctr Environm & Hlth, Inst Biomath & Biometry, D-85764 Neuherberg, Germany

[3] Univ Calif Davis, Dept Comp Sci, Davis, CA 95616 USA

来源：

APPLIED MATHEMATICS LETTERS | 1998年 / 11卷 / 04期

关键词：

computational biology; sequence analysis; sequence alignment; multiple alignment; enumerative combinatorics; Mobius inversion; exclusion/inclusion principle;

D O I：

10.1016/S0893-9659(98)00054-8

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study the number of all possible alignments of N sequences, N greater than or equal to 2, for two distinct alignment concepts proposed in the literature-standard alignments and effective alignments (consistent equivalence relations). Recursion formulae are developed to calculate these numbers. For standard alignments and for effective alignment of just two sequences, an explicit formula is also presented. The number of all effective alignments of a given site space is shown to be related to Stirling numbers of second kind. (C) 1998 Elsevier Science Ltd. All rights reserved.

引用

页码：43 / 49

页数：7

共 8 条

[1]

[Anonymous], 1983, SIAM REV

[2]

[Anonymous], 1969, FIBONACCI QUART

[3]

LAQUER HT, 1981, STUD APPL MATH, V64, P271

[4] Multiple DNA and protein sequence alignment based on segment-to-segment comparison [J].

Morgenstern, B ;

Dress, A ;

Werner, T .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1996, 93 (22) :12098-12103

[5]

MORGENSTERN B, UNPUB SOME THEORETIC

[6]

Rota G.C., 1964, Zeitschrift fur Wahrscheinlichkeitstheorie und verwandte Gebiete, V2, P340, DOI DOI 10.1007/BF00531932

[7]

Sloane N., 1995, The encyclopedia of integer sequences

[8]

Waterman M., 1995, INTRO COMPUTATIONAL

← 1 →