boofun.analysis.canalization

Canalization Analysis for Boolean Functions.

Canalization is a concept from systems biology where certain input values “dominate” and determine the output regardless of other inputs.

A Boolean function f is canalizing if there exists: - A variable x_i - A canalizing input a ∈ {0, 1} - A canalized output b ∈ {0, 1}

Such that: f(x_1, …, x_i=a, …, x_n) = b for all other inputs.

References: - Kauffman, S.A. (1969). Metabolic stability and epigenesis in randomly

constructed genetic nets. Journal of Theoretical Biology.

Kadelka, C. et al. (2023). Collectively canalizing Boolean functions. Advances in Applied Mathematics.

Functions

`edge_effectiveness`(f)	Compute edge effectiveness for each variable.
`effective_degree`(f)	Compute effective degree: sum of edge effectiveness.
`get_canalizing_depth`(f)	Compute the canalizing depth of a Boolean function.
`get_canalizing_variables`(f)	Find all canalizing variables and their canalizing inputs/outputs.
`get_essential_variables`(f)	Find all essential (non-degenerate) variables.
`get_input_types`(f)	Classify each input variable by its type.
`get_symmetry_groups`(f)	Find groups of symmetric (interchangeable) variables.
`input_redundancy`(f)	Compute input redundancy: fraction of inputs that are redundant.
`is_canalizing`(f)	Determine if a Boolean function is canalizing.
`is_k_canalizing`(f, k)	Determine if a Boolean function is k-canalizing.
`is_nested_canalizing`(f)	Determine if a Boolean function is nested canalizing (NCF).

Classes

CanalizationAnalyzer(f)

High-level analyzer for canalization properties.

boofun.analysis.canalization.is_canalizing(f: BooleanFunction) → bool[source]

Determine if a Boolean function is canalizing.

A function is canalizing if there exists at least one variable x_i and a value a ∈ {0,1} such that fixing x_i = a forces the output to a constant value, regardless of other inputs.

Parameters:: f – Boolean function to test
Returns:: True if function is canalizing, False otherwise

Example

>>> import boofun as bf
>>> bf.AND(3).is_canalizing()  # AND canalizes on 0
True
>>> bf.parity(3).is_canalizing()  # Parity is not canalizing
False

boofun.analysis.canalization.get_canalizing_variables(f: BooleanFunction) → List[Dict][source]

Find all canalizing variables and their canalizing inputs/outputs.

Parameters:

f – Boolean function to analyze

Returns:

‘variable’: index of canalizing variable
’canalizing_input’: the input value (0 or 1) that canalizes
’canalized_output’: the forced output value (0 or 1)

Return type:

List of dicts, each containing

Example

>>> import boofun as bf
>>> bf.AND(3).get_canalizing_variables()
[{'variable': 0, 'canalizing_input': 0, 'canalized_output': 0}, ...]

boofun.analysis.canalization.get_canalizing_depth(f: BooleanFunction) → int[source]

Compute the canalizing depth of a Boolean function.

The canalizing depth is the maximum k such that the function is k-canalizing (has k layers of nested canalization).

A function is k-canalizing if: 1. It has a canalizing variable x_i1 with input a1 → output b1 2. The subfunction f|_{x_i1 ≠ a1} is (k-1)-canalizing

Parameters:: f – Boolean function to analyze
Returns:: Canalizing depth (0 for non-canalizing functions)

Example

>>> import boofun as bf
>>> bf.AND(3).get_canalizing_depth()  # AND is fully nested canalizing
3
>>> bf.parity(3).get_canalizing_depth()  # Parity has depth 0
0

boofun.analysis.canalization.is_k_canalizing(f: BooleanFunction, k: int) → bool[source]

Determine if a Boolean function is k-canalizing.

A function is k-canalizing if it has at least k layers of nested canalization.

Parameters:

f – Boolean function to test
k – Required canalizing depth (0 ≤ k ≤ n)

Returns:

True if function is at least k-canalizing

Example

>>> import boofun as bf
>>> bf.AND(3).is_k_canalizing(3)  # AND is fully nested
True
>>> bf.parity(3).is_k_canalizing(1)  # Parity is not even 1-canalizing
False

boofun.analysis.canalization.is_nested_canalizing(f: BooleanFunction) → bool[source]

Determine if a Boolean function is nested canalizing (NCF).

A function on n variables is nested canalizing if it has canalizing depth n (every variable is canalizing in some layer).

NCFs are important in biological modeling.

Parameters:: f – Boolean function to test
Returns:: True if function is nested canalizing

Example

>>> import boofun as bf
>>> bf.AND(3).is_nested_canalizing()  # AND is NCF
True
>>> bf.majority(3).is_nested_canalizing()  # Majority is not NCF
False

boofun.analysis.canalization.get_essential_variables(f: BooleanFunction) → List[int][source]

Find all essential (non-degenerate) variables.

A variable is essential if there exists some input where flipping that variable changes the output.

Parameters:: f – Boolean function to analyze
Returns:: List of indices of essential variables

Example

>>> import boofun as bf
>>> len(bf.AND(3).get_essential_variables())
3

boofun.analysis.canalization.get_input_types(f: BooleanFunction) → Dict[int, str][source]

Classify each input variable by its type.

Types: - “positive”: f is monotone increasing in this variable - “negative”: f is monotone decreasing in this variable - “conditional”: f depends on this variable non-monotonically - “non-essential”: f does not depend on this variable

Parameters:: f – Boolean function to analyze
Returns:: Dict mapping variable index to type string

Example

>>> import boofun as bf
>>> bf.AND(3).get_input_types()
{0: 'positive', 1: 'positive', 2: 'positive'}

boofun.analysis.canalization.get_symmetry_groups(f: BooleanFunction) → List[Set[int]][source]

Find groups of symmetric (interchangeable) variables.

Two variables are symmetric if swapping their values in any input does not change the function’s output.

Parameters:: f – Boolean function to analyze
Returns:: List of sets, where each set contains indices of variables that are mutually symmetric.

Example

>>> import boofun as bf
>>> bf.AND(3).get_symmetry_groups()  # All variables symmetric
[{0, 1, 2}]
>>> bf.dictator(3, 0).get_symmetry_groups()
[{1, 2}, {0}]  # Only non-dictator vars symmetric

boofun.analysis.canalization.input_redundancy(f: BooleanFunction) → float[source]

Compute input redundancy: fraction of inputs that are redundant.

Input redundancy quantifies how many inputs are not needed to determine the output on average. Constant functions have redundancy 1, parity has redundancy 0.

This is computed as: k_r / n where k_r is the average number of redundant inputs across all input combinations.

Parameters:: f – Boolean function to analyze
Returns:: Input redundancy in [0, 1]

Note

This is a simplified version. For full CANA-style redundancy, install the CANA package.

boofun.analysis.canalization.edge_effectiveness(f: BooleanFunction) → ndarray[source]

Compute edge effectiveness for each variable.

Edge effectiveness measures how much flipping a variable influences the output. This is related to the influence but normalized differently.

e_i = Pr[f(x) ≠ f(x ⊕ e_i)]

This is equivalent to the influence Inf_i[f].

Parameters:: f – Boolean function to analyze
Returns:: Array of effectiveness values in [0, 1]

boofun.analysis.canalization.effective_degree(f: BooleanFunction) → float[source]

Compute effective degree: sum of edge effectiveness.

This is equivalent to the total influence I[f].

Parameters:: f – Boolean function to analyze
Returns:: Effective degree (= total influence)

class boofun.analysis.canalization.CanalizationAnalyzer(f: BooleanFunction)[source]

High-level analyzer for canalization properties.

Example

>>> import boofun as bf
>>> analyzer = CanalizationAnalyzer(bf.AND(4))
>>> analyzer.summary()

__init__(f: BooleanFunction)[source]

Initialize analyzer.

Parameters:: f – Boolean function to analyze

is_canalizing() → bool[source]: Check if function is canalizing.

canalizing_depth() → int[source]: Get canalizing depth.

canalizing_variables() → List[Dict][source]: Get all canalizing variables.

is_nested_canalizing() → bool[source]: Check if function is nested canalizing.

essential_variables() → List[int][source]: Get essential variables.

input_types() → Dict[int, str][source]: Get input type classification.

symmetry_groups() → List[Set[int]][source]: Get symmetry groups.

input_redundancy() → float[source]: Get input redundancy.

summary() → Dict[source]

Get comprehensive canalization summary.

Returns:: Dictionary with all canalization metrics