📐 Mathematical Behind

Dany Mukesha

2025-07-03

Introduction

This report provides a detailed mathematical analysis of the BioGA R package, which implements a multi-objective genetic algorithm (GA) for genomic data optimization. The analysis covers all major components of the algorithm with formal mathematical notation and proofs where applicable.

Genetic Algorithm Framework

The package implements a standard generational GA with the following components:

1. Population Initialization
2. Fitness Evaluation
3. Selection (NSGA-II inspired)
4. Crossover (SBX)
5. Mutation (Adaptive)
6. Replacement (Elitism + Diversity Preservation)

Mathematical Representation

Let:

• $G = (V, E)$ be the gene network where $V = \{g_1, g_2, \ldots, g_n\}$ are genes
• $X \in \mathbb{R}^{n \times m}$ be the genomic data matrix ($n$ genes × $m$ samples)
• $P_t \in \mathbb{R}^{p \times n}$ be the population at generation $t$ ($p$ individuals × $n$ genes)

The GA can be represented as:

$$P_{t+1} = R(M(C(S(P_t, f(P_t)), X)), P_t, f(P_t))$$

Where:

• $f$: Fitness evaluation function

• $S$: Selection operator

• $C$: Crossover operator

• $M$: Mutation operator

• $R$: Replacement operator

Population Initialization

Mathematical Formulation

Given genomic data $X \in \mathbb{R}^{n \times m}$ and population size $p$:

$$P_0[i,j] = X[j, k] \quad \text{where} \quad k \sim \text{Uniform}\{1, \ldots, m\}$$

With clustering (if provided): For each cluster $c \in C$:

$$P_0[i,j] = X[j, k] \quad \forall j \in c, \quad k \sim \text{Uniform}\{1, \ldots, m\}$$

Properties

1. Maintains original data distribution per gene
2. Preserves cluster structure if provided
3. Expected value: $\mathbb{E}[P_0[i,j]] = \mu_j$ (mean of gene $j$)

Fitness Evaluation

The package implements a multi-objective fitness function with two components:

Objective 1: Expression Difference

$$f_1(i) = \sum_j \sum_k (X_{jk} - P_{ij})^2$$

This measures how well the individual matches the observed expression patterns.

Properties:

1. Convex function with minimum at $P_{ij} = \mu_j$

2. Gradient: $\nabla f_1 = -2\sum_k(X_{jk} - P_{ij})$

Objective 2: Sparsity

$$f_2(i) = \frac{\sum_j I(|P_{ij}| > \epsilon)}{n}$$

Where $I$ is the indicator function and $\epsilon$ is a small constant ($10^{-6}$).

Properties:

1. Non-convex, non-differentiable

2. Encourages sparse solutions

3. Range: $[0, 1]$

Combined Fitness

$$F(i) = w_1f_1(i) + w_2f_2(i)$$

Where $w$ are user-provided weights.

Selection (NSGA-II Inspired)

The selection implements a simplified version of NSGA-II’s non-dominated sorting:

Domination Criteria

Individual $i$ dominates $j$ iff:

$$\forall k: f_k(i) \leq f_k(j) \quad \text{and} \quad \exists k: f_k(i) < f_k(j)$$

Proof of Partial Order:

1. Reflexive: No individual dominates itself

2. Antisymmetric: If $i$ dominates $j$, $j$ cannot dominate $i$

3. Transitive: If $i$ dominates $j$ and $j$ dominates $k$, then $i$ dominates $k$

Front Construction

1. Compute domination counts and dominated sets
2. First front: Individuals with domination count $= 0$
3. Subsequent fronts: Remove current front, update counts

Theorem: The front construction algorithm terminates in $O(p^2o)$ time where $p$ is population size and $o$ is number of objectives.

Proof:

• Domination check between two individuals is $O(o)$

• All pairs check is $O(p^2o)$

• Front construction is $O(p)$ per front

Crossover (Simulated Binary Crossover - SBX)

Given parents $x, y \in \mathbb{R}^n$, create offspring $z$:

For each gene $j$: With probability $p_c$: $$\begin{aligned} u &\sim \text{Uniform}(0,1) \\ \beta &= \begin{cases} (2u)^{1/(\eta+1)} & \text{if } u \leq 0.5 \\ \left(\frac{1}{2(1-u)}\right)^{1/(\eta+1)} & \text{otherwise} \end{cases} \\ z_j &= 0.5[(x_j + y_j) - \beta|y_j - x_j|] \end{aligned}$$ Else: $$z_j = x_j$$

Properties:

1. Preserves mean: $\mathbb{E}[z_j] = \frac{x_j + y_j}{2}$

2. Variance controlled by $\eta$ (distribution index)

3. For $\eta \to 0$: approaches uniform crossover

4. For $\eta \to \infty$: approaches no crossover ($z = x$ or $y$)

Mutation

Adaptive mutation with network constraints:

For each gene $j$: With probability $p_m(t) = p_0(1 + 0.5t/T)$: $$\begin{aligned} \Delta_j &\sim N(0, \sigma^2) \\ \text{If network provided:} & \quad z_j \leftarrow z_j + \Delta_j(1 - \sum_k N_{jk}z_k) \\ \text{Else:} & \quad z_j \leftarrow z_j + \Delta_j \end{aligned}$$

Properties:

1. Mutation rate increases with generation $t$

2. Network term reduces mutation magnitude for highly connected genes

3. Expected change: $\mathbb{E}[\Delta z_j] = 0$

4. Variance: $\text{Var}(\Delta z_j) = \sigma^2(1 - \sum_k N_{jk}z_k)^2$ if network provided

Replacement

Elitism + diversity-preserving replacement:

1. Keep best individual: $x^* = \text{argmin } f_1(x)$
2. For remaining replacements:
   • Select random individual $x$
   • Select offspring $y$
   • Replace $x$ with $y$ if $\text{diversity}(x,y) > \epsilon$

Where $\text{diversity}(x,y) = \|x - y\|_2^2$

Theorem: This strategy preserves elitism while maintaining population diversity.

Proof:

1. Best solution is never lost

2. Expected diversity is non-decreasing since replacements only occur when diversity increases

Convergence Analysis

The algorithm can be shown to converge under certain conditions:

Assumptions:

1. Finite search space

2. Strictly positive mutation probability 3. Elitism is maintained

Theorem: The algorithm converges in probability to the Pareto front.

Proof Sketch:

1. The selection and replacement strategies preserve Pareto optimal solutions (elitism)

2. Mutation provides ergodicity (any state reachable)

3. By the multi-objective GA convergence theorems (Rudolph 1998), the algorithm converges to the Pareto front

Computational Complexity

Let: - $p$ = population size - $n$ = number of genes - $m$ = number of samples - $o$ = number of objectives - $T$ = number of generations

Component Complexities:

1. Initialization: $O(pn)$

2. Fitness Evaluation: $O(Tpmn)$ (parallelized)

3. Selection: $O(Tp^2o)$ worst case

4. Crossover: $O(Tpn)$

5. Mutation: $O(Tpn)$

6. Replacement: $O(Tpn)$

Total Complexity: $O(Tp(po + mn))$

Mathematical Optimization Interpretation

The algorithm can be viewed as a stochastic optimization method for:

$$\begin{aligned} \text{minimize } & (f_1(P), f_2(P)) \\ \text{subject to } & P \in \mathbb{R}^{p \times n} \end{aligned}$$

Where: - $f_1$ measures data fidelity - $f_2$ measures sparsity

The GA approach is particularly suitable because:

1. The problem is multi-objective

2. The search space is high-dimensional

3. The fitness landscape may be non-convex

4. Sparsity objective is non-differentiable

Special Cases and Relationships

1. Single Objective Case ($w_2 = 0$):
   • Reduces to nonlinear least squares optimization
   • GA serves as global optimizer avoiding local minima
2. No Network Constraints:
   • Mutation becomes standard Gaussian mutation
   • Problem decomposes by genes
3. High Crossover Rate:
   • Approaches a recombination-based search
   • Faster convergence but reduced diversity

Biological Interpretation

The mathematical operations correspond to biological concepts:

1. Population Initialization: Sampling from observed biological variability
2. Fitness: Measuring both functional efficacy (expression matching) and parsimony (sparsity)
3. Network Constraints: Incorporating known gene-gene interactions
4. Clustering: Respecting co-expressed gene modules

Conclusion

This mathematical foundation shows that the BioGA package implements a theoretically sound multi-objective evolutionary algorithm for genomic data optimization, with proper attention to both computational efficiency and biological relevance.

Session Info

sessioninfo::session_info()
#> ─ Session info ───────────────────────────────────────────────────────────────
#>  setting  value
#>  version  R version 4.5.1 (2025-06-13)
#>  os       Ubuntu 24.04.2 LTS
#>  system   x86_64, linux-gnu
#>  ui       X11
#>  language en
#>  collate  C.UTF-8
#>  ctype    C.UTF-8
#>  tz       UTC
#>  date     2025-07-03
#>  pandoc   3.1.11 @ /opt/hostedtoolcache/pandoc/3.1.11/x64/ (via rmarkdown)
#>  quarto   NA
#> 
#> ─ Packages ───────────────────────────────────────────────────────────────────
#>  package     * version date (UTC) lib source
#>  BiocManager   1.30.26 2025-06-05 [1] RSPM
#>  BiocStyle   * 2.36.0  2025-04-15 [1] Bioconduc~
#>  bookdown      0.43    2025-04-15 [1] RSPM
#>  bslib         0.9.0   2025-01-30 [1] RSPM
#>  cachem        1.1.0   2024-05-16 [1] RSPM
#>  cli           3.6.5   2025-04-23 [1] RSPM
#>  desc          1.4.3   2023-12-10 [1] RSPM
#>  digest        0.6.37  2024-08-19 [1] RSPM
#>  evaluate      1.0.4   2025-06-18 [1] RSPM
#>  fastmap       1.2.0   2024-05-15 [1] RSPM
#>  fs            1.6.6   2025-04-12 [1] RSPM
#>  htmltools     0.5.8.1 2024-04-04 [1] RSPM
#>  htmlwidgets   1.6.4   2023-12-06 [1] RSPM
#>  jquerylib     0.1.4   2021-04-26 [1] RSPM
#>  jsonlite      2.0.0   2025-03-27 [1] RSPM
#>  knitr         1.50    2025-03-16 [1] RSPM
#>  lifecycle     1.0.4   2023-11-07 [1] RSPM
#>  pkgdown       2.1.3   2025-05-25 [1] any (@2.1.3)
#>  R6            2.6.1   2025-02-15 [1] RSPM
#>  ragg          1.4.0   2025-04-10 [1] RSPM
#>  rlang         1.1.6   2025-04-11 [1] RSPM
#>  rmarkdown     2.29    2024-11-04 [1] RSPM
#>  sass          0.4.10  2025-04-11 [1] RSPM
#>  sessioninfo   1.2.3   2025-02-05 [1] RSPM
#>  systemfonts   1.2.3   2025-04-30 [1] RSPM
#>  textshaping   1.0.1   2025-05-01 [1] RSPM
#>  xfun          0.52    2025-04-02 [1] RSPM
#>  yaml          2.3.10  2024-07-26 [1] RSPM
#> 
#>  [1] /home/runner/work/_temp/Library
#>  [2] /opt/R/4.5.1/lib/R/site-library
#>  [3] /opt/R/4.5.1/lib/R/library
#>  * ── Packages attached to the search path.
#> 
#> ──────────────────────────────────────────────────────────────────────────────