Open Access Open Access  Restricted Access Subscription or Fee Access

A Cellular Automata Based DNA Pattern Classifier

Tamal Chakrabarti, Sourav Saha, Devadatta Sinha


Contemporary researchers of Bio-informatics have witnessed an exponential growth in the amount of biological information over the years. The increasing volume of DNA sequences has of late created interest among many scientists in computational approaches to DNA sequence analysis. A lot of computer analysis of DNA sequences is directed toward meaningful interpretation of biologically significant patterns. Pattern classification forms one of the most important foundations for extraction of knowledge from the enormous DNA sequence databases. This paper reports a cheap and efficient DNA pattern classifier based on the sparse network of Cellular Automata.


Bio-informatics, Cellular Automata, DNA, Pattern Classification, Sequence Analysis

Full Text:



Stefania Bandini. Guest Editorial - Cellular Automata. Future Generation Computer Systems, 18:v–vi, August 2002.

A. Albicki, S. K. Yap, M. Khare, and S. Pamper. Prospects on Cellular Automata Application to Test Generation. Technical Report EL-88-05, Dept. of Electrical Engg., Univ. of Rochester, 1988.

H. Baltzer, W. P. Braun, and W. Kohler. Cellular Automata Model for Vegetable Dynamics. Ecological Modelling, 107:113–125, 1998.

S. Wolfram, “Theory and application of Cellular Automata”, World Scientific, 1986.

P. H. Bardell. Analysis of Cellular Automata used as Pseudo-Random Pattern Generators. In International Test Conference, pages 762–768, 1990.

C. Burks and D. Farmer. Towards Modeling DNA Sequences as Automata. Physica D, 10:157–167, 1984.

J. H. Moore and L. W. Hahn. A Cellular Automata-based Pattern Recognition Approach for Identifying Gene-Gene and Gene-Environment Interactions. American Journal of Human Genetics, 67(52), 2000.

J. H. Moore and L. W. Hahn. Multilocus Pattern Recognition using Cellular Automata and Parallel Genetic Algorithms. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO-2001), page 1452, 7-11 July 2001.

A. Albicki and M. Khare. Cellular Automata used for Test Pattern Generation. In Proc. ICCD, pages 56–59, 1987.

A. Albicki and S. K. Yap. Covering a Set of Test Patterns by a Cellular Automata. Research Review, Dept. of Comp. Sc. and Engg., Univ. of Rochester, 1987.

E. R. Banks. Information Processing and Transmission in Cellular Automata. PhD thesis, M. I. T., 1971.

S. C. Benjamin and N. F. Johnson. A Possible Nanometer-scale Computing Device based on an Adding Cellular Automaton. Applied Physics Letters, 1997.

A. M. Barbe. A Cellular Automata Ruled by an Eccentric Conservation Law. Physica D, 45:49–62, 1990.

Jianbo Gao, Yan Qi, Yinhe Cao, and Wen-wen Tung, "Protein Coding Sequence Identification by Simultaneously Characterizing the Periodic and Random Features of DNA Sequences", Journal of Biomedicine and Biotechnology, Vol. 2, pp. 139–146, 2005.

Peterson, D.; Lee, C.H., "A DNA-based pattern recognition technique for cancer detection," Engineering in Medicine and Biology Society, 2004. IEMBS '04. 26th Annual International Conference of the IEEE , vol.2, no., pp.2956,2959, 1-5 Sept. 2004 doi: 10.1109/IEMBS.2004.1403839

Ido Priness, Oded Maimon and Irad Ben-Gal, “Evaluation of gene-expression clustering via mutual information distance measure”, BMC Bioinformatics 2007, 8:111 doi:10.1186/1471-2105-8-111

David Kulp, avid Haussler, Martin G. Reese Frank, H. Eeckman, “A Generalized Hidden Markov Model for the Recognition of Human Genes in DNA”, ISMB-96 Proceedings, 1996.

Sathish Kumar S, N.Duraipandian, “An Effective Identification of Species from DNA Sequence: A Classification Technique by Integrating DM and ANN”, International Journal of Advanced Computer Science and Applications, Vol. 3, No.8, , pp. 104–114, 2012.

A. W. Burks. Essays on Cellular Automata. Technical Report, Univ. of Illinois, Urbana, 1970.

S. Bhattacharjee, J. Bhattacharya, and P. Pal Chaudhuri. An Efficient Data Compression based on Cellular Automata. In Data Compression Conference (DCC95), 1995.

Stephen A Billings and Yingxu Yang. Identification of Probabilistic Cellular Automata. IEEE Transaction on System, Man and Cybernetics, Part B, pages 1–12, 2002.

M. S. Capcarrere. Cellular Automata and Other Cellular System: Design and Evolution. PhD thesis, Swiss Federal Institute of Technology, Luassane, 2002.

S. Chakraborty, D. Roy Chowdhury, and P. Pal Chaudhuri. Theory and Application of Non-Group Cellular Automata for Synthesis of Easily Testable Finite State Machines. IEEE Trans. on Computers, 45(7):769–781, July 1996.

S. Chattopadhyay, S. Adhikari, S. Sengupta, and M. Pal. Highly Regular, Modular, and Cascadable Design of Cellular Automata-based Pattern Classifier. IEEE Transaction on VLSI Systems, 8(6):724–735, December 2000.

N. Ganguly, P. Maji, S. Dhar, B. K. Sikdar, and P. Pal Chaudhuri. Evolving Cellular Automata as Pattern Classifier. In Proc. of Fifth International Conference on Cellular Automata for Research and Industry, ACRI 2002, Switzerland, pages 56–68, October 2002.

E. H. L. Aarts and J. Korst. Simulated Annealing and Boltzmann Machines. John Wiley & Sons, Essex, U.K., 1989.

De Vicente, Juan; Lanchares, Juan; Hermida, Román (2003). "Placement by thermodynamic simulated annealing". Physics Letters A 317 (5–6): 415–423.

HMMER 3.1 (February 2013);

Hjelmqvist, Sten (March 2012), Fast, memory efficient Levenshtein algorithm (


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.