<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue3" %>
Fibonacci-Cayley Numbers and Repetition Patterns in Genomic DNA
Andreas Dress1, Robert Giegerich2, Stefan Gr邦newald1, and Holger Wagner2
1FSPM, Fakultät für Mathematik, Universität Bielefeld, Postfach 100131, 33501 Bielefeld, Germany
{dress, grunew}@mathematik.uni-bielefeld.de
2CeBiTec, Technische Fakultät, Universität Bielefeld, Postfach 100131, 33501 Bielefeld, Germany
robert@techfak.uni-bielefeld.de, hwagner@mathematik.uni-bielefeld.de
Annals of Combinatorics 7 (3) p.259-279 September, 2003
AMS Subject Classification: 11B39, 11A99, 92D20
Let F(k) denote the k-th Fibonacci number in the Fibonacci sequence F(0):=0, F(1):=1, ..., F(k+1):=F(k-1)+F(k). Motivated by proposals regarding putative mechanisms that may be responsible for producing those often observed long repetitive patterns in genomic DNA, we study in this note the Fibonacci-Cayley index fcx of positive integers x, i.e., the largest integer for which positive integers a, b with x=aF(k-1)+bF(k) exist and show that


holds for the arithmetic mean (kr+ k1)/2 of the indices of the smallest and the largest Fibonacci numbers occurring in the Zeckendorf decomposition (0 < k1 -1 < k2 -2 < ... < kr-r) of x.

Keywords: repetitive genomic DNA, Fibonacci-Cayley numbers, Fibonacci numbers, Lucas numbers, Zeckendorf's theorem


1. S.L. Basin, The Fibonacci sequence as it appears in nature, Fibonacci Quart. 1 (1963) 53每56.

2. G. Benson, Sequence alignment with tandem duplication, J. Comp. Biol. 4 (1997) 351每367.

3. G. Benson and L. Dong, Reconstructing the duplication history of a tandem repeat, In: Proceedings of the Intelligent Systems in Molecular Biology ISMB'99, 1999.

4. J.R. Brown Jr., Zeckendorf's theorem and some applications, Fibonacci Quart. 2 (1964) 162每168.

5. J. Buard and A.J. Jeffreys, Big, bad minisatellites, Nature Genetics 15 (1997) 327每328.

6. T.A. Davis, Why Fibonacci sequence in palm leafs, Fibonacci Quart. 9 (1971) 237每244.

7. B.S. Davis and T.A. Davis, Fibonacci number and golden mean in nature, Math. Sci. 14 (1989) 89每100.

8. S. Kurtz and C. Schleiermacher, REPuter: fast computation of maximal repeats in complete genomes, Bioinformatics 15 (1999) 426每427.

9.; V.E. Hoggatt, A favorable response, Fibonacci Quart. 3 (1965) 123每127.

10. V.E. Hoggatt Jr., A power identity for second-order recurrence relation, Fibonacci Quart. 4 (1966) 274每282.

11. E.J. Karchmar, Phylotaxis, Fibonacci Quart. 3 (1965) 64每66.

12. E. Levin, The Fibonacci series, www.goldenmeangauge.co.uk/fibonacci.htm.

13. E. Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math. 1 (1878) 184每240.

14. Nature 409 (2001).

15. P.V. Satyanarayama Murthy, Fibonacci-Cayley numbers, Fibonacci Quart. 20 (1982) 59每64.

16. L. Taylor, Residues of Fibonacci-like sequences, Fibonacci Quart. 5 (1967) 298每304.

17. E. Zeckendorf, A generalized Fibonacci numeration, Fibonacci Quart. 10 (1972) 365每372.