基于子空间进化的基因表达数据双聚类方法(SSEB)创新研究

《Algorithms》:Biclustering Gene Expression Data with Subspace Evolution

【字体: 大 中 小 】 时间:2026年01月02日 来源:Algorithms 2.1

编辑推荐:

  本文提出一种基于子空间进化的双聚类方法(SSEB),通过子空间划分策略将搜索空间从2m+n降至k×2m/k+n,并结合亲和传播聚类(AP-cluster)优化NSGA-II的选择算子。实验表明,SSEB在合成和真实基因表达数据集上相比典型算法将平均恢复率提升57.31%,运行时间减少63.42%,为高通量基因组数据分析提供了高效解决方案。

  

摘要

双聚类在基因表达数据分析中至关重要,但基于进化算法的方法常面临高计算成本问题。为解决此问题,本研究提出一种新颖的基于子空间进化的双聚类方法(SSEB),通过约束搜索空间和增强种群多样性显著减少运行时间。该方法首先将原始表达矩阵划分为子矩阵,利用新设计的选择策略高效识别双聚类种子,随后通过扩展和合并形成最终双聚类。在合成和真实基因表达数据集上的实验评估表明,SSEB在双聚类质量上优于现有典型算法,平均恢复率提升57.31%,且相比最先进的进化双聚类方法运行时间减少约63.42%。

1. 引言

微阵列技术的快速发展使其在生物医学研究中发挥重要作用,可测量多种条件下的基因表达水平并生成大量数据,最终结构化为基因表达数据矩阵。由基因子集和条件子集构成的局部相干块可用于挖掘生物信息,双聚类(而非单向聚类)常被用于提取此类局部相干块。
双聚类问题最初被提出用于搜索恒定值双聚类,后用于分析基因表达数据。研究目标是使双聚类中的行/列具有强相关性/相干性,同时希望双聚类体积较大。在典型基因表达矩阵中,行对应基因,列对应样本(如患者、组织或实验条件),矩阵中的每个条目代表特定基因在特定样本中的表达水平。双聚类的目标是识别在样本子集中表现出一致表达模式(如相关)的基因子集。此类双聚类可揭示功能基因模块(如通路),在特定样本类别(如疾病亚型)中特征性活跃或抑制,从而为分析赋予直接生物学意义。然而,强相干性和大体积是两个冲突目标。因此,大量多目标进化算法(MOEA)被提出以同时优化冲突目标。
文献中大多数基于MOEA的双聚类算法使用二进制字符串编码个体,其长度为行数和列数之和。然而,这种编码方法存在局限性。随着基因表达数据规模增大,由于个体长度与搜索空间之间的指数关系,搜索空间趋于极大。大搜索空间可能导致MOEA无法在合理时间内找到最优双聚类。因此,本研究将整个空间划分为多个子空间以减小搜索空间。由于基因表达数据矩阵中行数大于列数,本研究沿行方向划分搜索空间。如图所示,上子图中整个搜索空间为2m+n;下子图中行被划分为k等分,每部分的搜索空间为2m/k+n,整个搜索空间为k×2m/k+n。通过划分子空间,整个搜索空间将显著减小。下子图展示了整体策略:首先划分子空间,随后用MOEA从每个子空间寻找双聚类种子,最后将这些种子扩大至整个空间的双聚类。
此外,由于进化算法的内在特性,双聚类种群的多样性可能不高,尽管NSGA-II能够找到有希望的区域。因此,我们旨在引入聚类算法解决此问题。在NSGA-II中,帕累托支配策略无法提供足够的选择压力以向最优解进展。精英解主要通过非支配排序方法选择,然后通过拥挤距离计算选择。此类选择算子效率不足,因为大多数解仅通过非支配方法选择而未考虑解的多样性。因此,所选解易陷入局部最优。据此,我们旨在提出一种新颖易用的选择算子,在非支配排序前考虑个体多样性和高效率。本研究设计了一种使用传统聚类方法改进NSGA-II的选择算子。聚类是一种无监督分类方法,将个体集合划分为K个不相交簇,同一簇中的个体比不同簇中的个体更相似。在NSGA-II中,解根据非支配等级和拥挤距离等级选择,可能选择一些非支配等级较高但拥挤距离等级较差的解,导致多样性不足。为缓解此情况,我们创新性地应用apcluster方法,从每个不相交簇中选择非支配等级较高的解,可能同时保证所选解的收敛性和多样性。本研究中使用聚类算法允许从搜索空间的不同区域选择代表性个体,从而更高效地获得均匀分布的解。此外,通过从每个簇选择代表性个体,可避免选择相似解(更可能存在于同一簇中),从而节省相似个体的可观计算时间。
由于所提出的双聚类方法基于子空间进化,故命名为SSEB。其技术贡献可总结如下:
  • •
    提出双聚类的“子空间协同进化”框架,通过行子空间划分策略(核心思想是从每个子空间寻找双聚类种子然后扩大种子)减小搜索空间。
  • •
    提出多目标双聚类中种群多样性维护的形式化解决方案,通过改进的选择算子自动聚类搜索空间并保留每个簇中最具代表性的个体到下一代,导致更快的收敛速度和更均匀的最优解分布。
  • •
    实验结果验证所提方法能找到更优双聚类并节省可观时间。
后续章节组织如下:第2节介绍相关工作,第3节详细描述方法,第4节展示实验,第5节给出讨论和结论。

2. 相关工作

2.1. 预备知识

2.1.1. 双聚类类型
如前所述,双聚类是由行子集和列子集组成的具有相干模式的子矩阵。根据基因在实验条件下表达的相干模式,已提出并分类多种双聚类类型。定义双聚类为包含|R|个基因和|C|个条件的子矩阵B,常见三种类型定义如下:
  • •
    平移型:bij= c + αi
  • •
    缩放型:bij= c × βj
  • •
    缩放平移型:bij= ci× βj+ αj
    其中c为常数值;αi和αj分别指基因i和条件j的加性系数;βi和βj分别为行i和列j的乘性系数;ci(1≤i≤|R|)对应每个基因/行i的常数值。平移和缩放模式分别对应加性和乘性模式。
2.1.2. 质量度量
质量度量可评估双聚类质量,帮助双聚类算法找到更优双聚类。平移双聚类的常用度量是均方残差(MSR),计算公式为(1);缩放双聚类的常用度量是平方均方残差(SMSR),计算公式为(2)。
MSR(B) = ∑i∈R,j∈C(bij- biC- bRj+ bRC)2/ (|R|?|C|) (1)
SMSR(B) = ∑i∈R,j∈C(bij- biC- bRj+ bRC)2/ (biC2? bRj2) / (|R|?|C|) (2)
其中biC= ∑j∈Cbij/|C|, bRj= ∑i∈Rbij/|R|, bRC= ∑i∈R,j∈Cbij/(|R|?|C|) (3)
2.1.3. 多目标进化算法(MOEAs)
多目标优化问题涉及多个需最小化或最大化的目标函数。由于目标间的冲突,难以获得单一解,因此需搜索多个最优解(称为帕累托集)。帕累托最优解由其支配关系确定。对于具有m个目标和n维变量的多目标最小化问题,可表达为:
最小化 F(x) = 最小化 fi(X) i=1,2,…,m (4)
X = (x1,x2,…,xn) ∈ Rn(5)
其中X是包含n个元素的向量,fi(X)是第i个目标函数。
解X1支配解X2当且仅当满足以下两个要求:
fi(X1) ≤ fi(X2) ?i=1,2,…,m (6)
fj(X1) < fj(X2) ?j∈{1,2,…,m} (7)
帕累托解是解空间中不存在其他解能支配的解。将所有帕累托解映射到坐标系中生成帕累托最优前沿。
MOEA的目的是高效搜索具有均匀分布的收敛个体。由于进化算法能在单次模拟运行中找到多种解,已证明能高效解决多目标问题。此外,其快速探索和识别搜索空间中有希望区域的优秀能力使其在全局搜索中表现良好。
NSGA-II是最具代表性且应用最广泛的EMO算法之一,具有三个特点:采用精英策略避免进化过程中丢失优良解;通过新颖的密度估计度量和拥挤比较算子开发显式多样性保持机制;在主循环中强调非支配解,加速收敛速度。实验结果表明NSGA-II能均匀维持帕累托最优前沿的解。
在NSGA-II中,为强调较好非支配集中的解,首先根据非支配等级选择解。如果最佳非支配集中的个体数小于选择种群的大小,则选择最佳非支配集中的所有解。此类方法可能选择一些非支配等级较高但拥挤距离等级较差的解。为此,我们创新性地提出将聚类方法融入选择过程。

2.2. 基于多目标进化算法的双聚类方法及其局限性

尽管MOEA在平衡双聚类的冲突目标(如体积vs相干性)方面展现出强大能力并已成为主流框架,但现有基于MOEA的方法(尤其是基于NSGA-II的方法)仍存在基本局限性,阻碍其应用于大规模基因表达数据分析。本小节回顾代表性工作并批判性关注其缺点,从而阐明本研究动机。
2.2.1. 维数灾难与编码效率问题
大多数基于MOEA的双聚类方法采用二进制编码,染色体长度等于基因数和条件数之和。此编码方案导致搜索空间随数据规模指数增长。对于现代高通量测序生成的大规模矩阵(如超过10,000个基因),此维数灾难使进化算法难以在合理时间内收敛到高质量解区域。例如,首次将NSGA-II应用于双聚类的开创性工作未解决大规模数据的计算可扩展性问题。类似地,Maulik等人使用的变长编码和Seridi等人采用的整数编码策略虽然在内存使用或局部搜索方面提供优化,但未从根本上改变整个空间随机搜索的性质,因此计算开销对于非常高维数据仍然过高。
2.2.2. 种群多样性定义与维护不足
NSGA-II通过非支配排序和拥挤距离计算保持种群多样性,此机制对许多问题有效。然而,在双聚类的特定背景下,解本质上是数据矩阵的子空间,传统拥挤距离度量解在目标函数空间中的分布,但未能有效捕捉其在原始行列结构空间中的多样性。这可导致算法收敛到一组在目标值上分布良好但在行列组成上高度相似的解,即“结构多样性”损失。早期研究观察到进化算法在双聚类过程中易陷入局部最优,但未提供针对双聚类结构特征专门设计的理论严谨的多样性保持算子。当前文献在“如何定义和量化双聚类种群的结构多样性”方面存在显著研究空白。
2.2.3. 现有改进策略的局限性
为提高效率,一些研究尝试融入局部搜索或与特定算法混合。然而,这些方法常引入新问题:局部搜索的集成可能增加计算负担并使算法对初始解质量更敏感;与其他算法耦合可能破坏进化过程的一致性并增加参数调优复杂性。更重要的是,这些改进很大程度上是启发式和工程导向的,缺乏统一框架同时系统解决“过大搜索空间”和“不足结构多样性”两个核心挑战。
总之,当前研究现状存在两个关键空白需解决:缺乏能够系统且实质性减小进化搜索空间维度而不损害全局解质量的理论框架;缺乏能够准确测量并有效保持双聚类种群在原始行列空间多样性的选择机制。正是为填补这些空白,本研究提出基于行子空间划分的进化框架(解决第一个问题)和基于AP聚类的选择算子(解决第二个问题)。我们的方法不仅是对NSGA-II的工程改进,更是双聚类特定背景下进化搜索范式和多样性保持理论的有针对性扩展。

3. 方法

SSEB的流程图如图所示。首先,整个数据集(搜索空间)被划分为多个子集(子空间);随后用MOEA从每个子空间挖掘双聚类种子(SB);最后通过这些种子的合并和扩展形成整个数据集(空间)的大双聚类。

3.1. 子空间划分

为获得行子空间,基因表达数据矩阵M(m?n)沿行方向均匀随机划分为Ns个不相交子空间SSi(i∈1,…,Ns)。每个子空间的大小为[m/Ns, n]。

3.2. 从子空间寻找双聚类种子

由于每个子空间独立,从每个子空间挖掘双聚类种子并行执行。进化过程参数包括初始种群大小(N)、最大代数(Ng)、交叉概率(pc)和变异概率(pm)。双聚类种群中所有个体用二进制向量表示。两个适应度函数是ACV和双聚类中元素数量。ACV基于行/列间的平均皮尔逊相关系数,可检测几乎所有类型的双聚类。双聚类的ACV计算公式为(10)。
ACV(B) = 2max{ ∑i=1|R|-1∑j=i+1|R|PCCi,j/ (|R|?(|R|-1)) , ∑i=1|C|-1∑j=i+1|C|PCCi,j/ (|C|?(|C|-1)) } (10)
PCC(i1,i2) = ∑j=1|C|(Bi1,j- Bi1,C) ? (Bi2,j- Bi2,C) / √( ∑j=1|C|(Bi1,j- Bi1,C)2? ∑j=1|C|(Bi2,j- Bi2,C)2) (11)
初始种群随机生成,其后代通过锦标赛选择、单点交叉和均匀变异过程生成。由于精英策略旨在将当前代的最佳非支配解保留到下一代,我们将初始种群和后代种群组合进行后续选择过程。合并种群的大小为2N。
3.2.1. 选择
如前所述,我们通过将亲和传播聚类算法融入选择过程改进NSGA-II算法。在每一代中,apcluster算法应用于所有个体,在搜索空间中将它们划分为K个簇。根据非支配等级从每个簇中选择代表性最优个体。从不同簇选择的代表性个体保持良好的多样性。图展示了子空间中进化的主循环,详细方法如下:
为保留后代种群中选择的解,采用apcluster算法自动将所有个体划分为K个簇,然后选择每个簇中的最优解。详细步骤包括:(1)对合并种群执行apcluster,K的最优值自动确定;(2)对合并种群中所有个体应用非支配排序,快速非支配排序方法见文献;(3)对于每个簇,从最佳非支配集中随机选择一个个体,得到K个解。
与通过apcluster选择的K个解一起,使用NSGA-II从剩余的2N-K个解中选择N-K个解。执行NSGA-II的快速非支配排序后,迭代地从领先非支配面选择解,直到解总数达到N-K。然后使用拥挤比较算子测量最后非支配面中个体的多样性,并根据其多样性等级选择解。
3.2.2. 其他算子
通过apcluster和NSGA-II获得所选解后,使用传统遗传算子(包括二进制锦标赛选择、模拟二进制交叉和多项式变异)生成后代种群,其大小也为N。选择后代种群的整个过程构成一代。我们迭代重复选择过程直到达到最大代数。

3.3. 扩大双聚类种子

3.3.1. 扩展
由于从子空间挖掘的SB尺寸较小,需将其扩展至整个空间。每个双聚类种子的扩展如下:
  • •
    对于剩余行,如果由旧SB和新插入行组成的新SB的ACV不小于原始ACV,则将行添加到SB。
  • •
    对于剩余列,如果由旧SB和新插入列组成的新SB的ACV不小于原始ACV,则将列添加到SB。
3.3.2. 合并
由于扩展的双聚类可能相互重叠,为提高双聚类多样性,使用算法1合并这些扩展的双聚类。
算法1 合并双聚类
输入:Be,扩展的双聚类;ns,Be中找到的双聚类数量;δB,预定义的双聚类ACV阈值;
输出:Bf,最终双聚类集合
1: for i∈[1,ns] do
2: for j∈[i+1,ns] do
3: if Bej不与Bei重叠 then
4: 添加Bej和Bei到Bf
5: else
6: if 合并Bei和Bej的行索引,合并Bei和Bej的列索引,用合并的行列索引构建新双聚类,如果新双聚类的ACV大于δBthen
7: 添加新合并的双聚类到Bf
8: else
9: 添加Bej和Bei到Bf
10: end if
11: end if
12: end for
13: end for
14: 移除Bf中的重复双聚类
15: return Bf

4. 实验

4.1. 实验设置

首先介绍比较方法,随后描述合成数据集的生成以及真实基因表达数据集的详细信息,最后提供评估度量和参数设置。SSEB用Matlab语言实现,代码见链接。
4.1.1. 比较方法
SSEB与文献中七种相关方法比较:FBCP、IGABA、OPSM、BIMAX、SOEA、CC和ISA。这些比较方法在该领域具有代表性,尽管OPSM、BIMAX、SOEA、CC和ISA是旧方法,但它们是典型且高引用的双聚类方法,常被用作基线比较方法。
4.1.2. 合成数据集
由于对真实基因表达数据中的双聚类了解甚少,生成合成数据集以全面评估SSEB性能。合成数据集生成过程如下:(1)生成大小为200×30的背景矩阵Mbg,Mbg中所有元素服从均匀分布U(0,1);(2)通过两步生成大小为20×20的合成双聚类:(i)生成服从U(0,1)均匀分布的参考列;(ii)将不同系数乘到/加到参考列以产生其他列;(3)随机选择索引并通过替换相应元素将合成双聚类植入Mbg。为测试SSEB的噪声容忍度,向双聚类添加服从正态分布N(0,δ2)的噪声。
4.1.3. 真实基因表达数据集
使用两个真实基因表达数据集进一步验证SSEB性能:BCLL和DLBCL。两者均为常用白血病数据集,详细信息见表1。
4.1.4. 评估度量
对于合成数据集,使用两种度量(Recovery和Relevance)。
Recovery(Br,bt) = maxbr∈Br( |br∩bt| / |br∪bt| ) (12)
Relevance(Br,bt) = 1/|Br| ∑br∈Br( |br∩bt| / |br∪bt| ) (13)
其中bt是植入的双聚类,br是双聚类方法找到的检索双聚类集合Br中的一个双聚类,|br∩bt|和|br∪bt|分别表示两个双聚类交集和并集的体积。
为进一步研究SSEB性能,使用两种额外度量RowRecovery和ColumnRecovery,其表达式如(14)和(15)所示。
RowRecovery(Br,bt) = maxbr∈Br( |R(br)∩R(bt)| / |R(br)∪R(bt)| ) (14)
ColumnRecovery(Br,bt) = maxbr∈Br( |
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号