|
| |
|
|
A124435
|
|
Number of effective multiple alignments of three equal-length sequences.
|
|
0
| |
|
|
1, 5, 67, 1109, 20251, 391355, 7847155, 161476565, 3387271675, 72114452255, 1553475100717
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| 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.
|
|
|
REFERENCES
| 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.
|
|
|
LINKS
| A. Dress, B. Morgenstern and J. Stoye, On the number of standard and of effective multiple alignments, 1998.
|
|
|
FORMULA
| 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)
|
|
|
EXAMPLE
| a(1) = 5 because the five alignments are
A-- A- A- A- A
-C- C- -C -C C
--T -T T- -T T
|
|
|
CROSSREFS
| Sequence in context: A142009 A067393 A113265 * A123034 A166619 A113064
Adjacent sequences: A124432 A124433 A124434 * A124436 A124437 A124438
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Lee A. Newberg (integer(AT)quantconsulting.com), Dec 15 2006
|
| |
|
|
