一种基于双阶遗传计算的基因表达数据的双聚类算法

摘要

本发明公开了一种基于双阶遗传计算的基因表达数据的双聚类算法，将矩阵M中的每一列减去第k列得到矩阵M(k)，k＝1，2，…，n；对M(k)的每一列进行层次聚类，得到双聚类种子的集合；通过遗传计算获得对应的双聚类。本发明所述的算法，可解决传统基于遗传计算的双聚类算法只能针对双聚类进行选择的缺点，通过同时对行列进行优化，可提高搜索效率，并获得更优的双聚类分析效果。

说明书

技术领域

本发明涉及数据挖掘处理领域，特别涉及一种基于双阶遗传计算的基因表 达数据的双聚类算法。

背景技术

DNA微阵列技术的出现和发展使得人们可以同时检测数以千计的基因并测 量其转录mRNA的表达水平。通过在多个实验条件(如不同的实验环境,不同的时 间点，不同的组织样本)下反复地实验,可以搜集到上百个实验的基因表达数据。 基因表达数据矩阵的行代表一个基因在不同环境条件下或不同时间点的表达， 列代表不同条件或样本下(如组织、实验条件、处理因素等)所有基因的表达情 况，矩阵中的数据表示特定的基因在特定的样本中的表达水平。从获取基因表 达数据的具体过程来分析,可以得出基因表达数据有(1)数据量巨大；(2)高维 性；(3)高噪声；(4)高冗余等特点,这对数据分析算法的研究提出了更高要求和 挑战。怎样对这些海量的基因表达数据进行分析并发掘其中隐藏的信息,是当今 生物信息学的一个研究热点，也是数据挖掘领域中亟待解决的问题。

发明内容

本发明的目的在于克服现有技术的缺点与不足，提供一种基于双阶遗传计 算的基因表达数据的双聚类算法。

本发明的目的通过以下的技术方案实现：

一种基于双阶遗传计算的基因表达数据的双聚类算法，包含以下顺序的步 骤：

1)设基因表达数据矩阵为M，行数为m，列数为n，即基因表达数据矩阵 的大小为m×n，将原始的数据矩阵M的每一行减去第k行，得到处理之后的矩 阵M(k),k＝1,2,…,n；

2)对处理之后的矩阵M(k)中除了第k列之外的每一列，使用距离阈值为 cof的层次聚类，得到每一列的双聚类种子，然后将所有得到的双聚类种子全部 放入一个名为Bic_Set的集合；

3)从Bic_Set的集合中选取一个双聚类种子，对未包含其中的行列进行编 码；将未包含的行列作为搜索空间，每个行和列作为一个个体，随机选择N_i行 和N_j列，令N₁＝N_i+N_j，即随机选择N₁个个体，构成了初始化种群P1；将选中的 行和列的位置记为1，没有选中的行和列的位置记为0，则得到种群P1的编码；

4)将初始化的P1种群的N₁个个体(行或列)分别独立的加进双聚类种子 中，得到N₂个已扩大的双聚类，其中N₁＝N₂，每个双聚类作为一个个体，由N₂个 个体构成初始种群P2，然后对每个双聚类进行二进制编码，编码的长度为m+n， 前m位用于行编码，后n位用于列编码，将双聚类中包含的行和列对应的位置 置为1；经过以上步骤就得到种群P2中双聚类的编码；至此，我们就得到了初 始化的种群P1和初始化的种群P2；

5)接着使用适应度函数Fitness1(p)评价种群P1中每个个体的适应度，设变 异概率为m；从N₁个个体中选择(1-m)*N₁个适应度高的个体，将其遗传到下一 代种群中，然后将m*N₁个适应度低的个体进行变异，得到新的m*N₁个体，即 重新随机选取m*N₁个新的行或者列；然后将变异得到的新的个体也加入下一代 种群中，由此得到种群P1中新的N₁个个体，其中适应度函数为 Fitness1(p)＝Bicluster.Msr-Bicluster.Msr(p)，Bicluster.Msr是种群P1中第p个 个体对应产生的种群p2中的双聚类的平均平方残基，Bicluster.Msr(p)是去掉第p 行或者第p列之后的双聚类的平均平方残基；至此，这一代种群P1的遗传进化 完成；

6)然后使用适应度函数Fitness2(Bicluster)评价种群P2中的N₂个个体的适 应度，从中选取适应度高的g个个体遗传到下一代，将种群P2中其余的适应度 低的个体淘汰，其中g<N₂；其中适应度函数为

$\mathrm{Fitness}2\left(\mathrm{Bicluster}\right)=\frac{\mathrm{Bicluster}.\mathrm{Hscore}}{\mathrm{Bicluster}.\mathrm{Volume}},$

式中，Bicluster.Hscore是双聚类的平均平方残基，Bicluster.Volume是双聚 类的大小；

7)然后将下一代种群P1的N₁个体随机的加入到由步骤6)中由种群P2得 到的适应度较高的g个个体中，即将种群P1中的每个个体所对应的行和列分别 独立地加入g个双聚类中，得到N₂个包含较优且已扩大的双聚类个体的下一代 种群P2；

8)之后继续对种群P1使用遗传算法，产生下一代种群P1中的个体，将种 群P1的新一代的N₁个个体随机的加入到由种群P2得到的适应度较高的g个个 体中，又产生了下一代种群P2；不断重复步骤5)、6)、7)，直到达到预先设定 的最大的进化次数或种群P2中的个体大部分相同，最后从种群P2中挑选出最 优的双聚类。

步骤2)中，所述的每个双聚类种子都对应着一个处理任务，对每个处理任 务进行并行化处理。每一个双聚类种子都对应着后续一系列的运算过程，将每 个双聚类种子对应的运算过程作为一个子任务，每个子任务之间是相互独立， 互不影响的，因此我们可以对多个子任务进行并行计算，能够极大地减少运算 时间，提高运算效率。

步骤5)中，所述的使用适应度函数Fitness1(p)来评价种群P1中个体的适 应度，其实就是计算种群P1中第p个个体对种群p2中的对应的双聚类的贡献 程度，通过Fitness1(p)计算得到值越小，说明加入第p行或者第p列使得当前双 聚类的平均平方残基(MSR)值越小，即该行或者列对双聚类质量的影响越好。

步骤7)中，所述的将种群P1的新一代的N₁个个体随机的加入由种群P2得 到的适应度较高的g个个体中，具体通过使用一种轮盘赌规则来实现：计算出g 个个体适应度的总和；然后计算出g个个体相对适应度的大小，即每个个体的 适应度占适应度总和的比率R_i，i＝1,2,…,g；然后将P1中的N₁个个体分别乘以 相对比率R_i，得到种群P1中的个体随机加入到种群P2中g个个体的个数N₁*R_i。

本发明与现有技术相比，具有如下优点和有益效果：

1、本发明利用遗传算法中的二进制编码，对行列进行编码，进而可以对每 个基因在每种条件下的数据值进行搜索，因此搜索范围广，不容易遗漏重要的 生物信息。

2、本发明可解决传统基于遗传计算的双聚类算法只能针对双聚类进行选 择的缺点，通过同时对行列进行优化，可提高搜索效率。

3、基于双阶遗传计算我们能够发现更大的双聚类，即在更小的平均平方残 基值的情况下包含更多的基因和条件的信息。通过该算法，我们发现的双聚类 都是体积比较大，平均平方残基值比较小的矩阵，说明我们发现的双聚类质量 高。

4、本发明所采用的双聚类方法是基因表达数据分析中的一种无监督学习方 法,它在行和列上同时聚类，能够找出在某些样本下参与调控的基因聚类和与某 些基因相关联的样本，解决了传统聚类方法只能在基因表达数据集的基因或条 件方向上进行聚类的问题,克服了其不能发掘数据中局部信息的缺陷。

附图说明

图1为本发明所述的一种基于双阶遗传计算的基因表达数据的双聚类算法 的流程图；

图2为图1所述算法的使用分层聚类的示意图；

图3为图1所述算法的种群P2编码方式的示意图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方 式不限于此。

如图1，一种基于双阶遗传计算的双聚类算法，包括以下顺序的步骤：

1)基因表达数据矩阵为M，行数为m，列数为n，即基因表达数据矩阵的 大小为m×n，将原始的数据矩阵M的每一行减去第k行，得到处理之后的矩阵 M(k),k＝1,2,…,n；

2)对处理之后的矩阵M(k)中除了第k列之外的每一列，如图2所示，对每 一列使用距离阈值为cof＝0.02的分层聚类，得到每一列的双聚类种子，然后将 所有得到的双聚类种子全部放入一个名为Bic_Set的集合；因为每个双聚类种子 都对应着一个处理任务，所以此处可以对每个任务进行并行化处理；

3)从Bic_Set的集合中选取一个双聚类种子，对未包含其中的行列进行编 码；将未包含的行列作为搜索空间，每个行和列作为一个个体，随机选择N_i行 和N_j列，令N₁＝N_i+N_j，即随机选择N₁个个体，构成了初始化种群P1；将选中的 行和列的位置记为1，没有选中的行和列的位置记为0，则得到种群P1的编码；

4)将初始化的P1种群的N₁个个体(行或列)分别独立的加进双聚类种子 中，得到N₂个已扩大的双聚类，其中N₁＝N₂，每个双聚类作为一个个体，由N₂个 个体构成初始种群P2，如图3所示，然后对每个双聚类进行二进制编码，编码 的长度为m+n，前m位用于行编码，后n位用于列编码，将双聚类中包含的行 和列对应的位置置为1；经过以上步骤就得到种群P2中双聚类的编码；至此， 我们就得到了初始化的种群P1和初始化的种群P2；

5)接着使用适应度函数Fitness1(p)评价种群P1中每个个体的适应度，设变 异概率为m；从N₁个个体中选择(1-m)*N₁个适应度高的个体，将其遗传到下一 代种群中，然后将m*N₁个适应度低的个体进行变异，得到新的m*N₁个体，即 重新随机选取m*N₁个新的行或者列；然后将变异得到的新的个体也加入下一代 种群中，经过以上操作我们将得到种群P1中新的N₁个个体，其中适应度函数为 Fitness1(p)＝Bicluster.Msr-Bicluster.Msr(p)，Bicluster.Msr是种群P1中第p个 个体对应产生的种群p2中的双聚类的平均平方残基，Bicluster.Msr(p)是去掉第p 行或者第p列之后的双聚类的平均平方残基；至此，这一代种群P1的遗传进化 完成；

6)然后使用适应度函数Fitness2(Bicluster)评价种群P2中的N₂个个体的适 应度，从中选取适应度高的g个个体遗传到下一代，将种群P2中其余的适应度 低的个体淘汰，其中g<N₂；其中适应度函数为

$\mathrm{Fitness}2\left(\mathrm{Bicluster}\right)=\frac{\mathrm{Bicluster}.\mathrm{Hscore}}{\mathrm{Bicluster}.\mathrm{Volume}},$

式中，Bicluster.Hscore是双聚类的平均平方残基，Bicluster.Volume是双聚 类的大小；

7)然后将下一代种群P1的N₁个体随机的加入到由步骤6)中由种群P2得 到的适应度较高的g个个体中，即将种群P1中的每个个体所对应的行和列分别 独立地加入g个双聚类中，得到N₂个包含较优且已扩大的双聚类个体的下一代 种群P2；

8)之后继续对种群P1使用遗传算法，产生下一代种群P1中的个体，将种 群P1的新一代的N₁个个体随机的加入到由种群P2得到的适应度较高的g个个 体中，又产生了下一代种群P2；不断重复步骤5)、6)、7)，直到达到预先设定 的最大的进化次数或种群P2中的个体大部分相同，最后从种群P2中挑选出最 优的双聚类。

在图1中倒数第二行所述的“种群代数”实际上就是指步骤8)中所述的“种 群进化次数”；图1中倒数第二行所述的“t”实际上是指步骤8)中所述的“预 先设定的最大的进化次数”。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实 施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、 替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。