CFP last date
20 June 2024
Call for Paper
July Edition
IJCA solicits high quality original research papers for the upcoming July edition of the journal. The last date of research paper submission is 20 June 2024

Submit your paper
Know more
Reseach Article

Classification of n Variable Boolean Functions through Hamming Distance and their Application in System Biology

Published on May 2014 by Jayanta Kumar Das, Pabitra Pal Choudhury
National Conference cum Workshop on Bioinformatics and Computational Biology
Foundation of Computer Science USA
NCWBCB - Number 1
May 2014
Authors: Jayanta Kumar Das, Pabitra Pal Choudhury
200b5464-bc84-4420-9abd-244c53ab69aa

Jayanta Kumar Das, Pabitra Pal Choudhury . Classification of n Variable Boolean Functions through Hamming Distance and their Application in System Biology. National Conference cum Workshop on Bioinformatics and Computational Biology. NCWBCB, 1 (May 2014), 11-14.

@article{
author = { Jayanta Kumar Das, Pabitra Pal Choudhury },
title = { Classification of n Variable Boolean Functions through Hamming Distance and their Application in System Biology },
journal = { National Conference cum Workshop on Bioinformatics and Computational Biology },
issue_date = { May 2014 },
volume = { NCWBCB },
number = { 1 },
month = { May },
year = { 2014 },
issn = 0975-8887,
pages = { 11-14 },
numpages = 4,
url = { /proceedings/ncwbcb/number1/16505-1405/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 National Conference cum Workshop on Bioinformatics and Computational Biology
%A Jayanta Kumar Das
%A Pabitra Pal Choudhury
%T Classification of n Variable Boolean Functions through Hamming Distance and their Application in System Biology
%J National Conference cum Workshop on Bioinformatics and Computational Biology
%@ 0975-8887
%V NCWBCB
%N 1
%P 11-14
%D 2014
%I International Journal of Computer Applications
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
  1. 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
  2. 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 .
  3. Abdul Salam Jarrah, Blessilda Raposa, Reinhard Laubenbacher " Nested Canalyzing Unate Cas- cade, and Polynomial functions Physica D. 2007 September 15; 233(2): 167174
  4. 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
  5. 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
  6. L. Pauleve, A. Richard, "Stastic Analysis of Boolean Networks Based on Interaction graph: A survaey" ,Theoretical Computer scinece, 284(2012):93-104.
  7. 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).
  8. 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.
  9. 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.
  10. S. W. Golomb, "On the classification of Boolean functions," IRE Transactions on Circuit Theory, vol. 6, no. 5, pp. 176–186, 1959.
  11. 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.
  12. 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.
  13. S. W Golomb (1959), " On the classification of Boolean functions", IRE transactions on circuit theory, Vol. 06, Issue. 05, pp. 176- 186 .
  14. 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 .
  15. 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.
  16. 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.
  17. 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.
Index Terms

Computer Science
Information Sciences

Keywords

Classification Methodology Boolean Function Hamming Distance Nested Canalyzing Function Interaction Graph.