{ "cells": [ { "cell_type": "markdown", "id": "Nti1VE8-Dl_5", "metadata": { "id": "Nti1VE8-Dl_5" }, "source": [ "# BoolForge Tutorial #3: Canalization\n", "\n", "In this tutorial, we will focus on canalization, a key property of Boolean functions, specifically those that constitute biologically meaningful update rules in biological networks. \n", "You will learn how to:\n", "- determine if a Boolean function is canalizing, k-canalizing and nested canalizing,\n", "- compute the canalizing layer structure of any Boolean function, and\n", "- compute properties related to collective canalization, such as the canalizing strength or the effective degree and input redundancy." ] }, { "cell_type": "code", "execution_count": 43, "id": "d6aba3ec", "metadata": { "executionInfo": { "elapsed": 8118, "status": "ok", "timestamp": 1729274660920, "user": { "displayName": "Bernard Lidicky", "userId": "15999393152596956268" }, "user_tz": 300 }, "id": "d6aba3ec" }, "outputs": [], "source": [ "import boolforge\n", "import numpy as np\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "markdown", "id": "1d2108ff", "metadata": {}, "source": [ "## Canalizing variables and layers\n", "\n", "A Boolean function $f(x_1, \\ldots, x_n)$ is *canalizing* if there exists at least one *canalizing variable* $x_i$ and a *canalizing input value* $a \\in \\{0, 1\\}$ such that $f(x_1, \\ldots,x_i = a, \\ldots, x_n)=b$, where $b\\in\\{0,1\\}$ is a constant, the *canalized output*.\n", "\n", "A Boolean function is *k-canalizing* if it has at least k conditionally canalizing variables. This is checked recursively: after fixing a canalizing variable $x_i$ to its non-canalizing input value $\\bar a$, the subfunction $f(x_1,\\ldots,x_{i-1},x_{i+1},\\ldots,x_n)$ must itself contain another canalizing variable, and so on. For a given function, the maximal possible value of k is defined as its *canalizing depth*. If all variables are conditionally canalizing (i.e., if the canalizing depth is $n$), the function is called *nested canalizing*. Biological networks are heavily enriched for nested canalizing functions as we explore in a later tutorial.\n", "\n", "Per (He and Macauley, Physica D, 2016), any Boolean function can be decomposed into a unique standard monomial form by recursively identifying and removing all conditionally canalizing variables (this set of variables is called a *canalizing layer*). Each variable of a Boolean function appears in exactly one layer, or (if it is not conditionally canalizing) it is part of the non-canalizing core function that has to be evaluated only if all conditionally canalizing variables receive their non-canalizing input value. The *canalizing layer structure* $[k_1,\\ldots,k_r]$ describes the number of variables in each canalizing layer. We thus have $r\\geq 0$, $k_i\\geq 1$ and $k_1+\\cdots+k_r$.\n", "\n", "In the following code, we define four 3-input functions with different canalizing properties." ] }, { "cell_type": "code", "execution_count": 54, "id": "a1a56603", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x0\tx1\tx2\t|\tf\tg\th\tk\n", "---------------------------------------------------------\n", "0\t0\t0\t|\t0\t1\t0\t0\n", "0\t0\t1\t|\t1\t0\t0\t0\n", "0\t1\t0\t|\t1\t0\t0\t0\n", "0\t1\t1\t|\t0\t1\t1\t1\n", "1\t0\t0\t|\t1\t1\t0\t1\n", "1\t0\t1\t|\t0\t1\t0\t1\n", "1\t1\t0\t|\t0\t1\t0\t1\n", "1\t1\t1\t|\t1\t1\t0\t1\n" ] } ], "source": [ "# Example: a non-canalizing XOR function.\n", "f = boolforge.BooleanFunction('(x0 + x1 + x2) % 2')\n", "\n", "# Example: a 1-canalizing function\n", "g = boolforge.BooleanFunction('(x0 | (x1 & x2 | ~x1 & ~x2)) % 2')\n", "\n", "# Example: a nested canalizing (i.e., 3-canalizing) function with 3 canalizing variables in the outer layer\n", "h = boolforge.BooleanFunction('~x0 & x1 & x2')\n", "\n", "# Example: a nested canalizing (i.e., 3-canalizing) function with 1 canalizing variable in the outer layer and two in the inner layer\n", "k = boolforge.BooleanFunction('x0 | (x1 & x2)')\n", "\n", "\n", "labels = ['f','g','h','k']\n", "\n", "boolforge.display_truth_table(f,g,h,k,labels=labels)" ] }, { "cell_type": "markdown", "id": "788b1861", "metadata": {}, "source": [ "For each function, we can determine whether it is canalizing and/or nested canalizing. This is determined by the canalizing depth (the number of conditionally canalizing variables), which we can also directly compute. As a reminder, an n-input function is canalizing if its canalizing depth is non-zero and nested canalizing if its canalizing depth equals n." ] }, { "cell_type": "code", "execution_count": 32, "id": "21a919ec", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Canalizing depth of f: 0\n", "f is canalizing: False\n", "f is nested canalizing: False\n", "\n", "Canalizing depth of g: 1\n", "g is canalizing: True\n", "g is nested canalizing: False\n", "\n", "Canalizing depth of h: 3\n", "h is canalizing: True\n", "h is nested canalizing: True\n", "\n", "Canalizing depth of k: 3\n", "k is canalizing: True\n", "k is nested canalizing: True\n", "\n" ] } ], "source": [ "for func,label in zip([f,g,h,k],labels):\n", " canalizing_depth = func.get_canalizing_depth()\n", " print(f'Canalizing depth of {label}: {canalizing_depth}') \n", " \n", " CANALIZING = func.is_canalizing()\n", " print(f'{label} is canalizing: {CANALIZING}')\n", "\n", " NESTED_CANALIZING = func.is_k_canalizing(k=func.n)\n", " print(f'{label} is nested canalizing: {NESTED_CANALIZING}')\n", "\n", " \n", "\n", " print() " ] }, { "cell_type": "markdown", "id": "f1d8dda8", "metadata": {}, "source": [ "We can also compute the entire canalizing layer structure, which yields information on the canalizing input values, the canalized output values, the order of the canalizing variables, the layer structure and the core function." ] }, { "cell_type": "code", "execution_count": 33, "id": "970e5586", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Canalizing input values of f: []\n", "Canalized output values of f: []\n", "Order of canalizing variables of f: []\n", "Layer structure of f: []\n", "Number of canalizing layers of f: 0\n", "Non-canalizing core function of f: [0 1 1 0 1 0 0 1]\n", "\n", "Canalizing input values of g: [1]\n", "Canalized output values of g: [1]\n", "Order of canalizing variables of g: [0]\n", "Layer structure of g: [1]\n", "Number of canalizing layers of g: 1\n", "Non-canalizing core function of g: [1 0 0 1]\n", "\n", "Canalizing input values of h: [1 0 0]\n", "Canalized output values of h: [0 0 0]\n", "Order of canalizing variables of h: [0 1 2]\n", "Layer structure of h: [3]\n", "Number of canalizing layers of h: 1\n", "Non-canalizing core function of h: [1]\n", "\n", "Canalizing input values of k: [1 0 0]\n", "Canalized output values of k: [1 0 0]\n", "Order of canalizing variables of k: [0 1 2]\n", "Layer structure of k: [1, 2]\n", "Number of canalizing layers of k: 2\n", "Non-canalizing core function of k: [1]\n", "\n" ] } ], "source": [ "for func,label in zip([f,g,h,k],labels):\n", " canalizing_info = func.get_layer_structure()\n", " print(f'Canalizing input values of {label}: {canalizing_info['CanalizingInputs']}')\n", " print(f'Canalized output values of {label}: {canalizing_info['CanalizedOutputs']}')\n", " print(f'Order of canalizing variables of {label}: {canalizing_info['OrderOfCanalizingVariables']}')\n", " print(f'Layer structure of {label}: {canalizing_info['LayerStructure']}')\n", " print(f'Number of canalizing layers of {label}: {canalizing_info['NumberOfLayers']}')\n", " print(f'Non-canalizing core function of {label}: {canalizing_info['CoreFunction']}')\n", " print()\n", "\n" ] }, { "cell_type": "markdown", "id": "99660fd9", "metadata": {}, "source": [ "Consider, for example, the output for `h`. The canalizing input variables corresponding to the canalizing variables $x_0, x_1, x_2$ are $1,0,0$, respectively. Likewise, the corresponding canalized output values are all 0. This tells us that `h` can be evaluated as follows:\n", "$$h(x_0,x_1,x_2) = \n", "\\begin{cases}\n", "0 & \\ \\text{if}\\ x_0 = 1,\\\\\n", "0 & \\ \\text{if}\\ x_0 \\neq 1 \\ \\text{and} \\ x_1 = 0,\\\\\n", "0 & \\ \\text{if}\\ x_0 \\neq 1 \\ \\text{and} \\ x_1 \\neq 0 \\ \\text{and} \\ x_2 = 0,\\\\\n", "1 & \\ \\text{if}\\ x_0 \\neq 1 \\ \\text{and} \\ x_1 \\neq 0 \\ \\text{and} \\ x_2 \\neq 0.\\end{cases}\n", "$$\n", "Since $x_1$ and $x_2$ are both part of the second canalizing layer, `h` can equivalently be evaluated as:\n", "$$h(x_0,x_1,x_2) = \n", "\\begin{cases}\n", "0 & \\ \\text{if}\\ x_0 = 1,\\\\\n", "0 & \\ \\text{if}\\ x_0 \\neq 1 \\ \\text{and} \\ x_2 = 0,\\\\\n", "0 & \\ \\text{if}\\ x_0 \\neq 1 \\ \\text{and} \\ x_2 \\neq 0 \\ \\text{and} \\ x_1 = 0,\\\\\n", "1 & \\ \\text{if}\\ x_0 \\neq 1 \\ \\text{and} \\ x_2 \\neq 0 \\ \\text{and} \\ x_1 \\neq 0.\\end{cases}\n", "$$" ] }, { "cell_type": "markdown", "id": "2901dee5", "metadata": { "id": "2901dee5" }, "source": [ "## Collective canalization\n", "\n", "More recently, the idea of collective canalization was introduced (Reichhardt & Bassler, Journal of Physics A, 2007). Rather than defining canalization as a property of each individual variable of a Boolean function, it is considered as a property of the function itself. Extending the basic definition of canalization, a Boolean n-input function is *k-set canalizing* if there exists a set of k variables such that setting these variables to specific values forces the output of the function, irrespective of the other n - k inputs (Kadelka et al, Advances in Applied Mathematics, 2023). Naturally, \n", "- any Boolean function is n-set canalizing,\n", "- the only two Boolean functions that are not $n-1$-set canalizing are the parity / XOR functions, and\n", "- the 1-set canalizing functions are exactly the canalizing functions.\n", "\n", "For any function and a given k, we can quantify the proportion of k-sets that collectively canalize this function (i.e., suffice to determine its output). This is called the *k-set canalizing proportion* $P_k(f)$.\n", "It is fairly obvious that\n", "- nested canalizing functions of a single layer such as `h` are the non-degenerate functions with highest k-set canalizing proportion $P_k(f) = 1-1/2^k$, and\n", "- $P_{k-1}(f) \\leq P_k(f)$, i.e., more knowledge about a function's inputs cannot result in less knowledge about its output,\n", "- the $n-1$-set canalizing proportion $P_{n-1}(f)$ is 1 minus the function's normalized average sensitivity.\n", "\n", "We can compute the k-set canalizing proportions for the four 3-input functions:" ] }, { "cell_type": "code", "execution_count": 40, "id": "67a5a393", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1-set canalizing proportions of f: 0.0\n", "2-set canalizing proportions of f: 0.0\n", "Normalized average sensitivity of f: 1.0\n", "3-set canalizing proportions of f: 1.0\n", "\n", "1-set canalizing proportions of g: 0.16666666666666666\n", "2-set canalizing proportions of g: 0.5\n", "Normalized average sensitivity of g: 0.5\n", "3-set canalizing proportions of g: 1.0\n", "\n", "1-set canalizing proportions of h: 0.5\n", "2-set canalizing proportions of h: 0.75\n", "Normalized average sensitivity of h: 0.25\n", "3-set canalizing proportions of h: 1.0\n", "\n", "1-set canalizing proportions of k: 0.16666666666666666\n", "2-set canalizing proportions of k: 0.5833333333333334\n", "Normalized average sensitivity of k: 0.4166666666666667\n", "3-set canalizing proportions of k: 1.0\n", "\n" ] } ], "source": [ "for func,label in zip([f,g,h,k],labels):\n", " print(f'1-set canalizing proportions of {label}: {func.get_kset_canalizing_proportion(k=1)}')\n", " print(f'2-set canalizing proportions of {label}: {func.get_kset_canalizing_proportion(k=2)}')\n", " print(f'Normalized average sensitivity of {label}: {func.get_average_sensitivity(EXACT=True)}')\n", " print(f'3-set canalizing proportions of {label}: {func.get_kset_canalizing_proportion(k=3)}')\n", " print()\n" ] }, { "cell_type": "markdown", "id": "e978926c", "metadata": {}, "source": [ "The *canalizing strength* is a measure to quantify the degree of canalization of any Boolean function (Kadelka et al, Advances in Applied Mathematics, 2023). It is computed as a weighted average of the k-set canalizing proportions. It is 1 for the most canalizing non-degenerate functions (namely, nested canalizing functions of a single canalizing layer such as `h`) and 0 for the least canalizing functions (namely, parity / XOR functions such as `f`). For all other non-degenerate Boolean functions it is within $(0,1)$.\n", "\n", "It helps to consider the canalizing strength as a probability: Given that I know a random number of function inputs (drawn uniformly at random from $1,\\ldots,n-1$), how likely am I to already know the function output?" ] }, { "cell_type": "code", "execution_count": 41, "id": "8275851d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Canalizing strength of f: 0.0\n", "\n", "Canalizing strength of g: 0.5\n", "\n", "Canalizing strength of h: 1.0\n", "\n", "Canalizing strength of k: 0.5555555555555556\n", "\n" ] } ], "source": [ "for func,label in zip([f,g,h,k],labels):\n", " canalizing_strength = func.get_canalizing_strength()\n", " print(f'Canalizing strength of {label}: {canalizing_strength}')\n", " print()" ] }, { "cell_type": "markdown", "id": "628dc116", "metadata": {}, "source": [ "An enumeration of all non-degenerate 3-input Boolean functions reveals the distribution of the canalizing strength. Note that this brute-force code can also run (in less than a minute) for all $2^{2^4}=2^{16}=65,536$ 4-input functions but will take days for all $2^{2^5}=2^{32}=4,294,967,296$ 5-input functions." ] }, { "cell_type": "code", "execution_count": 52, "id": "6b9df367", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Text(0, 0.5, 'Count')" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjIAAAGzCAYAAAA1yP25AAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjUsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvWftoOwAAAAlwSFlzAAAPYQAAD2EBqD+naQAAJO5JREFUeJzt3QmUFdWdP/DL0oAbIC6ACoILiDpoxIi4ZBTRjhojgzPRxHHQgxoTIAqJC6OIOnHgGAPGDGjcIDNHh0hGHBWDUQiuGBUkcSWiGIgIGE2zmLAI73/undP9p7FZ7e73bvP5nFOhX1W96l9fsN83d6lqVCgUCgEAIEONi10AAMD2EmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGw1LeY3v+GGG8KNN95YbV/Xrl3D22+/nb5etWpV+P73vx8mTpwYVq9eHcrLy8O4ceNC27Ztt/p7rF+/PixatCjstttuoVGjRrX+MwAAtS8+QWnFihVhn332CY0bNy7NIBMddthh4amnnqp63bTp/y9pyJAhYcqUKWHSpEmhVatWYdCgQaFfv37h+eef3+rrxxDToUOHWq8bAKh7CxcuDPvtt1/pBpkYXNq1a/e5/cuWLQv33ntveOCBB0Lv3r3TvvHjx4du3bqFF198MRx77LFbdf3YE1PZEC1btqzl6gGAurB8+fLUEVH5OV6yQeadd95J3UYtWrQIvXr1CiNHjgwdO3YMs2bNCmvXrg19+vSpOveQQw5Jx2bOnLnJIBOHoOJWKXZLRTHECDIAkJctTQsp6mTfnj17hgkTJoSpU6eGO+64I8yfPz+ceOKJKXwsXrw4NGvWLLRu3brae+L8mHhsU2IQisNQlZthJQBouIraI3P66adXfd29e/cUbPbff//w4IMPhp122mm7rjls2LAwdOjQz3VNAQANT0ktv469L126dAnz5s1L82bWrFkTKioqqp2zZMmSGufUVGrevHnVMJLhJABo2EoqyKxcuTK8++67oX379qFHjx6hrKwsTJs2rer43Llzw4IFC9JcGgCAog4t/eAHPwhnnXVWGk6Ky6RHjBgRmjRpEr75zW+m+S0DBgxIw0Rt2rRJPSuDBw9OIWZrVywBAA1bUYPMn/70pxRaPv7447DXXnuFE044IS2tjl9HY8aMSTfBOeecc6rdEA8AIGpUiLfOa8DiZN/YuxPvS2O+DAA0rM/vkpojAwCwLQQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwV9c6+UIo6XTNli+e8P+rMeqmF+uPvHfKkRwYAyJYgAwBkS5ABALIlyAAA2RJkAIBsCTIAQLYEGQAgW4IMAJAtQQYAyJYgAwBkS5ABALIlyAAA2RJkAIBsCTIAQLYEGQAgW4IMAJAtQQYAyJYgAwBkS5ABALIlyAAA2RJkAIBsCTIAQLYEGQAgW4IMAJAtQQYAyJYgAwBkS5ABALIlyAAA2RJkAIBsCTIAQLYEGQAgW4IMAJAtQQYAyJYgAwBkS5ABALIlyAAA2RJkAIBsCTIAQLYEGQAgW4IMAJAtQQYAyJYgAwBkS5ABALIlyAAA2RJkAIBsCTIAQLYEGQAgW4IMAJAtQQYAyJYgAwBkS5ABALIlyAAA2RJkAIBslUyQGTVqVGjUqFG44oorqvatWrUqDBw4MOyxxx5h1113Deecc05YsmRJUesEAEpHSQSZl19+OfzsZz8L3bt3r7Z/yJAh4dFHHw2TJk0KTz/9dFi0aFHo169f0eoEAEpL0YPMypUrw/nnnx/uvvvusPvuu1ftX7ZsWbj33nvD6NGjQ+/evUOPHj3C+PHjwwsvvBBefPHFotYMAJSGogeZOHR05plnhj59+lTbP2vWrLB27dpq+w855JDQsWPHMHPmzE1eb/Xq1WH58uXVNgCgYWpazG8+ceLEMHv27DS0tLHFixeHZs2ahdatW1fb37Zt23RsU0aOHBluvPHGOqkXaluna6Zs8Zz3R51ZL7UA5KhoPTILFy4Ml19+ebj//vtDixYtau26w4YNS8NSlVv8PgBAw1S0IBOHjpYuXRqOOuqo0LRp07TFCb233357+jr2vKxZsyZUVFRUe19ctdSuXbtNXrd58+ahZcuW1TYAoGEq2tDSKaecEl577bVq+y666KI0D+bqq68OHTp0CGVlZWHatGlp2XU0d+7csGDBgtCrV68iVQ0AlJKiBZnddtstHH744dX27bLLLumeMZX7BwwYEIYOHRratGmTelYGDx6cQsyxxx5bpKoBgFJS1Mm+WzJmzJjQuHHj1CMTVyOVl5eHcePGFbssAKBElFSQmTFjRrXXcRLw2LFj0wYAUHL3kQEA2F6CDACQLUEGAMiWIAMAZEuQAQCyJcgAANkSZACAbAkyAEC2BBkAIFuCDACQLUEGAMiWIAMAZEuQAQCyJcgAANkSZACAbAkyAEC2BBkAIFuCDACQLUEGAMiWIAMAZEuQAQCyJcgAANkSZACAbAkyAEC2BBkAIFuCDACQLUEGAMiWIAMAZEuQAQCyJcgAANkSZACAbAkyAEC2BBkAIFuCDACQLUEGAMiWIAMAZEuQAQCyJcgAANkSZACAbAkyAEC2BBkAIFuCDACQLUEGAMiWIAMAZEuQAQCyJcgAANkSZACAbAkyAEC2BBkAIFuCDACQLUEGAMiWIAMAZEuQAQCyJcgAANkSZACAbAkyAEC2BBkAIFuCDACQLUEGAMiWIAMAZEuQAQCyJcgAANkSZACAbBU1yNxxxx2he/fuoWXLlmnr1atX+NWvflV1fNWqVWHgwIFhjz32CLvuums455xzwpIlS4pZMgBQQooaZPbbb78watSoMGvWrPDKK6+E3r17h7PPPju88cYb6fiQIUPCo48+GiZNmhSefvrpsGjRotCvX79ilgwAlJCmxfzmZ511VrXXN998c+qlefHFF1PIuffee8MDDzyQAk40fvz40K1bt3T82GOPLVLVAECpKJk5MuvWrQsTJ04Mn376aRpiir00a9euDX369Kk655BDDgkdO3YMM2fO3OR1Vq9eHZYvX15tAwAapqIHmddeey3Nf2nevHm47LLLwuTJk8Ohhx4aFi9eHJo1axZat25d7fy2bdumY5sycuTI0KpVq6qtQ4cO9fBTAAA7ZJDp2rVrmDNnTvjtb38bvvOd74T+/fuHN998c7uvN2zYsLBs2bKqbeHChbVaLwBQOoo6RyaKvS4HHXRQ+rpHjx7h5ZdfDj/5yU/CueeeG9asWRMqKiqq9crEVUvt2rXb5PViz07cAICGr+g9Mhtbv359mucSQ01ZWVmYNm1a1bG5c+eGBQsWpDk0AABF7ZGJw0Cnn356msC7YsWKtEJpxowZ4YknnkjzWwYMGBCGDh0a2rRpk+4zM3jw4BRirFgCAIoeZJYuXRr+5V/+JXz44YcpuMSb48UQc+qpp6bjY8aMCY0bN043wou9NOXl5WHcuHH+5gCA4geZeJ+YzWnRokUYO3Zs2gAASn6ODADA1hJkAIBsCTIAQLYEGQAgW4IMAJAtQQYAyJYgAwBkS5ABALIlyAAA2RJkAIAdK8gccMAB4eOPP/7c/oqKinQMAKBkg8z7778f1q1b97n98cGOH3zwQW3UBQBQuw+NfOSRR6q+jk+pjk+srhSDzbRp00KnTp225ZIAAPUTZPr27Zv+bNSoUejfv3+1Y2VlZSnE/PjHP97+agAA6irIrF+/Pv3ZuXPn8PLLL4c999xzW94OAFC8IFNp/vz5tVsFAEB9BZkozoeJ29KlS6t6airdd99923tZAIC6DTI33nhjuOmmm8LRRx8d2rdvn+bMAABkEWTuvPPOMGHChHDBBRfUfkUAAHV5H5k1a9aE4447bnveCgBQ3CBz8cUXhwceeKD2qgAAqK+hpVWrVoW77rorPPXUU6F79+7pHjIbGj169PZcFgCg7oPM73//+3DkkUemr19//fVqx0z8BQBKOsj85je/qf1KAADqY44MAEC2PTInn3zyZoeQpk+f/kVqAgCouyBTOT+m0tq1a8OcOXPSfJmNHyYJAFBSQWbMmDE17r/hhhvCypUrv2hNAAD1P0fmn//5nz1nCQDIM8jMnDkztGjRojYvCQBQu0NL/fr1q/a6UCiEDz/8MLzyyith+PDh23NJAID6CTKtWrWq9rpx48aha9eu6YnYp5122vZcEgCgfoLM+PHjt+dtAADFDzKVZs2aFd5666309WGHHRa+9KUv1VZdAAB1E2SWLl0azjvvvDBjxozQunXrtK+ioiLdKG/ixIlhr7322p7LAgDU/aqlwYMHhxUrVoQ33ngjfPLJJ2mLN8Nbvnx5+N73vrc9lwQAqJ8emalTp4annnoqdOvWrWrfoYceGsaOHWuyLwBQ2kFm/fr1oays7HP74754DIqh0zVTtnjO+6POrJdaqD/+3mHHtl1DS7179w6XX355WLRoUdW+Dz74IAwZMiSccsoptVkfAEDtBpn/+I//SPNhOnXqFA488MC0de7cOe376U9/uj2XBACon6GlDh06hNmzZ6d5Mm+//XbaF+fL9OnTZ3suBwBQ9z0y06dPT5N6Y89Lo0aNwqmnnppWMMXty1/+crqXzLPPPrt9lQAA1GWQue2228Ill1wSWrZsWeNjC7797W+H0aNHb2sNAAB1H2R+97vfha9+9aubPB6XXse7/QIAlFyQWbJkSY3Lris1bdo0fPTRR7VRFwBA7QaZfffdN93Bd1N+//vfh/bt22/LJQEA6ifInHHGGWH48OFh1apVnzv2t7/9LYwYMSJ87Wtf2/5qAADqavn1ddddFx566KHQpUuXMGjQoNC1a9e0Py7Bjo8nWLduXbj22mu35ZIAAPUTZNq2bRteeOGF8J3vfCcMGzYsFAqFtD8uxS4vL09hJp4DAFCSN8Tbf//9w+OPPx7+8pe/hHnz5qUwc/DBB4fdd9+9bioEAKjNO/tGMbjEm+ABAGT1rCUAgFIgyAAA2RJkAIBsCTIAQLYEGQAgW4IMAJAtQQYAyJYgAwBkS5ABALIlyAAA2RJkAIBsFTXIjBw5Mj2vabfddgt777136Nu3b5g7d261c1atWhUGDhwY9thjj7DrrruGc845JyxZsqRoNQMApaOoQebpp59OIeXFF18MTz75ZFi7dm047bTTwqefflp1zpAhQ8Kjjz4aJk2alM5ftGhR6NevXzHLBgByf/p1bZg6dWq11xMmTEg9M7NmzQpf+cpXwrJly8K9994bHnjggdC7d+90zvjx40O3bt1S+Dn22GOLVDkAUApKao5MDC5RmzZt0p8x0MRemj59+lSdc8ghh4SOHTuGmTNn1niN1atXh+XLl1fbAICGqWSCzPr168MVV1wRjj/++HD44YenfYsXLw7NmjULrVu3rnZu27Zt07FNzbtp1apV1dahQ4d6qR8A2IGDTJwr8/rrr4eJEyd+oesMGzYs9exUbgsXLqy1GgGA0lLUOTKVBg0aFB577LHwzDPPhP32269qf7t27cKaNWtCRUVFtV6ZuGopHqtJ8+bN0wYANHxF7ZEpFAopxEyePDlMnz49dO7cudrxHj16hLKysjBt2rSqfXF59oIFC0KvXr2KUDEAUEqaFns4Ka5I+t///d90L5nKeS9xbstOO+2U/hwwYEAYOnRomgDcsmXLMHjw4BRirFgCAIoaZO64447050knnVRtf1xifeGFF6avx4wZExo3bpxuhBdXJJWXl4dx48YVpV4AoLQ0LfbQ0pa0aNEijB07Nm0AACW5agkAYFsJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGSrabELoGHrdM2ULZ7z/qgz66UWABre73A9MgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZKmqQeeaZZ8JZZ50V9tlnn9CoUaPw8MMPVzteKBTC9ddfH9q3bx922mmn0KdPn/DOO+8UrV4AoLQUNch8+umn4Ygjjghjx46t8fgtt9wSbr/99nDnnXeG3/72t2GXXXYJ5eXlYdWqVfVeKwBQepoW85uffvrpaatJ7I257bbbwnXXXRfOPvvstO8///M/Q9u2bVPPzXnnnVfP1QIApaZk58jMnz8/LF68OA0nVWrVqlXo2bNnmDlz5ibft3r16rB8+fJqGwDQMJVskIkhJoo9MBuKryuP1WTkyJEp8FRuHTp0qPNaAYDiKNkgs72GDRsWli1bVrUtXLiw2CUBADtakGnXrl36c8mSJdX2x9eVx2rSvHnz0LJly2obANAwlWyQ6dy5cwos06ZNq9oX57vE1Uu9evUqam0AQGko6qqllStXhnnz5lWb4DtnzpzQpk2b0LFjx3DFFVeEH/7wh+Hggw9OwWb48OHpnjN9+/YtZtkAQIkoapB55ZVXwsknn1z1eujQoenP/v37hwkTJoSrrroq3Wvm0ksvDRUVFeGEE04IU6dODS1atChi1QBAqShqkDnppJPS/WI2Jd7t96abbkobAEA2c2QAALZEkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZEmQAgGw1LXYBOet0zZQtnvP+qDPrpRYA2BHpkQEAsiXIAADZEmQAgGwJMgBAtgQZACBbggwAkC1BBgDIliADAGRLkAEAsiXIAADZyiLIjB07NnTq1Cm0aNEi9OzZM7z00kvFLgkAKAElH2R+8YtfhKFDh4YRI0aE2bNnhyOOOCKUl5eHpUuXFrs0AKDISj7IjB49OlxyySXhoosuCoceemi48847w8477xzuu+++YpcGABRZST/9es2aNWHWrFlh2LBhVfsaN24c+vTpE2bOnFnje1avXp22SsuWLUt/Ll++vNbrW7/6r1s8py6+b07qs41q63vlWPOOLMe/d8jF+iL+d1F53UKhsPkTCyXsgw8+iNUXXnjhhWr7r7zyysIxxxxT43tGjBiR3mOz2Ww2my1kvy1cuHCzWaGke2S2R+y9iXNqKq1fvz588sknYY899giNGjWq1aTYoUOHsHDhwtCyZctauy6fp63rh3auH9q5fmjn/Ns59sSsWLEi7LPPPps9r6SDzJ577hmaNGkSlixZUm1/fN2uXbsa39O8efO0bah169Z1VmP8i/MfSf3Q1vVDO9cP7Vw/tHPe7dyqVau8J/s2a9Ys9OjRI0ybNq1aD0t83atXr6LWBgAUX0n3yERxmKh///7h6KOPDsccc0y47bbbwqeffppWMQEAO7aSDzLnnntu+Oijj8L1118fFi9eHI488sgwderU0LZt26LWFYev4r1tNh7GovZp6/qhneuHdq4f2nnHaedGccZv0b47AMAXUNJzZAAANkeQAQCyJcgAANkSZACAbAkymzF27NjQqVOn0KJFi9CzZ8/w0ksvbfb8SZMmhUMOOSSd/3d/93fh8ccfr7dac7ctbX333XeHE088Mey+++5pi8/e2tLfDdv3b7rSxIkT052x+/btW+c17ojtXFFREQYOHBjat2+fVn906dLF7486aOd4+46uXbuGnXbaKd2NdsiQIWHVqlX1Vm+OnnnmmXDWWWelu+vG3wEPP/zwFt8zY8aMcNRRR6V/ywcddFCYMGFC3RZZm89GakgmTpxYaNasWeG+++4rvPHGG4VLLrmk0Lp168KSJUtqPP/5558vNGnSpHDLLbcU3nzzzcJ1111XKCsrK7z22mv1XntDb+tvfetbhbFjxxZeffXVwltvvVW48MILC61atSr86U9/qvfaG3I7V5o/f35h3333LZx44omFs88+u97q3VHaefXq1YWjjz66cMYZZxSee+651N4zZswozJkzp95rb8jtfP/99xeaN2+e/oxt/MQTTxTat29fGDJkSL3XnpPHH3+8cO211xYeeuih9NyjyZMnb/b89957r7DzzjsXhg4dmj4Lf/rTn6bPxqlTp9ZZjYLMJsSHUg4cOLDq9bp16wr77LNPYeTIkTWe/41vfKNw5plnVtvXs2fPwre//e06r3VHa+uNffbZZ4Xddtut8POf/7wOq9wx2zm27XHHHVe45557Cv379xdk6qCd77jjjsIBBxxQWLNmTT1WueO1czy3d+/e1fbFD9vjjz++zmttKMJWBJmrrrqqcNhhh1Xbd+655xbKy8vrrC5DSzVYs2ZNmDVrVhqyqNS4ceP0eubMmTW+J+7f8PyovLx8k+ez/W29sb/+9a9h7dq1oU2bNnVY6Y7ZzjfddFPYe++9w4ABA+qp0h2vnR955JH0yJU4tBRv9Hn44YeHf//3fw/r1q2rx8obfjsfd9xx6T2Vw0/vvfdeGr4744wz6q3uHcHMInwWlvydfYvhz3/+c/olsvHdg+Prt99+u8b3xLsO13R+3E/ttvXGrr766jR+u/F/PHyxdn7uuefCvffeG+bMmVNPVe6Y7Rw/UKdPnx7OP//89ME6b9688N3vfjeF83jHVGqnnb/1rW+l951wwgnpqcqfffZZuOyyy8K//uu/1lPVO4bFm/gsjE/J/tvf/pbmJ9U2PTJkbdSoUWki6uTJk9OEP2rHihUrwgUXXJAmVsen0FN34oNwY6/XXXfdlR6SGx/Lcu2114Y777yz2KU1KHECauzpGjduXJg9e3Z46KGHwpQpU8K//du/Fbs0viA9MjWIv7ibNGkSlixZUm1/fN2uXbsa3xP3b8v5bH9bV7r11ltTkHnqqadC9+7d67jSHaud33333fD++++n1QobfuBGTZs2DXPnzg0HHnhgPVTe8P89x5VKZWVl6X2VunXrlv6fbRxCadasWZ3XvSO08/Dhw1M4v/jii9PruLI0PoD40ksvTcExDk3xxW3qs7Bly5Z10hsT+ZurQfzFEf+f0bRp06r9Eo+v41h2TeL+Dc+PnnzyyU2ez/a3dXTLLbek/ycVHyAan4xO7bZzvI3Aa6+9loaVKrevf/3r4eSTT05fx6Wr1M6/5+OPPz4NJ1UGxegPf/hDCjhCTO21c5xLt3FYqQyPHjlYe4ryWVhn04gbwNK+uFRvwoQJaQnZpZdempb2LV68OB2/4IILCtdcc0215ddNmzYt3HrrrWlJ8IgRIyy/rqO2HjVqVFp2+ctf/rLw4YcfVm0rVqwo4k/R8Np5Y1Yt1U07L1iwIK26GzRoUGHu3LmFxx57rLD33nsXfvjDHxbxp2h47Rx/J8d2/u///u+0RPjXv/514cADD0wrTtm0+Hs13uoibjEyjB49On39xz/+MR2PbRzbeuPl11deeWX6LIy3yrD8uoji+veOHTumD8241O/FF1+sOvb3f//36Rf7hh588MFCly5d0vlx+dmUKVOKUHXDb+v9998//Qe18RZ/UVG7/6Y3JMjUXTu/8MIL6XYN8YM5LsW++eab09J3aq+d165dW7jhhhtSeGnRokWhQ4cOhe9+97uFv/zlL0WqPg+/+c1vavx9W9m28c/Y1hu/58gjj0x/L/Hf8/jx4+u0xkbxf+quvwcAoO6YIwMAZEuQAQCyJcgAANkSZACAbAkyAEC2BBkAIFuCDACQLUEG2G7xeUyNGjWqekJ2fDBffF1RUbFV74/nPvzww3VcZcMwYcKE0Lp162KXASVHkAFqzXHHHRc+/PDD0KpVq606P557+umnh2IqxTDVqVOncNtttxW7DMiCp18Dtfowv2154nsuT4f3FGooXXpkIFPxab/xKeAHHXRQaN68eejYsWO4+eabq45fffXVoUuXLmHnnXcOBxxwQBg+fHhYu3Zt1fEbbrghHHnkkeG//uu/Ug9A7EU577zzwooVK6rOiU8XP+GEE9KQxh577BG+9rWvhXfffXeTNW08tHTSSSel1xtvcUhq496QymGqhx56KD1lO9Z9xBFHhJkzZ1b7HnfffXd6+nY8/g//8A9h9OjRmx1yiSFk0KBB6WnSLVq0CPvvv38YOXJkOhZ/7iheJ37vyteVbXPPPfeEzp07p/dF8ee6+OKLw1577RVatmwZevfuHX73u99tU5vGr88///ywyy67pJrGjBmT2umKK66oarM//vGPYciQIVXttaEnnngidOvWLey6667hq1/9aurVgh2ZIAOZGjZsWBg1alQKKG+++WZ44IEHQtu2bauO77bbbmleRTz2k5/8JAWA+KG5oRhKYpB47LHH0vb000+na1b69NNPw9ChQ8Mrr7wSpk2bFho3bpw+9GOI2hoxlMQP2sqtX79+oWvXrtXq3Ni1114bfvCDH6R5NzGIffOb3wyfffZZOvb888+Hyy67LFx++eXp+KmnnlotvNXk9ttvD4888kh48MEHw9y5c8P9999fFVhefvnl9Of48eNTfZWvo3nz5oX/+Z//ST9D5Rygf/qnfwpLly4Nv/rVr8KsWbPCUUcdFU455ZTwySefbHWbxvaMP0es6cknnwzPPvtsmD17drU222+//cJNN91U1W6V/vrXv4Zbb701BaVnnnkmLFiwILUV7NDq9JGUQJ1Yvnx5elLy3XffvdXv+dGPflTo0aNH1ev4tPCdd945XavSlVdemZ7CvCkfffRRevLta6+9ll7Pnz8/vX711VerPSm3picKjx49utC6devC3Llzq/bFcydPnlztWvfcc0/V8TfeeCPte+utt9Lrc889t3DmmWdWu+75559faNWq1SZrHjx4cKF3796F9evX13h8wxo2bJuysrLC0qVLq/Y9++yzhZYtWxZWrVpV7dz4NOWf/exnW9WmcX+87qRJk6qOV1RUpPdcfvnl1Z7wPmbMmGrfJz5BONY6b968qn1jx44ttG3bdpM/O+wI9MhAht56662wevXq1BuwKb/4xS/C8ccfn+ahxGGI6667Lv0/+A3FnonYc1MpDnXEHodK77zzTuoRiUNTcSilsidj4+tsSezBuOaaa1JNsZdlc7p3716tnqiyptijcswxx1Q7f+PXG7vwwgtTj0rsCfre974Xfv3rX29VzXEIKg4hVYpDSCtXrkxDbLE9K7f58+dXG27bXJu+9957aXhvw5rj8FOsbWvE4bQDDzywxmvDjspkX8jQTjvttNnjcV5JnIdx4403hvLy8vRhOXHixPDjH/+42nllZWXVXsf5GBsOG5111lnpAz0OS+2zzz7p2OGHH57mnWytOLQV54nE4ZXTTjtti+dvWFPl/JCtHcqqSRz+iWEjhqmnnnoqfOMb3wh9+vQJv/zlLzf7vjiHZUMxxMTgEOcBbWzDOTpbatMvoqZr/1+nEuy4BBnI0MEHH5zCTJy3EiefbuyFF15IASTON6kUJ5Bui48//jj1gMQQc+KJJ6Z9zz333DZd489//nMKQ+ecc06avPpFxZ6LDeexRBu/rknsTTr33HPT9o//+I9pkmyc19KmTZsUDtatW7dVgWjx4sWhadOmVT1T2yr2bMXvF2uOk7OjZcuWhT/84Q/hK1/5StV5cYXU1tQECDKQpbiKJq5Kuuqqq9KHXhxC+uijj8Ibb7wRBgwYkIJOHP6JvTBf/vKXw5QpU8LkyZO36XvsvvvuaRjlrrvuSj0R8XpxeGhbxAATh0Piap4YAirFIZsmTZqEbTV48OD0gR9XKsWANH369NTTsvHKng3Fc2P9X/rSl9Jk5UmTJqXhtspelBhKYiCMbRhXf8WfuyaxF6dXr16hb9++abVYHCJbtGhRats4Afroo4/eYv1xyKl///7hyiuvTCFq7733DiNGjEh1bfgzxJriZN7YkxVr2nPPPbe5rWBHYY4MZCquVvr+978frr/++rQcN/Y2VM6X+PrXv556QOKy47gcOPbQxPO3RfxwjUEors6Jw0nxej/60Y+26Rrxw/j1119PvUMxTFRuCxcuDNsjho0777wzhZO4NDsuD491VS6P3lR4iMEjBo0Y6uIy78cffzz9fFEcbourh+KS7hh2NiUGjfi+GKQuuuiiFGRi0Ig9XZtbhbWxWHsMRHEpewxH8WeKf38b/gxxxVKsM86H2XCeDvB5jeKM3xr2A2ThkksuCW+//XZaxpyjuMR93333TYEq9qYB28bQEpCVeB+VeP+YOBk3Div9/Oc/D+PGjQu5ePXVV1PwiiuX4vyY2PsSnX322cUuDbIkyABZeemll9JQUbxDbpw8G294V9OE51IPY3EidZzf1KNHj9SbZB4MbB9DSwBAtkz2BQCyJcgAANkSZACAbAkyAEC2BBkAIFuCDACQLUEGAMiWIAMAZEuQAQBCrv4f28M/HCM4HGwAAAAASUVORK5CYII=", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "n = 3\n", "all_functions = boolforge.get_left_side_of_truth_table(2**n)\n", "\n", "canalizing_strengths = []\n", "for binary_vector in all_functions:\n", " func = boolforge.BooleanFunction(f = binary_vector)\n", " if func.is_degenerate() == False:\n", " canalizing_strength = func.get_canalizing_strength()\n", " canalizing_strengths.append(canalizing_strength)\n", "\n", "fig,ax = plt.subplots()\n", "ax.hist(canalizing_strengths,bins=50)\n", "ax.set_xlabel('canalizing strength')\n", "ax.set_ylabel('Count')" ] }, { "cell_type": "markdown", "id": "83ed6112", "metadata": {}, "source": [ "## Canalization as a measure of input redundancy\n", "\n", "Canalization, symmetry and redundancy are related concepts. A highly symmetry Boolean function with few (e.g., one) symmetry group exhibits high input redundancy and is on average more canalizing, irrespective of the measure of canalization. Recently, it was shown that almost all Boolean functions (except the parity / XOR functions) exhibit some level of *input redundancy* (Gates et al., PNAS, 2021). The input redundancy of a variable is defined as 1 minus its *edge effectiveness*, which describes the proportion of times that this variable is needed to determine the output of the function. Edge effectiveness is very similar to the activity of a variable but is not the same (the difference is defined as *excess canalization*). The sum of all edge effectivenesses of the inputs of a function is known as its *effective degree*. The average input redundancy serves as a measure of the canalization in a function.\n", "\n", "In `BoolForge`, all these quantities can be computed, however not directly. Instead, they are computed from the `CANA` package, which uses simulation and needs to be installed (`pip install cana`) to enjoy this functionality. To exemplify this, we reconsider the four 3-input functions from above." ] }, { "cell_type": "code", "execution_count": 61, "id": "c1c6c988", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Edge effectiveness of the variables of f: [1.0, 1.0, 1.0]\n", "Activities of the variables of f: [1. 1. 1.]\n", "Excess canalization of the variables of f: [0. 0. 0.]\n", "Effective degree of f: 3.0\n", "Average edge effectiveness of f: 1.0\n", "Normalized input redundancy of f: 0.0\n", "\n", "Edge effectiveness of the variables of g: [0.625, 0.625, 0.625]\n", "Activities of the variables of g: [0.4974 0.5036 0.5036]\n", "Excess canalization of the variables of g: [0.1276 0.1214 0.1214]\n", "Effective degree of g: 1.875\n", "Average edge effectiveness of g: 0.625\n", "Normalized input redundancy of g: 0.375\n", "\n", "Edge effectiveness of the variables of h: [0.41666666666666663, 0.41666666666666663, 0.41666666666666663]\n", "Activities of the variables of h: [0.2502 0.2502 0.2511]\n", "Excess canalization of the variables of h: [0.16646667 0.16646667 0.16556667]\n", "Effective degree of h: 1.25\n", "Average edge effectiveness of h: 0.4166666666666667\n", "Normalized input redundancy of h: 0.5833333333333334\n", "\n", "Edge effectiveness of the variables of k: [0.8125, 0.375, 0.375]\n", "Activities of the variables of k: [0.7525 0.2445 0.2441]\n", "Excess canalization of the variables of k: [0.06 0.1305 0.1309]\n", "Effective degree of k: 1.5625\n", "Average edge effectiveness of k: 0.5208333333333334\n", "Normalized input redundancy of k: 0.4791666666666667\n", "\n" ] } ], "source": [ "for func,label in zip([f,g,h,k],labels):\n", " edge_effectiveness = func.get_edge_effectiveness()\n", " activities = func.get_activities()\n", " effective_degree = func.get_effective_degree()\n", " input_redundancy = func.get_input_redundancy()\n", " print(f'Edge effectiveness of the variables of {label}: {edge_effectiveness}')\n", " print(f'Activities of the variables of {label}: {activities}')\n", " print(f'Excess canalization of the variables of {label}: {edge_effectiveness - activities}')\n", " print(f'Effective degree of {label}: {effective_degree}')\n", " print(f'Average edge effectiveness of {label}: {effective_degree/n}')\n", " print(f'Normalized input redundancy of {label}: {input_redundancy}')\n", " print()" ] } ], "metadata": { "colab": { "provenance": [ { "file_id": "1uYGafWSuMhd9QxcQkz2tTMTeFsLb_VHA", "timestamp": 1696210918065 } ] }, "kernelspec": { "display_name": "envpy312", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.3" } }, "nbformat": 4, "nbformat_minor": 5 }