基于基因表达数据的双聚类算法研究

发布时间：2017-12-13 14:30

  本文关键词：基于基因表达数据的双聚类算法研究

  更多相关文章： 基因表达数据 双聚类算法 趋势一致双聚类 最长公共子序列

【摘要】：基因芯片技术是近年来分子生物学领域的一大技术突破,它可以平行检测数以万计基因的表达水平,从而获得不同条件下基因组水平的基因表达数据。然而面对迅速增长的数据,如何借助有效的计算方法对海量数据进行分析成为了新的挑战。本文主要研究的就是如何针对基因表达数据设计双聚类算法,从而在表达数据中寻找趋势一致双聚类,即那些在特定条件下具有趋势一致表达的基因集。通过对基因表达数据的研究,有助于分析基因的表达调控信息,了解基因之间的相关性,对疾病诊断治疗、药物疗效判断等方面具有十分重要的意义。最早的研究基因表达数据的方法是利用单聚类算法分别对基因或条件进行分析。其结果反映的往往是一组基因在全部条件下,或全部基因在某些条件下表达的相关性。然而在生物体内,参与同一调控功能的仅仅是一部分基因,且它们只在部分条件下具有表达相关性。同时,许多基因通常具有多种调控功能,可能会在不同的条件下表现出不同的功能。因此在基因表达数据的分析中,我们需要的是能够反映部分基因在部分条件下表达相关性的双聚类,同时允许不同的双聚类之间会存在一定程度的覆盖,而这些数据特征都是采用传统的单聚类算法难以获得的。双聚类算法的提出为基因表达数据的分析提供了有效的方法,使得我们可以找到在特定条件下具有一致表达类型的基因集。双聚类算法最初由Morgan等人提出,他们将矩阵分解为值近似相等的子矩阵。随着双聚类算法被应用到基因表达数据的分析中,大量针对不同类型双聚类的算法涌现出来,并对基因表达数据的分析起了重要的作用。趋势一致双聚类是隐藏在基因表达数据中最具有生物意义的一种双聚类类型,目前也有很多算法是针对此类型双聚类设计的。但是由于问题本身的复杂性,如何快速有效地识别数据中的趋势一致双聚类仍然是一大难题。本文中,我们提出了一种新的双聚类算法UniBic,它可以准确地识别矩阵数据中的趋势一致双聚类。算法的设计基于如下发现：在顺序一致的双聚类中,存在一个列的重排列,使得各行元素值在该重排列下是非降序排列的,且识别双聚类的关键就在于准确定位双聚类所在的列。UniBic的设计主要分为以下几步：首先,根据原始矩阵创建数据的索引矩阵,并根据所要寻找的双聚类的显著性信息将索引矩阵分组：随后,将最长公共子序列方法运用到索引矩阵每一分组的行对之间,以定位可以用来进一步扩增双聚类的种子序列；最后,将种子扩增为严格顺序一致的双聚类,并在允许误差存在时将严格顺序一致的双聚类扩增为趋势一致双聚类。索引矩阵的建立将在背景矩阵中寻找趋势一致双聚类的问题转化为在索引矩阵的行对之间寻找最长公共子序列的问题,使得原问题不那么棘手。此外,在处理如基因表达数据等的大规模矩阵数据时,我们通过对数据进行预处理,选择出起调控作用的部分数据进行分析,从而有效地减少了冗余数据及噪音数据对结果造成的影响。我们分别在模拟数据及真实数据上对比了UniBic与其余六种算法的性能。在不同类型的模拟数据上的测试结果表明,当嵌入的双聚类具有一定列数支持时,UniBic的表现明显优于其余所有算法,特别地,UniBic能够有效识别模拟矩阵数据中嵌入的趋势一致双聚类。同时,当模拟数据中嵌入的双聚类之间存在一定覆盖度时,UniBic的表现也优于其它算法。在真实数据的测试中,UniBic得到的结果也是平均GO富集度最高的。但我们的算法仍有不足之处,由于种子是从索引矩阵行对之间的最长公共子序列中寻找的,UniBic在一定程度上会忽略列数较少的窄形双聚类。目前已有算法是专门针对数据中的窄形双聚类设计的,但是此类型的算法不但时间复杂度普遍较高,而且当双聚类列数较多时表现十分不理想。考虑到双聚类算法的复杂性,我们很难设计一种算法来高效地寻找所有类型的双聚类,不过我们提出了一种可行的方法来弥补现有算法的不足,并作为后续的研究课题。文章的最后我们介绍了一个简单的聚类算法Peg,并在梭状芽孢杆菌基因组数据中将其与层次聚类算法进行对比。结果表明我们的算法可以较好地反映基因组的分组状态。UniBic已用C语言实现为开源软件,下载地址为：http://sourceforge.net/projects/unibic/files/?source=navbar.本文所用测试数据及测试结果也可从该地址下载。
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP311.13

【相似文献】

中国期刊全文数据库 前10条

1 周世兵;徐振源;唐旭清;;新的K-均值算法最佳聚类数确定方法[J];计算机工程与应用;2010年16期

2 周世兵;徐振源;唐旭清;;基于近邻传播算法的最佳聚类数确定方法比较研究[J];计算机科学;2011年02期

3 周世兵;徐振源;唐旭清;;一种基于近邻传播算法的最佳聚类数确定方法[J];控制与决策;2011年08期

4 李旭;林伟;温金环;史彩云;;基于图谱理论的图像聚类数的确定及应用[J];工程数学学报;2012年05期

5 秦振涛;杨武年;;一种新的最佳聚类数确定方法[J];电子技术应用;2013年01期

6 宋铭利;高新科;;基于距离的最大聚类数探索算法的探讨[J];矿山机械;2006年09期

7 普运伟;朱明;金炜东;胡来招;;核聚类算法最佳聚类数的自适应确定方法[J];计算机工程;2007年04期

8 杨欣斌,孙京诰,黄道;一种进化聚类学习新方法[J];计算机工程与应用;2003年15期

9 田彦山;;基于山峰聚类的聚类上限确定方法[J];江西师范大学学报(自然科学版);2007年02期

10 褚娜;马利庄;王彦;;聚类趋势问题的研究综述[J];计算机应用研究;2009年03期

中国重要会议论文全文数据库 前9条

1 高翠芳;吴小俊;;基于二阶差分的聚类数自动确定方法[A];江苏省系统工程学会第十一届学术年会论文集[C];2009年

2 刘洋;江志纲;丁增喜;王大玲;鲍玉斌;于戈;;一种基于图的聚类算法GB-Cluster[A];第十九届全国数据库学术会议论文集（技术报告篇）[C];2002年

3 李浪波;傅彦;刘红;;基于范例推理的网格和密度聚类算法[A];第二十二届中国数据库学术会议论文集（技术报告篇）[C];2005年

4 娄冬梅;陈明;朱有娜;;一种基于密度的无参数聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

5 魏昕路;洪志令;姜青山;;一种基于样本缩减策略的新窗口式聚类算法[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

6 程尊平;周鼎;王晨;周皓峰;汪卫;施伯乐;;SDPHC——基于密度的分割和分层的自校聚类算法[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年

7 张晓峰;王丽珍;陆叶;;一种基于属性加权的不确定K-means聚类算法[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

8 蔡军;袁华鹏;陈金海;施伯乐;;一种基于相似性分析的聚类新算法:PDS算法[A];第十八届全国数据库学术会议论文集（研究报告篇）[C];2001年

9 胡仲义;郭超;王永炎;刘胜航;王宏安;;基于时间衰减和特征变量的数据流聚类算法[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

中国博士学位论文全文数据库 前10条

1 王振佳;基于基因表达数据的双聚类算法研究[D];山东大学;2016年

2 胡雅婷;可能性聚类方法研究及应用[D];吉林大学;2012年

3 王纵虎;聚类分析优化关键技术研究[D];西安电子科技大学;2012年

4 周世兵;聚类分析中的最佳聚类数确定方法研究及应用[D];江南大学;2011年

5 杨燕;基于计算智能的聚类组合算法研究[D];西南交通大学;2006年

6 冯永;基于计算智能的聚类技术及其应用研究[D];重庆大学;2006年

7 刘晨;高伸缩性聚类分析方法研究[D];哈尔滨工程大学;2013年

8 王强;局部叠加基因表达模式聚类分析方法研究[D];哈尔滨工业大学;2012年

9 姜磊;混合演化聚类算法研究及其应用[D];武汉大学;2012年

10 尹学松;半监督聚类分析策略设计及其拓展性研究[D];南京航空航天大学;2009年

中国硕士学位论文全文数据库 前10条

1 魏建东;K-means初始化算法研究[D];南京理工大学;2015年

2 张依;基于MapReduce的k-means聚类算法并行化研究[D];中央民族大学;2015年

3 刘婵;蚁群与K均值聚类算法融合研究及其在用户分群中的应用[D];西南科技大学;2015年

4 朱琪;基于减法聚类的混合算法研究[D];湖南科技大学;2015年

5 韩伟森;聚类集成研究与应用[D];贵州大学;2015年

6 谭浩;K-Means算法改进及其在森林健康评价中的应用[D];中南林业科技大学;2015年

7 严巍;以KPCA为核心的FCM算法改进[D];成都理工大学;2015年

8 汪娟;基于权重设计的聚类集成算法研究[D];重庆大学;2015年

9 牛品菽;基于图模型的高效聚类算法研究[D];北京交通大学;2016年

10 蔡洪山;大数据分析中的聚类算法研究[D];安徽理工大学;2016年

，

本文编号：1285505