2025-11-22T15:25:16.453421

Complexity and accessibility of random landscapes

Pahujani, Krug

These notes introduce probabilistic landscape models defined on high-dimensional discrete sequence spaces. The models are motivated primarily by fitness landscapes in evolutionary biology, but links to statistical physics and computer science are mentioned where appropriate. Elementary and advanced results on the structure of landscapes are described with a focus on features that are relevant to evolutionary searches, such as the number of local maxima and the existence of fitness-monotonic paths. The recent discovery of submodularity as a biologically meaningful property of fitness landscapes and its consequences for their accessibility is discussed in detail.

academic

Complexity and accessibility of random landscapes

基本信息

论文ID: 2502.05896
标题: Complexity and accessibility of random landscapes
作者: Sakshi Pahujani, Joachim Krug (University of Cologne)
分类: q-bio.PE (Population and Evolution), cond-mat.dis-nn (Disordered Systems), math.PR (Probability)
发表时间: 2025年 (SciPost Physics Lecture Notes Submission)
论文链接: https://arxiv.org/abs/2502.05896

摘要

本文介绍了定义在高维离散序列空间上的概率景观模型。这些模型主要受进化生物学中适应性景观的启发，同时也涉及统计物理和计算机科学的相关内容。文章描述了景观结构的基础和高级结果，重点关注与进化搜索相关的特征，如局部最大值的数量和适应性单调路径的存在性。详细讨论了亚模性作为适应性景观生物学意义属性的最新发现及其对景观可达性的影响。

研究背景与动机

核心问题

高维景观导航问题：在生物进化、自旋玻璃系统和神经网络优化等多个领域中，都涉及在高维复杂景观上的导航问题
适应性景观的结构特征：理解适应性景观中局部最大值（峰值）的分布和可达性
Wright vs Fisher争论：解决进化生物学中关于适应性景观是崎岖难以导航（Wright观点）还是相对可达（Fisher观点）的经典争论

研究重要性

跨学科应用：该研究连接了进化生物学、统计物理学和计算机科学
实际意义：帮助理解进化过程的可预测性和重复性
理论价值：为高维随机景观提供数学框架和分析工具

现有方法局限性

完全随机模型（如House of Cards模型）过于简化，不能反映真实生物系统的相关性
缺乏对结构化景观可达性的系统性理解
对亚模性等重要数学性质在生物学中的意义认识不足

核心贡献

统一的数学框架：建立了分析高维离散序列空间上概率景观的完整理论体系
可达性相变理论：揭示了随机景观中可达路径存在的相变现象，确定了临界阈值
亚模性与可达性的联系：首次系统阐述了亚模适应性景观的子集-超集可达性性质
适应性吸引盆地理论：提供了亚模景观中适应性吸引盆地大小的指数下界
跨学科连接：建立了Fisher几何模型与反铁磁Hopfield模型的映射关系

方法详解

任务定义

研究在高维离散序列空间 $\{0,1,...,a-1\}^L$ 上定义的适应性景观，分析其结构特征（如峰值数量）和动力学性质（如可达路径的存在性）。

核心模型

1. House of Cards (HoC) 模型

定义：适应性值为独立同分布连续随机变量
峰值概率： $P_{\max} = \frac{1}{(a-1)L+1}$
期望峰值数： $E(N_L) = \frac{a^L}{(a-1)L+1}$
复杂度： $\Λ = \lim_{L→∞} \frac{1}{L}\log E(N_L) = \ln a$

2. 可达性分析

直接路径可达性：

概率： $P_{β,l} = \frac{β^{l-1}}{(l-1)!}$
期望路径数： $E(X_{α,ω}) = lβ^{l-1}$
临界阈值： $β_c(l) = 1 - \frac{\ln l}{l}$

间接路径可达性：

扩展适应性景观方法处理自相交路径
期望准可达路径数： $E[\tilde{X}_{α,ω}] ∼ \prod_{k,l=0}^{a-1}[(e^βA)_{k,l}]^{p_{k,l}L}$
二元情况下的条件： $\sinh(β_c)^δ \cosh(β_c)^{1-δ} = 1$

3. 结构化景观

NK模型： $g(σ) = \sum_{i=1}^b g_i(σ_{i,1}, σ_{i,2}, ..., σ_{i,k})$

粗糙富士山模型： $g(σ) = -cd(σ,σ^*) + ξ_σ$

复合基因型-表现型-适应性映射： $g(σ) = Φ[z(σ)], \quad z(σ) = \sum_{i=1}^L \sum_{μ=0}^{a-1} a_{i,μ}δ_{σ_i,μ}$

技术创新点

1. 亚模性理论

通用上位性条件： $g(σ ∪ τ) - g(σ) ≤ g(σ' ∪ τ) - g(σ')$ ，其中 $σ' ⊆ σ$
等价于亚模性： $g(A ∪ B) + g(A ∩ B) ≤ g(A) + g(B)$
生物学构造：凹函数表现型-适应性映射产生亚模景观

2. 子集-超集可达性性质

定理：任何峰值都可以从其所有子集和超集通过直接路径到达
证明思路：利用通用负上位性条件和峰值的局部最优性质

3. 适应性吸引盆地

下界公式： $S_σ ≥ 2^{|σ|} + 2^{L-|σ|} - 2$
指数增长：吸引盆地大小随基因型空间指数增长

实验设置

理论分析框架

本文主要采用理论分析方法，包括：

概率论分析（马尔可夫不等式、中心极限定理）
组合优化理论（亚模函数理论）
渗流理论（可达性相变）
图论方法（Hamming图、适应性图）

数学工具

Hamming距离： $d(σ,τ) = \sum_{i=1}^L (1-δ_{σ_i,τ_i})$
适应性图：通过将连边指向适应性增加方向构造的有向无环图
复杂度定义： $Λ = \lim_{L→∞} \frac{1}{L}\log E(N_L)$

实验结果

主要理论结果

1. HoC模型的精确解

峰值统计：证明了峰值数满足中央极限定理，具有亚泊松统计特征
方差公式： $\text{Var}(N_L) = \frac{a^L(a-1)(L-1)}{2\{(a-1)L+1\}^2}$
Wright-Fisher争论解决：在高维极限下，单个基因型成为峰值的概率趋于0（支持Fisher），但峰值总数趋于无穷（支持Wright）

2. 可达性相变现象

临界行为：存在明确的相变阈值 $β_c(l) = 1 - \frac{\ln l}{l}$
相变特征：
- $β < β_c(l)$ ： $\lim_{l→∞} P[X_{α,ω} ≥ 1] = 0$
- $β > β_c(l)$ ： $\lim_{l→∞} P[X_{α,ω} ≥ 1] = 1$