基于改进关联规则和遗传算法的基因表达网络构建方法

基于改进关联规则和遗传算法的基因表达

网络构建方法1

袁祚涌，饶妮妮

电子科技大学生命科学与技术学院，成都 (610054)

摘 要：本文针对基因表达网络的构建问题，首先改进关联规则算法，设计了遗传算法中的编译码方法、适应度函数和遗传操作，引入选优算子，以提高遗传算法的搜索效率。接着，将改进的关联规则算法和遗传算法相结合，形成了一种新的基因表达网络构建方法。用酵母基因表达数据进行仿真试验，发现了具有重要生物意义的规则，以此构建出了基因表达网络，并作了生物意释。理论分析和仿真实验均证实了新方法的可行性、有效性以及实际应用价值。

关键词：关联规则，支持度，信任度，遗传算法，基因表达网络

1. 引言

重构转录水平上的基因表达网络可以帮助我们理解复杂的分子或细胞过程机理，是当前国际上的一项重点和难点课题。就转录水平上基因表达网络的构建问题，国内外学者均已经开展了大量相关研究工作。 Lee（2002）和Bar Joseph（2003）等用基于实验的基因组定位分析方法，构建了转录因子启动子结合网络，以此推导出转录网络[1-2]。然而，定位分析实验方法只适用于特定的实验条件，在其它实验条件下，该方法可能失效。迄今为止，各种统计数据挖掘工具已经用于发现基因表达网络。如Somogyi、 Liang 和Chen 和D’haeseleer的差分方程方法[6]，Friedman 和YooD’haeseleer提出的逆工程方法[3-5]，

采用的贝叶斯网络法[7-8]，以及离散布尔网络模型[9-11]和线性规划[12-13]等。这些方法在计算上很复杂，需要依赖于非常贪婪的计算策略。为了避免计算复杂性问题，Pilpel、Wang、Segal和Beer等把基因表达数据、DNA序列和功能注释整合成一个可以理解的模型，以构建基因表达转录网络[14-16]。此外，Xing等利用基因表达数据、启动子序列和转录因子结合位点数据来构建转录网络[17]。这种方法需要假设数据满足正态分布，而这种假设还没有得到证实，导致所得结果的可信度不高。因此，针对具体的生物学事件，发展更加适用的基因网络构建方法是一项十分重要的研究工作。

关联规则挖掘[18]（Association Rules Mining）是数据挖掘（Data Mining）领域的一项技术。近年来，该技术在生物医学领域得到应用，如Chad Creighton 和Pedro Carmona-Saez用此方法挖掘基因表达数据[19-20]，Exarchos挖掘心电图和脑电图的记录数据[21-22]，Artamonova挖掘蛋白质序列注释数据[23]。除此以外，还有学者将关联规则用于分析蛋白质相互作用关系、分析骨骼肌中蛋白激酶的关系以及心脏病的预测等。这些研究发现了许多有意义的规则，并作出了相应的解释。然而，现有主要关联规则挖掘算法利用了“支持度和信任度”框架，而算法对二者的取值很敏感，取值太大和太小的结果相差甚远，可能产生具有高信任度的无关规则，但却没有进一步考虑规则的优化问题，因此，算法执行效率不够高。

遗传算法[24]（Genetic Algorithm，GA）是一种智能优化算法，它具有高度并行、随机和自适应的特点，一般来说能够找到问题的最优解。现已被广泛应用于组合优化、机器学习、

1

本课题得到国家自然科学基金面上项目（No. 60571047）、四川省学术与技术带头人培养基金（No. 901008）、四川省应用基础项目（No. J13 - 075）和电子科技大学中青年人才培养计划 (No. 601016)的资助。

-1-

http://www.paper.edu.cn

信号处理和自适应控制等领域。在生物信息学领域也有较多应用，如肿瘤分类和生物标识发现[25]、基因表达模式发现[26]、元件模块的识别[27]、真核基因启动子的识别[28]和基因网络的动力学模型构造[29]等。这些应用表明，在不同的应用场合，均需要结合具体问题设计遗传算法中的编译码方法、适应度函数和遗传操作等，以保障算法的收敛性和收敛速度，寻找到期望的最优解。

本文尝试将关联规则和遗传算法两种技术结合起来形成一种推断基因表达网络的新方法。文中第二部分针对基因表达网络的构建问题，对两种算法进行了改进和设计；第三部分描述了基因表达网络的构建方法；第四部分用计算机实验证实算法的可行性和有效性，并对实验结果进行分析和生物意释；最后，给出了本工作得到的结论。

2. 算法设计

2.1 改进关联规则算法

经典的关联规则算法Apriori算法是Agrawal等人于1993年首先提出，并用于挖掘顾客交易数据库中项集间的关联规则问题。可把关联规则挖掘分成两个阶段：一是基于最小支持度获取频繁项集；二是在频繁项集上基于最小信任度产生关联规则，其中，第一步最重要，是本文讨论的重点。

，其中ik (k = 1,2,…,m)是项（item）。在不同的应用场设I = {i1,i2,…,im}是项集（itemset）

合，可以赋予项一定的物理意义，如购物篮中的物品或保险公司的顾客。设交易数据库D是事务的集合，其中每个事务T是项集，使得T ⊆ I。设A是一个项集，且A ⊆T。关联规则是如下形式的逻辑蕴涵式：A ⇒ B，A ⊂ I, B ⊂ I，且A∩B = Φ。关联规则具有两个重要参数：支持度（support）和信任度（confidence），如表1所示。支持度是对关联规则的重要性或适用性的衡量，信任度是对关联规则的准确度的衡量。支持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大关联规则越重要。有些关联规则虽然信任度很高，但支持度却很低，说明该关联规则实用的机会很小，不是很重要。

表1 关联规则的两个参数

名称

支持度（support） 信任度（confidence）

描述

A和B两个项集在事务集D中同时出现的概率 在出现项集A的事务集D中，项集B也同时出现的概率

公式 P(A∪B) P(B | A)

支持度大于或等于最小支持度的项集称为频繁项集（frequent itemset），也可称为大项集（large itemset）。同时满足最小支持度（minsupp）和最小信任度（minconf）的规则称为强规则。给定一个事务集D，挖掘关联规则问题就是产生支持度和信任度分别大于或等于用户给定的最小支持度和最小信任度的关联规则，也就是产生强规则的问题。

经典的关联规则算法首先找出频繁1-项集，记为L1；然后利用L1来挖掘L2，即频繁２-项集；不断如此循环下去直到无法发现更多的频繁K-项集为止。每挖掘一层Lk 就需要扫描整个数据库一遍。为提高搜索效率，Apriori算法利用了一个重要性质来帮助有效缩小频繁项集的搜索空间，即一个频繁项集的任何一个非空子集都应该是频繁的，通常称为剪枝技术。换言之，如果某项集I中存在一个不是频繁项集的子集，那么这个项集I也不是频繁的，因而可以从候选项集中删除，不用计算它的支持度。表2给出了交易数据的格式。

-2-

http://www.paper.edu.cn

表2交易数据库的记录数据

交易号（TID）

T100

项集（itemset）

I1, I2, I5

T200 I2, I4 T400 T500

I1, I2, I4, I6 I1, I3, I5

T300 I2, I3

为了生成所有频繁项集，使用了递推的方法，其核心思想简要描述如下： (1) L1 = {frequent 1-itemsets}; (2) for (k = 2; Lk-1 ≠ Φ; k++) do begin (3) Ck = apriori-gen(Lk-1); //新的候选集

(4) for all transactions t ∈ D do begin (5) Ct = subset(Ck,t); //事务t中包含的候选集 (6) for all candidates c ∈ Ct do

(7) c.count++; (8) end

(9) Lk = {c ∈ Ck | c.count ≥ minsupp} (10) end

(11) Answer = ∪kLk;

在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有Ck中的项集是用来产生频繁项一个项不同的属于Lk-1的频繁项集做一个(k-2)连接来产生的。

集的候选集，最后的频繁项集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，如果频繁项集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。

针对以上问题，本文提出从三个方面改进经典的关联规则算法：

(1) 在筛选频繁项集时，除了最小支持度的外，再增加一个筛选条件，比如指定频繁项集的最大长度（即项集中项的最大数目）；

(2) 采用事务压缩技术。其基本原理是当一个事务不包含长度为k的频繁项集时，则必然不包含长度为k+1的频繁项集，从而可以将这些事务移去或者作一个标记，这样在下一遍的扫描中就可以减少扫描的事务集个数；

(3) 将交易数据库中的记录数据用表或文件的形式存储起来，扫描时将数据从文件读入内存，避免了频繁访问数据库，这样大大提高了扫描速度。

2.2 遗传算法设计

遗传算法是模拟生物进化的自然选择和遗传机制的一种寻优算法。从一组随机产生的初始群体（Population）出发，经过选择、交叉和变异等进化过程，形成一代更适应环境的新的群体，其中的个体叫染色体（Chromosome），它是一串字符，例如一个二进制字符串“1111001010011”。这些染色体在迭代过程中不断地进化遗传，每一代中染色体的好坏用适应度（Fitness）来衡量，控制群体向更好的方向发展，因此适应度函数的选取非常重要。经

-3-

http://www.paper.edu.cn

过若干代进化之后，算法最后收敛于最好的染色体，它可能就是问题的最优解或次优解。

标准遗传算法（Standard Genetic Algorithm，SGA）的工作过程如下： (1) 对所求问题进行编码，通常是二进制编码；

(2) 随机产生初始群体X(0) = (x1, x2, … , xn)，n是群体规模；

适应度表示了该个体的性能好坏； (3) 对当前群体X(t)中每个个体xi计算其适应度F(xi)，(4) 运用选择算子产生中间代Xm(t)；

(5) 对Xm(t)运用交叉和变异算子，产生新一代群体X(t+1)。以上算子操作的目的在于扩展有限个体的覆盖面，体现全局搜索的思想；

(6) t = t +1；如果不满足终止条件继续(3)～(6)。

针对标准遗传算法与关联规则算法结合用于构建基因表达网络的具体问题，本文提出了设计和改进标准遗传算法中编译码、适应度函数和遗传操作的新思想。 2.2.1 编译码设计

基因表达数据中一个事务集可能包含几百或几千个基因，若采用二进制编码，则编码串可能很长，这将影响遗传算法的搜索效率。本文提出采用十进制编码方法，编码对象是关联规则。例如，规则｛HXT3｝⇒｛BSC1,HXT4,HXT7,PRM7｝，假设这五个基因的编号分别是35、1568、1203、247和4，基因的总数为6000个（设每个基因的编码长度为4，后同），那么这条规则的编码为：“00351568120302470004”，不足4位的在前面添0，这样大大减少了编码串的长度。译码很简单，每次取四位就可得到基因的编号，根据编号就能找到对应的基因。

2.2.2 适应度函数设计

适应度是遗传算法中评价个体性能好坏的唯一标准，因而它的选取至关重要，直接影响到算法的收敛速度，即最终能否找到最优解。根据关联规则的两个参数：支持度和信任度，构造出的适应度函数为：

F(r)=aS(r)+bC(r) (1)

其中，r代表规则变量，Ｓ(r)代表规则的支持度，C(r)代表规则的信任度，a和b是权重，取值范围是0＜a≤1，0＜b≤1。通过调节a和b的值，可以改变适应度是偏重于支持度还是信任度，从而灵活地控制进化过程，使其沿着用户期望的方向进行。 2.2.3 遗传操作设计

选择（Selection），交叉（Crossover），变异（Mutation）构成标准遗传算法的三个基本操作算子。

(1) 选择算子：本文采用轮盘赌的方法，将个体适应度与总适应度（群体中所有个体适应度之和）的比值作为选择概率Ps，每一轮选择产生一个[0~1]的随机数，用该随机数做为选择指针来确定被选个体。显然，个体适应度越大被选中的机会就越大，体现了自然界“优胜劣汰，适者生存”的进化规律。

(2) 交叉算子：本文采用单点交叉，根据交叉概率Pc从群体中随机选择成对的个体，随机产生交叉点，交换两个父代个体交叉点之后的部分，形成两个新个体。这里交叉点必须是4的倍数，因为基因的编码长度为4，基因是最小的功能单位，所以交叉位置的选取不能在基因的内部。交叉操作能产生新的个体但是不会破坏基因，因而保证了基因的完整性。表3是单点交叉的一个实例。

-4-

http://www.paper.edu.cn

表3 交叉操作（设交叉点是8）

父代个体

子代个体

00351568120302470004 00351568512034120008 21000106512034120008 21000106120302470004

(3) 变异算子：本文采用随机产生变异位的策略。由于采用十进制编码，因此对产生的变异位不能作翻转操作，而是在[0~9]之间随机产生一个整数去替换变异位的值，从而改变原来的基因。例如：个体“00351568120302470004”，变异位是13，产生的随机整数是5，则变异后的个体为：“00351568120352470004”。变异操作能产生新的基因，使遗传算法具有局部的随机搜索能力，可维持群体的多样性，其取值通常都很小，如0.01，视具体问题而定。 2.2.4选优算子的引入

为了提高遗传算法的搜索效率，使进化向更优的方向进行，本文提出增设选优算子操作，即把经过选择、交叉和变异后的群体做一次选优操作，把当前群体中适应度高于上一代群体平均适应度的个体优选出来，并从初始群体中选出适应度较好的个体补充到其中，形成新一代群体。

3. 基因表达网络构建新方法

新方法将改进关联规则和遗传算法相结合，首先运用改进关联规则挖掘基因表达数据，再运用遗传算法形成优良规则，最后根据所得基因与基因之间的关联关系，构建出具有生物意义的基因表达网络。

3.1 基因表达数据转化为交易数据

基因芯片表达数据通常是用一个基因表达矩阵来表示，如表4所示。其中，行代表基因，列代表样本或者时间序列，表中的元素代表某一个基因在某样本或某时间点上的表达水平。假设表达量大于等于1.0认为是上调的，表达量小于等于-1.0认为是下调的，表达量在-1.0和1.0之间认为既不上调也不下调，那么基因表达矩阵可以转化为表5。通常人们感兴趣的是那些上调或下调的基因，因此形成两个事务集，分别如表6和表7所示。

表4 基因表达矩阵 表5 转化后的基因表达矩阵

T1 T2T3 T4 G1 -0.6 2.3 3.0 4.5 G2 -1.5 -1.4 1.8 2.6 G3 1.2 1.1 -0.9 -1.7 G4 -0.8 -3.0 -1.3 1.9 G5 1.0 -0.2 1.2 -1.6 T1 T2 T3 T4 G1 up up up G2downdownup up G3up up down G4 downdownup G5up up down

-5-

http://www.paper.edu.cn

表6 上调基因的事务集 表7 下调基因的事务集

交易ID 项集（itemset）

交易ID 项集（itemset）

T1 G3, G5 T2 G1, G3 T3 T4

G1, G2, G5 G1, G2, G4

T1 G2 T2 G2, G4 T3 G4 T4 G3, G5

3.2 挖掘交易数据形成优良规则

根据用户指定的最小支持度和最小信任度挖掘交易数据，产生出大量的关联规则。关联规则能描述一个基因的表达如何与另一组基因的表达相关联，如果存在这样一个关联，可以很容易地推断这些基因同属于某种类型的基因网络。例如某个规则为：{gene A} ⇒ {gene B, gene C, gene D}，从这条规则可以推断A，B，C，D四个基因可能同属于某个基因网络，而且基因Ａ可能起作用，控制其它三个基因的表达水平。把这些大量的关联规则作为初始群体，应用改进遗传算法进行优化，筛选出其中优良的规则。在这些优良的规则中，蕴涵了大量具有意义的生物信息和表达模式，为进一步研究基因的功能和相互关系提供了线索和帮助。

3.3 构建基因表达网络

在同一条规则中出现的基因存在内在关联性[19]，基于这一观点，我们把挖掘出的关联规则作进一步地分析和处理，以发现它们中存在的内在联系，构建出基因表达网络。我们把优良规则中的基因作为结点，把规则左边的基因与规则右边与其有关联的每个基因用带箭头的连线联系起来，箭头方向从左边基因指向右边基因，结果则构成一个能够反映基因之间关系的有向图，即基因表达网络。例如，从模拟基因表达数据中挖掘出来的三条规则：(1) {gene A} ⇒ {gene B, gene C, gene D}，(2) {gene E} ⇒ {gene B, gene C}，(3) {gene D} ⇒ {gene C}，以此构建的有向图如图1所示，反映了这三条规则之间的内在联系。

图1 三条规则构建的具有关系的有向图

4. 实验与结果分析

我们选用了经典的酵母基因表达数据[30]作为测试数据来证实新方法的有效性。该数据包含有6221个基因, 我们针对实验样本Cell-cycle Alpha Factor进行了仿真实验。

将表达数据转化为交易数据时，实验中采用1.0作为筛选阈值，这是因为表达值是以2

-6-

http://www.paper.edu.cn

为底的对数值，上调2倍值为1，下调2倍值为-1，两个值分别位于坐标原点的两侧，呈对称关系，便于分析作图。再者文献[19-20]采用了这个阈值，被证明是比较有效的。用新方法分别对上述两组数据进行挖掘，得到很多优良的关联规则。

表8列出了从Cell-cycle Alpha Factor数据中挖掘的优良规则，图2是由这些规则构建的基因表达网络。

表8 Cell-cycle Alpha Factor中发现的优良关联规则（其中几乎所有基因上调）

关联规则

支持度

信任度 1 1

1 1 1 1 1 1 1

1 {YAR010C}⇒{YIL080W YIL082W YMR051C YML045W 0.611111

YCL020W YFL-TYB}

0.722222 0.722222 3 {YBR012W-A}⇒{YIL080W YIL082W}

0.722222 4 {YBR296C}⇒{YIL080W YIL082W YIL017W}

5 {YCL019W}⇒{YIL080W YIL082W YIL017W YMR051C 0.666667

0.611111 YML045W YCL020W YFL-TYB}

6 {YHL047C}⇒{YIL080W YIL082W YOR382W YMR058W 0.611111

0.611111

YEL065W YLR136C}

0.611111

7 {YHR145C}⇒{YIL082W YMR051C YIL017W YFL-TYB YML045W}

2 {YBL101W-A}⇒{YIL080W YIL082W YMR051C YML045W} 8 {YHR145C}⇒{YIL080W YIL082W YIL017W} 9 {YIL060W}⇒{YIL080W YIL082W}

10 {YJR026W}⇒{YIL080W YIL082W YMR051C YML045W 0.722222

0.666667 YFL-TYB}

11 {YJR028W}⇒{YIL080W YIL082W YMR051C YML045W 0.611111

0.611111 YFL-TYB}

0.611111 12 {YJR109C}⇒{YIL080W YIL082W YMR051C}

0.611111 13 {YJR109C}⇒{YMR051C YML045W}

0.611111

14 {YML040W}⇒{YIL082W YMR051C}

0.611111

15 {YML040W}⇒{YML045W YMR051C}

0.777778

16 {YML040W}⇒{YIL082W YML045W}

0.611111

17 {YML040W}⇒{YIL080W YIL082W}

0.611111

18 {YML045W}⇒{YIL080W YIL082W YMR051C YEL065W}

0.777778

19 {YMR046C}⇒{YIL082W YMR051C YIL017W YML045W

0.611111

YFL-TYB}

20 {YMR046C}⇒{YIL080W YIL082W YIL017W}

21 {YMR051C}⇒{YIL080W YIL082W YJR026W YML045W}

22 {YOL158C}⇒{YIL080W YIL082W YLR136C YEL065W YOR382W YMR058W}

从表8中可知，规则1中信任度为1表示基因YAR010C上调（即过表达）时，规则右边的基因100%上调；支持度为0.611111表示该规则中的所有基因在实验中同时上调的可能性是61%，表8中其它规则可类似地作出解释。通过分析我们发现，一个基因可以同时出现在几条规则中，如基因YIL080W YIL082W YML040W YML045W YMR051W等，这与生

-7-

0.928571

1 1 1 1 1 1 1

0.875

1 1

0.875

1

http://www.paper.edu.cn

物系统中细胞、组织和器官的功能多样性吻合，而传统聚类方法一个基因只能分到某一类，这与基因功能的多样性是相违背的。而且，仔细研究还发现，某些基因如象YIL080W和YIL082W，几乎出现在所有规则中，说明它们非常重要，可以推测这些基因可能起全局作用，参与多个层次的基因网络，或者具有多种功能。

从图2中可以看到，有四个基因（蓝色区域）YIL080W YIL082W YML045W YMR051C跟其它许多基因都有关联，说明它们扮演着重要角色，通过查询酵母基因组数据库[31]（SGD），发现它们都有很多功能，除了YIL082W尚未注释外，其它三个基因都有RNA结合、蛋白质结合功能。其中YIL080W 和YML045W还有DNA介导的DNA聚合酶活性、RNA介导的DNA聚合酶活性、肽酶活性、核糖核酸酶活性等功能。这四个基因还是反转录转座子核衣壳的重要组成成分。与YIL080W相关联的15个基因中就有9个基因（YMR051C YCL019W YAL010C YMR046C YML040W YJR028W YBL101W-A YBR012W-A YJR026W）的功能注释完全相同，这充分说明这些基因是一组共基因，受相同的转录因子。经查询YEASTRACT数据库[32]证实，这些基因大多数受Gcr1p和Yap1p。有2个基因YHL047C和YOL158C与含铁细胞运输有关，另外2个基因YBR296C和YJR109C分别参与磷酸盐运输和精氨酸合成，还有2个基因（YIL060W YHR145C）没有注释。与YHL047C关联的一组基因（YOR382W YLR136C YMR058W YEL065W YIL080W YIL082W）大多数都参与铁离子运输活动或维持铁离子动态平衡，它们都受转录因子Aft2p和Rcs1p。

YIL060W

YHL047C

YOL158C

YCL019W

YIL082W

YOR382W YML045W

YLR136C YCL020W

YMR058W YBR296C

YAR010C YMR051C

YMR046C YIL080W

YHR145C YJR026W

YJR109C YBR012W-A

YML040W

YEL065W

YJR028W

YBL101W-A

图2 Cell-cycle Alpha Factor数据构建的基因表达网络

-8-

http://www.paper.edu.cn

5. 结论

本文针对基因表达网络的构建问题，从三个方面改进了关联规则算法，（1）增加频繁集筛选条件以减少项的数目；（2）采用事务压缩以减少事务集个数；（3）采取存储技术以提高扫描速度。设计了标准遗传算法中的编译码方法、适应度函数和遗传操作，并引入一种新的选优算子，提高遗传算法的搜索效率。将改进后的关联规则和遗传算法相结合，形成了一种构建基因表达网络的新方法。将新方法运用于酵母基因表达数据的实验样本Alpha Factor，构建出了具有重要生物意义的基因表达网络，证实了新方法的有效性和可行性。通过对Alpha Factor实验样本数据构建的基因表达网络进行分析，发现了各自的生物功能、细胞组分以及关系，并预测了一些未知基因的功能。新方法可以应用到其他模式生物的基因表达数据，构建其基因表达网络，也适用于蛋白质芯片和组织芯片等生物芯片的数据挖掘中，具有很好的应用前景。

致谢

本文研究工作得到国家自然科学基金面上项目（No. 60571047）、四川省学术与技术带头人培养基金（No. 901008）、四川省应用基础项目（No. J13 - 075）和电子科技大学中青年人才培养计划 (No. 601016)支持，在此表示感谢。

参考文献

[1] Lee T I, et al. Transcriptional regulatory networks in Saccharomyces cerevisiae[J]. Science, 2002, 298: 799-804

[2] Bar-Joseph Z, et al. Computational discovery of gene modules and regulatory networks[J]. Nat. Biotechnol., 2003, 21: 1337-1342

[3] Somogyi R, et al. The gene expression matrix: towards the extraction of genetic network architectures[J]. Proceedings of Second World Congress of Nonlinear Analysts, 1997, 30: 1815-1824

[4] Liang S, et al. REVEAL: a general reverse engineering algorithm for inference of genetic network architectures[J]. Proc. Pac. Symp. Biocomput. 1998, 3: 18-29

[5] D’Haeseleer P, et al. Genetic network inference: from co-expression clustering to reverse engineering[J]. Bioinformatics, 2000, 16: 707-726

[6] Chen T, et al. Modeling gene expression with differential equations[J]. Proc. Pac. Symp. Biocomput. 2004, 4: 29-40

[7] Friedman N, et al. Using bayesian networks to analyze expression data[J]. J. Comput. Biol. 2000, 7: 601-620 [8] Yoo C, et al. Discovery of causal relationships in a gene-regulation pathway from a mixture of experimental and observational DNA microarray data[J]. Proc. Pac. Symp. Biocomput. 2002, 7: 498-509

[9] Kauffman S, Peterson C, Samuelsson B, et al. Random Boolean network models and the yeast transcriptional network[J]. Proc Natl Acad Sci USA, 2003, 100(25): 14796-14799

[10] Shmulevich I, Dougherty ER, Kim S, et al. Probabilistic Boolean Networks: a rule-based uncertainty model for gene regulatory networks[J]. Bioinformatics, 2002, 18(2): 261-274

[11] Akutsu T, Miyano S, Kuhara S. Identification of genetic networks from a small number of gene expression patterns under the Boolean network model[J]. Pac Symp Biocomput, 1999, 17-28

[12] Yong Wang, Trupti Joshi, Dong Xu, et al. Supervised Inference of Gene Regulatory Networks by Linear Programming[J]. D S Huang, K Li and G W Irwin (Eds.): ICIC2006, LNBI 4115, pp. 551-561, Springer-Verlag, 2006

[13] Dasika MS, Gupta A, Maranas CD. A mixed integer linear programming (MILP) framework for inferring time delay in gene regulatory networks[J]. Pac Symp Biocomput, 2004, 474-485

[14] Pilpel Y, Sudarsanam P, Church G. Identifying regulatory networks by combinatorial analysis of promoter

-9-

http://www.paper.edu.cn

elements[J]. Nat. Genet, 2001, 29: 153-159

[15] Wang W et al. A systematic approach to reconstructing transcription networks in Saccharomyces cerevisiae[J]. PNAS, 2002, 99: 163-168

[16] Segal E, et al. Genome-wide discovery of transcriptional modules from DNA sequence and gene expression[J]. Bioinformatics, 2003, 19: 273-282

[17] Xing B, van der Laan M J. A statistical method for constructing transcriptional regulatory networks using gene expression and sequence data[J]. J. Comput. Biol., 2005, 12: 229-246

[18] 范明, 孟小峰. 数据挖掘: 概念与技术[M]. 北京: 机械工业出版社, 2001

[19] Chad Creighton, Samir Hanash. Mining gene expression databases for association rules[J]. Bioinformatics, 2003, 19(1): 79-86

[20] Pedro Carmona-Saez, Monica Chagoyen, Andres Rodriguez, et al. Integrated analysis of gene expression by association rules discovery[J]. BMC Bioinformatics, 2006, 7(54): 1-16

[21] Exarchos TP, Papaloukas C, Fotiadis DI, et al. An association rule mining-based methodology for automated detection of ischemic ECG beats[J]. IEEE Trans Biomed Eng. 2006, 53(8): 1531-1540

[22] Exarchos TP, Tzallas AT, Fotiadis DI, et al. EEG transient event detection and classification using association rules. IEEE Trans Inf Technol Biomed[J]. 2006, 10(3): 451- 457

[23] Artamonova II, Frishman G, Gelfand MS, et al. Mining sequence annotation databanks for association patterns[J]. Bioinformatics. 2005, 21(3): 49-57

[24] 王小平, 曹立明. 遗传算法——理论、应用与软件实现[M]. 西安: 西安交通大学出版社, 2002

[25] Liu JJ, Cutler G, Li W, et al. Multiclass cancer classification and biomarker discovery using GA-based algorithms[J]. Bioinformatics. 2005, 21(11): 2691-2697

[26] Tsai HK, Yang JM, Tsai YF, et al. An evolutionary approach for gene expression patterns[J]. IEEE Trans Inf Technol Biomed. 2004, 8(2): 69-78

[27] Aerts S, Van Loo P, Moreau Y, et al. A genetic algorithm for the detection of new cis-regulatory modules in sets of coregulated genes[J]. Bioinformatics. 2004, 20(12): 1974-1976

[28] Levitsky VG, Katokhin AV. Recognition of eukaryotic promoters using a genetic algorithm based on iterative discriminant analysis[J]. In Silico Biol. 2003, 3(1-2): 81-87

[29] Kikuchi S, Tominaga D, Arita M, et al. Dynamic modeling of genetic networks using genetic algorithm and S-system[J]. Bioinformatics. 2003, 19(5): 3-650

[30] Michael Eisen. Microarray and Related Data for Analyses. http://rana.lbl.gov/EisenData.htm [31] Saccharomyces Genome Database. http://www.yeastgenome.org [32] YEASTRACT. http://www.yeastract.com/index.php

Constructing Gene Expression Regulation Networks Based on Improved Association Rules and Genetic Algorithm

Yuan Zuoyong, Rao Nini

School of Life Science and Technology, UEST of China, Chengdu ( 610054)

Abstract

Based on the construction of gene expression regulation networks in this paper, association rules was firstly improved. The coding/decoding approaches, fitness function and genetic manipulation in genetic algorithm are designed. The optimum selection operator was adopted to improve the searching efficiency of genetic algorithm.Then, the improved association rule algorithm and genetic algorithm were combined to establish a novel approach for constructing gene expression regulatory networks. Finally, the simulation experiments for Yeast gene expression data showed that the gene expression regulatory networks with important biological meanings can be constructed according to the discoverable association rules. The feasibility, effectiveness and practical application values for the novel approach were verified.

Keywords: association rules; support; confidence; genetic algorithm; gene expression regulation networks

-10-