Phase-independent rhythmic analysis of genome-wide expression patterns

ABSTRACT

We introduce a model-based analysis technique for extracting and characterizing rhythmic expression profiles from genome-wide DNA microarray hybridization data. These patterns are clues to discovering rhythmic genes implicated in cell-cycle, circadian, and other biological processes. The algorithm, implemented in a program called RAGE (Rhythmic Analysis of Gene Expression), decouples the problems of estimating a pattern's periodicity and phase. Our algorithm is linear-time in frequency and phase resolution, an improvement over previous quadratic-time approaches. Unlike previous approaches, RAGE uses a true distance metric for measuring expression profile similarity, based on the Hausdorff distance. This results in better clustering of expression profiles for rhythmic analysis. The confidence of each frequency estimate is computed using Z-scores. We demonstrate that RAGE is superior to other techniques on synthetic and actual DNA microarray hybridization data. We also show how to replace the discretized phase search in our method with an exact (combinatorially precise) phase search, resulting in a faster algorithm with no complexity dependence on phase resolution.

REFERENCES

• 1: [1] Stanford Microarray Database. http://genome- www4.stanford.edu/MicroArray/SMD/.
• 2: [2] H. Araki, R. K. Hamatake, A. Morrison, A. L. Johnson, L. H. Johnston, and Sugino A. Cloning DPB3, the gene encoding the third subunit of DNA polymerase II of Saccharomyces cerevisiae. Nucleic Acids Res, 19:4867-4872, 1991.
• 3: Esther M. Arkin , L. Paul Chew , Daniel P. Huttenlocher , Klara Kedem , Joseph S. B. Mitchell, An Efficiently Computable Metric for Comparing Polygonal Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.3, p.209-216, March 1991 [doi>10.1109/34.75509]
• 4: [4] A. Balsalobre, F. Damiola, and U. Schibler. A Serum Shock Induces Circadian Gene Expression in Mammalian Tissue Culture Cells. Cell, 93:929-937, 1998.
• 5: [5] E. Belogay, C. Cabrelli, U. Molter, and R. Shonkwiler. Calculating the Hausdorff distance between curves. Information Processing Letters, 64(1):17-22, 1997.
• 6: [6] L. H. Caro, G. J. Smits, P. van Egmond, J. W. Chapman, and F. M. Klis. Transcription of multiple cell wall protein-encoding genes in Saccharomyces cerevisiae is deferentially regulated during the cell cycle. FEMS Microbiol. Lett, 161:345-349, 1998.
• 7: [7] J. W. Chapman and Johnston L. H. The yeast gene, dbf4, essential for entry into s phase is cell cycle regulated. Exp. Cell Res., 180:419-428, 1989.
• 8: [8] R. Cho, M. Campbell, E. Winzeler, L. Steinmetz, A. Conway, L. Wodicka, T. Wolfsberg, A. Gabrielian, D. Landsman, D. Lockhart, and R. Davis. A genome-wide transcriptional analysis of the mitotic cell cycle. Mol. Cell, 2:65-73, 1998.
• 9: [9] A. Claridge-Chang, H. Wijnen, F. Naef, C. Boothroyd, N. Rajewsky, and M. W. Young. Circadian Regulation of Gene Expression Systems in the Drosophila Head. Neuron, 32:657-671, 2001.
• 10: [10] B. R. Donald, D. Kapur, and J. Mundy. Symbolic and Numerical Computation for Artificial Intelligence, chapter 8, "Distance metrics for comparing shapes in the plane," by D. Huttenlocher and K. Kedem, pages 201-219. Academic Press, Harcourt Jovanovich, London, 1992.
• 11: [11] M. Eisen, P. T. Spellman, D. Botstein, and P. O. Brown. Cluster Analysis and display of genome-wide expression patterns. Proc. Natl. Acad. Sci., 95(25):14863-14868, 1998.
• 12: Vladmir Filkov , Steven Skiena , Jizu Zhi, Analysis techniques for microarray time-series data, Proceedings of the fifth annual international conference on Computational biology, p.124-131, April 22-25, 2001, Montreal, Quebec, Canada [doi>10.1145/369133.369183]
• 13: [13] I. Fitch, C. Dahmann, U. Surana, A. Amon, K. Nasmyth, L. Goetsch, B. Byers, and Futcher B. Characterization of four B-type cyclin genes of the budding yeast Saccharomyces cerevisiae. Mol. Biol. Cell, 3:805-818, 1992.
• 14: [14] C. Grundschober, F. Delaunay, A. Phlhofer, G. Trique neaux, V. Laudet, T. Bartfai, and P. Nef. Circadian Regulation of Diverse Gene Products Revealed by mRNA Expression Profiling of Synchronized Fibroblasts. J. Biol. Chem., 276:46751-46758, 2001.
• 15: [15] S. Harmer, J. B. Hogenesch, M. Straume, H. S. Chang, B. Han, T. Zhu, X. Wang, J. A. Kreps, and S. A. Kay. Orchestrated Transcription of Key Pathways in Arabidopsis by the Circadian Clock. Science, 290:2110-2113, 2000.
• 16: Daniel P. Huttenlocher , Klara Kedem, Computing the minimum Hausdorff distance for point sets under translation, Proceedings of the sixth annual symposium on Computational geometry, p.340-349, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98599]
• 17: [17] J. C. Igual, A. L. Johnson, and L. H. Johnston. Coordinated regulation of gene expression by the cell cycle transcription factor Swi4 and the protein kinase C MAP kinase pathway for yeast cell integrity. EMBO J., 15:5001-5013, 1996.
• 18: [18] V. R. Iyer, M. B. Eisen, D. T. Ross, G. Schuler, T. Moore, J. C. F. Lee, J. M. Trent, L. M. Staudt, J. Jr Hudson, M. S. Boguski, D. Lashkari, D. Shalon, D. Botstein, and P. O. Brown. The transcriptional program in the response of human fibroblasts to serum. Science, 283:83-87, 1999.
• 19: [19] L. H. Johnston, J. H. White, A. L. Johnson, G. Lucchini, and P. Plevani. Expression of the yeast DNA primase gene, PRI1, is regulated within the mitotic cell cycle and in meiosis. Mol. Gen. Genet., 221:44-48, 1990.
• 20: [20] M. J. McDonald and M. Rosbash. Microarray analysis and organization of circadian gene expression in Drosophila. Cell, 107:567-578, 2001.
• 21: [21] D. Mumford. The problem of robust shape descriptors. Proc. 1st Int. Conf. Comput. Vision, pages 602-606, 1987.
• 22: [22] R. Schaffer, J. Landgraf, M. Accerbi, V. Simon, M. Larson, and E. Wisman. Microarray analysis of diurnal and circadian-regulated genes in Arabidopsis. Plant Cell, 13:113- 123, 2001.
• 23: [23] W. Siede, G. W. Robinson, D. Kalainov, T. Malley, and E. C. Friedberg. Regulation of the RAD2 gene of Saccharomyces cerevisiae. Mol. Microbiol, 3:1697-1707, 1989.
• 24: [24] P. Spellman, G. Sherlock, M. Q. Zhang, R. I. Iyer, K. Anders, M. B. Eisen, P. O. Brown, D. Botstein, and B. Futcher. Comprehensive identification of cell cycle-regulated genes of the yeast Saccharomyces cerevisiae by Microarray Hybridization. Mol. Biol. Cell, 9(12):3273-3297, 1998.
• 25: [25] J. Wan, H. Xu, and M. Grunstein. Cdcl4 of Saccharomyces cerevisiae. Cloning, sequence analysis, and transcription during the cell cycle. J. Biol. Chem., 267:11274-11280, 1992.
• 26: [26] J. H. White, S. R. Green, D. G. Barker, L. B. Dumas, and L. H. Johnston. The cdc8 transcript is cell cycle regulated in yeast and is expressed coordinately with cdc9 and cdc21 at a point preceding histone transcription. Exp. Cell Res., 171:223-231, 1987.
• 27: [27] K. Yagita, F. Tamanini, G. T. J. van der Horst, and H. Okamura. Molecular Mechanisms of the Biological Clock in Cultured Fibroblasts. Science, 292:278-281, 2001.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Performance