Classification of n Variable Boolean Functions through Hamming Distance and their Application in System Biology
Jayanta Kumar Das and Pabitra Pal Choudhury. Article: Classification of n Variable Boolean Functions through Hamming Distance and their Application in System Biology. IJCA Proceedings on National Conference cum Workshop on Bioinformatics and Computational Biology NCWBCB(1):11-14, May 2014. Full text available. BibTeX
@article{key:article,
author = {Jayanta Kumar Das and Pabitra Pal Choudhury},
title = {Article: Classification of n Variable Boolean Functions through Hamming Distance and their Application in System Biology},
journal = {IJCA Proceedings on National Conference cum Workshop on Bioinformatics and Computational Biology},
year = {2014},
volume = {NCWBCB},
number = {1},
pages = {11-14},
month = {May},
note = {Full text available}
}
Abstract
In this article, a noble approach is presented to classify n-variable Boolean functions in logical way such that each function belonging to a particular class can be traced with respect to a single base function. In the present study, two different methods have been proposed for this classification. The first one is done through the Hamming distance with regards to base 0 (2^n bits of zeros) Boolean function. In the second method, the classification is done to generate all Boolean functions from n variable to n+1 variable through the concatenation methodology. The presented paper also contains two unique and different methodologies for finding the cardinality of different classes. In this classification all the basis Boolean functions were captured into a single class. All the linear and corresponding affine Boolean functions belong to a single class along with other nonlinear Boolean functions except two classes of single cardinality. It has been also observed symmetrical class distribution with equal cardinality and functions belonging to the symmetrical classes are complement of each other. Special Boolean functions like Nested Canalyzing Functions (NCFs) [1, 2, 3, 4, and 5] are considered biologically important. So they are specially viewed in our classification among different classes.
References
- L. Layne, E. Dimaitrova, M. Macauley, " Nested Canalyzing Depth and Network Stability",Bull Math Biol (2012) 74:422433 DOI 10. 1007/s11538-011-9692-y
- Camellia. Ray, Jayanta Kumar das, Pabitra Pal Choudhury, "On Analysis and Generation of some Biologically Important Boolean Functions" arXiv:submit/0952437 [cs. YS] 8 Apr 2014 .
- Abdul Salam Jarrah, Blessilda Raposa, Reinhard Laubenbacher " Nested Canalyzing Unate Cas- cade, and Polynomial functions Physica D. 2007 September 15; 233(2): 167174
- Franziska Hinkelmann, Abdul Salam Jarrah, " Inferring Biologically Relevant Models: Nested Canalyzing Functions ", International Scholarly Research Network ISRN Biomathematics Volume 2012, Article ID 613174, 7 pages doi:10. 5402/2012/613174
- David Murrugarra and Reinhard Laubenbacher, "The Number of Multistate Nested Canalyzing Functions ", Physica D: Nonlinear Phenomena Volume 241, Issue 10, 15 May 2012, Pages 929938
- L. Pauleve, A. Richard, "Stastic Analysis of Boolean Networks Based on Interaction graph: A survaey" ,Theoretical Computer scinece, 284(2012):93-104.
- Ranjeet Kumar Rout, Jayanta Kumar Das, Pabitra Pal Choudhury, "Analysis of Boolean Functions based on Interaction Graphs and their influence in System Biology" (Accepted for seminar and possible publication in your upcoming symposium "3rd International Symposium on Complex Dynamical Systems and Applications (CDSA -2014).
- R. K. Rout, P. Pal Choudhury, and S. Sahoo, "Classification of Boolean Functions Where Affine Functions Are Uniformly Distributed," Journal of Discrete Mathematics, vol. 2013, Article ID 270424, 12 pages, 2013.
- D. Slepian,"On the number of symmetry types of Boolean functions of n variables" Canadian Journal of Mathematics, vol. 5, no. 2, pp. 185–193, 1953. View at Zentralblatt MATH • View at MathSciNet.
- S. W. Golomb, "On the classification of Boolean functions," IRE Transactions on Circuit Theory, vol. 6, no. 5, pp. 176–186, 1959.
- M. A. Harrison, "On the classification of Boolean functions by the general linear and affine groups" Journal of the Society for Industrial and Applied Mathematics, vol. 12, no. 2, pp. 285–299, 1964.
- V. P. Correia and A. I. Reis, "Classifying n-input Boolean functions," in Proceedings of the 7th Workshop IBERCHIP (IWS '01), pp. 58–66, Montevideo, Uruguay, March 2001.
- S. W Golomb (1959), " On the classification of Boolean functions", IRE transactions on circuit theory, Vol. 06, Issue. 05, pp. 176- 186 .
- P. Pal Choudhury, S. Sahoo, M. Chakarborty, S. K Bhandari, A. Pal(2009), "Investigation of the Global Dynamics of Cellular Automata Using Boolean Derivatives ", Computers and Mathematics with Applications, Elsevier, 57, pp. 1337-1351 .
- P. Pal Choudhury, S. Sahoo, M. Chakraborty (2011) ,"Characterization of the evolution of Non-linear Uniform Cellular Automata in the light of Deviant States", Mathematics and Mathematical Sciences, Vol. 2011, Article ID 605098.
- S. Sahoo, P. Pal Choudhury, M. Chakraborty (2010), "Characterization of any Non-linear Boolean function Using A Set of Linear Operators", Journal of Orissa Mathematical Society, Vol. 2, No. 1&2, pp. 111-133.
- An. Braeken, Y. Borissov, S. Nikova, B. Preneel (2005), "Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties", ICALP'05 Proceedings of the 32nd international conference on Automata, Languages and Programming,Springer-Verlag Berlin, Heidelberg , pp. 324-334.