The number of standard and of effective multiple alignments

AbstractWe study the number of all possible alignments of N sequences, N ≥ 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