0,2

This counts effective alignments rather than standard alignments, so that for example the following two alignments are equivalent:

-A A-

-T T-

C- -C

See Dress, Morgenstern and Stoye for more information.

A. Dress, B. Morgenstern and J. Stoye, On the number of standard and of effective multiple alignments, Applied Mathematics Letters, Vol. 11, No. 4, 1998, pp. 43-49.

A. Dress, B. Morgenstern and J. Stoye, On the number of standard and of effective multiple alignments, 1998.

The recurrence is three dimensional with the order of the three parameters immaterial. That is, a(i,j,k)=a(i,k,j)=a(j,i,k)=a(j,k,i)=a(k,i,j)=a(k,j,i). a(i, j, 0) = (i+j)! / i! / j! a(i, j, k) = a(i-1,j,k) + a(i,j-1,k) + a(i,j,k-1) - a(i-1,j-1,k-1)

a(1) = 5 because the five alignments are

A-- A- A- A- A

-C- C- -C -C C

--T -T T- -T T

Sequence in context: A142009 A067393 A113265 this_sequence A123034 A166619 A113064

Adjacent sequences: A124432 A124433 A124434 this_sequence A124436 A124437 A124438

nonn

Lee A. Newberg (integer(AT)quantconsulting.com), Dec 15 2006