核心种质筛选-05底层算法

Posted on | Post modified | In

核心种质优化的底层原理。

核心矛盾：代表性 vs 内部多样性

任何一种核心种质筛选算法，本质上都是在求解一个多目标优化（或带约束优化）问题，算法的设计主要面临两大相互制约的目标：

  • 代表性（Representativeness）：核心集需要完美覆盖整个群体的特征分布，像影子一样“代表”全集。这要求在数学上最小化全集到核心集的距离。
  • 内部多样性（Internal Diversity）：核心集内部个体之间应尽量不同，降低互相之间的冗余。这要求在数学上最大化核心集内部个体间的距离。

追求极致代表性可能把核心集挤在数据密度最高的中心区域；而追求极致内部多样性又可能导致算法只去“薅”那些分布边缘的离散样本，丢失了群体的主体特征。底层算法的每一次演进，正是在这二者之间寻找更高效的破局点。

核心种质筛选算法的演进路线

伴随着对保护遗传学指标理解的深入，以及计算机算力的发展，抽样与优化算法经历了以下几个主流阶段：

分层抽样法（Stratified Sampling）

  • 核心思想：这是一种基于规则的传统算法。首先计算遗传距离或表型距离矩阵，对材料进行聚类分层（Cluster），然后从每个类簇中按照预设比例抽出样本。
  • 分配策略：
    • C策略 (Constant)：每个类簇抽取固定数量（容易导致小群过度代表，大群代表不足）。
    • P策略 (Proportional)：按类簇成员数比例分配（目前较常用的基线方法）。
    • L策略 (Logarithm)：按类簇成员数的对数进行分配，以平衡大小群落差异。
    • 按多样性分配：后期研究证实，按各个簇内部的多样性水平来分配抽取名额，能得到最高质量的核心集。

等位基因富集法（M-method & MSTRAT）

  • 核心思想：彻底抛开个体距离的概念，算法的唯一数学目标是最大化“全集观测到的等位基因在核心集中得到保留”的概率，直接暴力构建高遗传丰度（Allelic richness）。
  • 算法实现：经典软件 MSTRAT 实现了一种广义的 M-method。它从全集开始进行采样，使用基础的爬山算法（Hill-climbing algorithm），通过不断替换组内样本来迭代搜索等位基因丰度的局部最优解。

逐步排除与启发式算法（Stepwise Elimination）

  • 核心思想：做减法的逻辑。从满负荷的全集开始，每轮迭代都会在群体里寻找一对“数学距离最近（最冗余）”的个体，并利用规则淘汰掉其中一个，直至规模缩减到期望值。
  • 算法实现：经典软件 SimEli。剔除时的准则可以是随机的（最小距离逐步随机抽样），也可以是评估剔除谁能使“剩余集合的期望杂合度”或“到剩余个体的总体距离”最大化。它在去冗余方面收敛很快。

基于 K-medoids 的代表性优化（GDOpt）

  • 核心思想：既然业务要求“每个全集个体都能在核心集中找到一个极其相似的兄弟”，那就用类似无监督聚类的中心点思维。将整个数据集划分到若干个中心（Medoids）周围，并将这些中心直接作为核心集。
  • 算法实现：GDOpt (Genetic distance optimization strategy) 就是这一流派的代表。该算法的唯一目标是粗暴且极其有效地最小化 A-NE（Accession-to-Nearest-Entry，即全集到代表的距离）。

变长规模覆盖算法（Variable Size Core Sampling）

  • 核心思想：颠覆了“给定样本数去优化指标”的常规思路，反过来要求“必须 100% 覆盖所有的等位基因和性状”，然后由算法去求解最小所需的核心集规模（样本数）。
  • 算法实现：PowerCore 使用启发式算法完成全覆盖；而 GenoCore 则专门针对高密度标记（如几十万个 SNP 位点）的矩阵计算进行了深度性能优化。

Core Hunter 的算法演进与底层逻辑

在目前的工业级项目中，Core Hunter 3 (CH3) 是最常被使用、也最灵活的软件。它把“多目标优化”集成得极其完备。回顾 Core Hunter 的算法迭代史，恰好能说明为什么我们在 03 篇操作中要选用那些参数组合。

CH1 & CH2：从平均距离到“最大化最小距离”的性能困境

在早期算法理论中，为了让核心集极其丰富，人们认为应当去最大化条目间的平均距离（Average distance）。

  • 严重的缺陷：这导致算法走上了歧途——疯狂去挑选那些数据分布上极其边缘的“奇异样本/离群值”，反而忽略了占主体的正常遗传类型。
  • CH2 的救火策略：为了规避这个问题，Core Hunter 2 在算法中增加了一个约束目标：在最大化平均距离的同时，还必须最大化条目间的最小距离（Minimum distance）。
  • 算力灾难：代价是巨大的。优化平均距离用快速的局部搜索算法就行，但要优化最小距离，CH2 不得不设计一套极其复杂的 MixRep（混合副本搜索） 架构。它需要并行多套不同类型的随机局部搜索和构建算法，在陷入局部最优时还会像遗传算法那样强行交叉组合解集空间。这使得大规模运算变得异常缓慢。

CH3：基于 E-NE 与 A-NE（当前主流策略）

Odong 等学者提出用新的距离总结指标来替换单纯的“平均距离”，这一理论直接成为了 Core Hunter 3 的绝对算法基石：

  1. 优化内部多样性：弃用“平均距离”，转而最大化 E-NE (Entry-to-Nearest-Entry，在 Core Hunter 中简称为 EN)，即核心集内每个个体到其最近邻的距离。它完美地剥离了冗余，且不会过度吸引分布极端的离群样本。
  2. 优化代表性：使用 A-NE (Accession-to-Nearest-Entry，在 Core Hunter 中简称为 AN)，即全体样本到核心集最近邻的距离，来强迫核心集涵盖所有的真实分布。

CH3 引擎相比前辈的降维打击：

  • 抛弃沉重的 MixRep：CH3 团队在数学上证实，当你最大化 E-NE 时，系统会间接且自然地拔高条目间的“最小距离”。这意味着当年把 CH2 拖垮的 MixRep 算法彻底没用了，CH3 重新回归到了极快的快速局部搜索（Fast local search）。
  • 并行回火（Parallel Tempering）的威力：这是 CH3 用来逃出局部最优陷阱的启发式大招。算法允许生成多条平行的搜索链，它们处在不同的“温度（随机扰动程度）”下寻优。当链条陷入死胡同，它们会定期交换状态。这样能在高维的基因组位点空间中迅速逼近多目标优化的帕累托前沿（Pareto Front）。
  • 多维度距离度量引擎：为了兼容不同数据，CH3 开放了底层距离度量方法的切换。若是基因型，默认距离为改良罗杰斯距离（Modified Roger’s distance，简写为 MR）；若是表型，默认距离为 Gower 距离（Gower’s distance，简写为 GD）。通过组合加权目标函数（例如 list(objective("EN", "MR"), objective("AN", "MR"))），可以在极低算力开销下完美达成兼顾多样性与代表性的复杂业务要求。