A Hill-Climbing Approach for Automatic Gridding of cDNA Microarray Images

ABSTRACT

Image and statistical analysis are two important stages of cDNA microarrays. Of these, gridding is necessary to accurately identify the location of each spot while extracting spot intensities from the microarray images and automating this procedure permits high-throughput analysis. Due to the deficiencies of the equipment used to print the arrays, rotations, misalignments, high contamination with noise and artifacts, and the enormous amount of data generated, solving the gridding problem by means of an automatic system is not trivial. Existing techniques to solve the automatic grid segmentation problem cover only limited aspects of this challenging problem and require the user to specify the size of the spots, the number of rows and columns in the grid, and boundary conditions. In this paper, a hill-climbing automatic gridding and spot quantification technique is proposed which takes a microarray image (or a subgrid) as input and makes no assumptions about the size of the spots, rows, and columns in the grid. The proposed method is based on a hill-climbing approach that utilizes different objective functions. The method has been found to effectively detect the grids on microarray images drawn from databases from GEO and the Stanford genomic laboratories.

REFERENCES

• 1: [1] J. Angulo and J. Serra, "Automatic Analysis of DNA Microarray Images Using Mathematical Morphology," Bioinformatics, vol. 19, no. 5, pp. 553-562, 2003.
• 2: Giuliano Antoniol , Michele Ceccarelli, A Markov Random Field Approach to Microarray Image Gridding, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 3, p.550-553, August 23-26, 2004 [doi>10.1109/ICPR.2004.50]
• 3: Alison Cawsey, The Essence of Artificial Intelligence, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 4: [4] S. Draghici, Data Analysis Tools for DNA Microarrays. Chapman & Hall/CRC, 2003.
• 5: [5] A. Jain, T. Tokuyasu, A. Snijders, R. Segraves, D. Albertson, and D. Pinkel, "Fully Automatic Quantification of Microarray Data," Genome Research, vol. 12, no. 2, pp. 325-332, 2002.
• 6: Mathias Katzer , Franz Kummert , Gerhard Sagerer, A Markov Random Field model of microarray gridding, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952551]
• 7: [7] M. Katzer, F. Kummert, and G. Sagerer, "Automatische Auswertung von Mikroarraybildern," Proc. Workshop Bildverarbeitung für die Medizin, 2002.
• 8: B. John Oommen , Luis G. Rueda, A formal analysis of why heuristic functions work, Artificial Intelligence, v.164 n.1-2, p.1-22, May 2005 [doi>10.1016/j.artint.2002.02.001]
• 9: [9] L. Rueda and L. Qin, "An Improved Clustering-Based Approach for DNA Microarray Image Segmentation," Proc. Int'l Conf. Image Analysis and Recognition, pp. 17-24, 2004.
• 10: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 11: [11] M. Schena, Microarray Analysis. John Wiley & Sons, 2002.
• 12: [12] G. Sherlock, T. Hernandez-Boussard, A. Kasarskis, G. Binkley, J. Matese, S. Dwight, M. Kaloper, S. Weng, H. Jin, C. Ball, M.B. Eisen, P.T. Spellman, P.O. Brown, D. Botstein, and J.M. Cherry, "The Stanford Microarray Database," Nucleic Acids Research, vol. 29, pp. 152-155, 2001.
• 13: [13] M. Steinfath, W. Wruck, and H. Seidel, "Automated Image Analysis for Array Hybridization Experiments," Bioinformatics, vol. 17, no. 7, pp. 634-641, 2001.
• 14: [14] S. Subramanian, R. West, R. Marinelli, T. Nielsen, B. Rubin, J. Goldblum, R. Patel, S. Zhu, K. Montgomery, T. Ng, C. Corless, M. Heinrich, and M. van de Rijn, "The Gene Expression Profile of Extraskeletal Myxoid Chondrosarcoma," J. Pathology, vol. 206, no. 4, pp. 433-444, 2005.
• 15: [15] K. Sullivan and S. Jacobson, "A Convergence Analysis of Generalized Hill-Climbing Algorithms," IEEE Trans. Automatic Control, vol. 46, no. 8, pp. 1288-1293, 2001.
• 16: [16] V. Vidyadharan, "Automatic Gridding of DNA Microarray Images," master's thesis, School of Computer Science, Univ. of Windsor, Canada, 2004, http://www.cs.uwindsor.ca/lrueda/ papers/VidyaThesis.pdf.
• 17: [17] Y. Yang, M. Buckley, S. Dudoit, and T. Speed, "Comparison of Methods for Image Analysis on cDNA Microarray Data," J. Computational and Graphical Statistics, vol. 11, pp. 108-136, 2002.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
        I.4.10 Image Representation
            Subjects: Statistical
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Design

Keywords:
cDNA Microarrays, gene expression, gridding, hill-climbing.