样本断点距离问题的算法与复杂性研究

发布时间：2017-05-27 08:19

  本文关键词：样本断点距离问题的算法与复杂性研究，由笔耕文化传播整理发布。

【摘要】：随着生物技术的发展和计算机科技的进步,生物信息学这个生物和计算机的交叉学科越来越引起人们的注意。生物信息学可以理解成计算机技术在生物上的应用。比较基因组学是生物信息学中的一个重要研究领域。自从九十年代末期,比较基因组学开始逐步兴起,迄今已经走过将近二十年的历程。比较基因组学传统的研究假设是两条基因组不包含重复基因,这种假设在部分病毒和线粒体的基因组中是成立的,但是对于哺乳动物和植物等,这种假设是不满足的。据估计人类的基因组中有15%的基因是含有重复的[49]。样本断点距离问题的研究就是在基因组包含重复的假设下进行的。寻找两条基因组之间的保留基因集合是基因组比较中的一个基本问题。在基因组中以相同顺序保存的一组基因暗示它们参与相同的生物过程。为了寻找基因组中保留基因集合,人们提出许多相似性度量,例如,断点数目,邻接数目,保留区间数目和公共区间数目。当基因组不包含重复基因时,所有这些距离都能很好定义。然而,基因复制是基因组进化的主要驱动力之一,并且频繁发生(Dennis等,2012)。当复制发生时,一个基因可能出现在一条基因组中的几个不同地方。样本断点距离问题是受寻找两条基因组之间保留基因集合启发提出的一个问题。它询问寻找两条基因组各自的样本,以满足样本之间的断点距离最小。如果一条基因组没有重复基因(称为平凡基因组)并且另一条基因组的每个基因至多出现两次,它被称为(1,2)-样本断点距离问题,简称为EBD(1,2)。虽然EBD(1,2),作为最基本的样本断点距离问题,已知为APX-Hard多年,但在算法设计方面却做得很少。事实上,EBD(1,2)是否存在固定参数算法直到现在都是未知的。Zhu(2009)指出如果参数是样本断点距离,EBD(2,2)不存在任何固定参数算法[34]。这让EBD(1,2)是否存在基于某个参数的固定参数算法变得更加有趣。针对EBD(1,2)的固定参数算法,本文重点进行了以下研究工作：(1)我们利用非平凡基因组的跨度(span),记为s,作为参数,设计EBD(1,2)的第一个固定参数算法,其中引入基因组的跨度(span)这个概念来表示基因组中同一基因家族的两个基因横跨的最多基因数目。这取决于一个实际观察,这个观察是在一条基因组中同一基因家族的两个基因通常被少量基因所分隔(Shi等,2010)[31]。对于一个每条基因组包含n个基因家族的EBD(1,2)实例,我们的算法可以在O(4Sn2)时间内和O(4Sn)空间内运行。这在之前是未见的。(2)我们用C++语言实现了上述算法。在随机产生数据上的仿真表明,当基因组的跨度为10,我们的算法总是可以在1000秒内处理包含5000个基因家族的基因组,并且当基因组的跨度为15,我们的算法可以在1600秒内处理包含1000个基因家族的基因组。我们算法的软件包可以在如下网址获取：http://www.cs.sdu.edu.cn/dmzhu/exemplar-distance/software.html基于串联质谱的肽从头测序问题是本文作者的早期研究问题。基于串联质谱的肽从头测序问题是蛋白质组学领域中蛋白质识别最常用的方法之一,它在没有蛋白质数据库辅助的情况下,直接由未知肽P的串联质谱识别出其氨基酸序列。肽从头测序一般将未知肽P的串联质谱转换为一个质谱图G,通过在图G中寻找合适路径的方法来识别出未知肽P的氨基酸序列。图G中的一条路径代表一条可能的肽,我们希望找出与未知肽P尽可能相似的一条或多条肽。在质谱图G的构造过程中,由于不知道串联质谱中的每个峰值p对应的是未知肽P的前端子序列,还是后端子序列,因此在质谱图G中,每个峰值p用两个顶点v和v表示。其中、,表示峰值p对应的是前端子序列,v表示峰值p对应的是后端子序列,但用未知肽P减去后端子序列,我们得到前端子序列。这样,对于每个峰值p,不管它是前端子序列,还是后端子序列,我们总是可以在质谱图G中用一个顶点来表示这个峰值p对应的未知肽P的前端子序列。因为图中的每个顶点表示未知肽P的某个前端子序列,如果任意两个顶点对应质量值相减等于一个或几个氨基酸的质量值,表示这两个前端子序列相差一个或几个氨基酸。Dancik等[39]为质谱图G设计了一种加权算法,并通过在加权质谱图中寻找最长路径的方法来得到与未知肽P最相似的肽。但他们注意到同时经过v和v的最长路径是毫无意义的。因为一个峰值p不可能既是未知肽P的前端子序列又是后端子序列。这样问题转化为寻找不能同时经过一些顶点对的最长路径问题。称不能同时经过的顶点对为禁止顶点对。因为避免禁止顶点对的路径问题是NP-Hard的,所以避免禁止顶点对的最长路径问题也是NP-Hard的。Dancik等和Chen等又注意到因为每个顶点都对应一个质量值,实际上顶点是有序的,可以将它们从左向右画在数轴上,对于任意两对禁止顶点对(v1,v1)和(v,v2),(v1,v1)对应的区间段和(v2,v2)对应的区间段是嵌套的。针对基于串联质谱的肽从头测序问题,本文重点进行了以下研究工作：(1)基于串联质谱的肽从头测序问题可以转化为避免禁止顶点对的最长路径问题(PAFP)。一般的PAFP问题是NP-Hard的。但是从肽从头测序到PAFP问题的转化过程中,禁止顶点对具有嵌套结构。基于禁止顶点对的嵌套结构,我们给出求解肽从头测序问题的一种顶点收缩算法。顶点收缩算法是一种多项式时间算法,其时间复杂度为D(|V|3)。
【关键词】：样本 断点 基因组 跨度 肽从头测序 禁止顶点对 嵌套结构 顶点收缩 算法
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：Q78;TP301.6
【目录】：

• 摘要11-14
• ABSTRACT14-17
• 第1章 绪论17-30
• 1.1 研究背景及意义17-20
• 1.1.1 研究背景18-19
• 1.1.2 研究意义19-20
• 1.2 研究现状20-24
• 1.2.1 样本断点距离问题20-22
• 1.2.2 肽从头测序问题22-24
• 1.3 算法基本知识24-27
• 1.3.1 算法与计算复杂性24-26
• 1.3.2 动态规划算法26-27
• 1.3.3 参数化算法27
• 1.4 本文主要工作和创新点27-28
• 1.5 各章节安排28-30
• 第2章 样本断点距离的复杂性30-43
• 2.1 引言30
• 2.2 (1,2)-样本断点距离是NP-Hard的30-34
• 2.2.1 预备知识31-32
• 2.2.2 样本断点距离是NP-Hard的32-34
• 2.3 (1,2)-样本断点距离是APX-Hard的34-40
• 2.3.1 预备知识34-36
• 2.3.2 样本断点距离是APX-Hard的36-40
• 2.4 样本断点距离不存在近似算法和参数算法40-42
• 2.4.1 样本断点距离不存在近似算法40-41
• 2.4.2 样本断点距离不存在参数算法41-42
• 2.5 本章小结42-43
• 第3章 (1,2)-样本断点距离的动态规划算法43-59
• 3.1 引言43-45
• 3.2 预备知识45-47
• 3.3 动态规划算法47-54
• 3.3.1 寻找最小样本的动态规划算法47-51
• 3.3.2 算法的复杂性51-54
• 3.4 仿真实验54-58
• 3.4.1 产生随机数据54-55
• 3.4.2 仿真55-58
• 3.5 本章小结58-59
• 第4章 基于串联质谱的肽从头测序59-68
• 4.1 引言59-63
• 4.2 质谱图的构造63-65
• 4.2.1 顶点的构造63-64
• 4.2.2 边的构造64-65
• 4.2.3 加权函数的构造65
• 4.3 禁止顶点对的结构65-67
• 4.3.1 分半结构66
• 4.3.2 层次结构66-67
• 4.3.3 嵌套结构67
• 4.4 本章小结67-68
• 第5章 肽从头测序的顶点收缩算法68-81
• 5.1 引言68-71
• 5.2 层次结构的顶点收缩算法71-75
• 5.2.1 层次结构的收缩算法71-72
• 5.2.2 层次结构的算法示例72-75
• 5.3 嵌套结构的顶点收缩算法75-79
• 5.3.1 嵌套结构的收缩算法75-77
• 5.3.2 嵌套结构的算法示例77-79
• 5.4 本章小结79-81
• 第6章 总结与展望81-83
• 6.1 本文总结81
• 6.2 研究展望81-83
• 参考文献83-88
• 致谢88-89
• 攻读学位期间发表的学术论文89-90
• 在读期间参与科研项目情况90-91
• 外文论文91-117
• 学位论文评阅及答辨情况表117

【相似文献】

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

1 胡洪林;;截断思想在算法分析中的应用[J];科技风;2012年12期

2 陈际平;算法分析与优化程序的研究[J];西北大学学报(自然科学版);1994年05期

3 梁彦杰;徐坚;;算法分析中概率变化与图形生成[J];云南大学学报(自然科学版);2009年S2期

4 刘宁;邵晓艳;;算法分析与设计课程中多媒体技术的应用[J];科技风;2009年18期

5 海亚;张永平;;算法对学生解决问题能力的培养[J];黑龙江科技信息;2008年10期

6 李冰颖,夏利民,舒远仲;学分制模式下网上选课系统的算法探析[J];江西科学;2004年05期

7 Anany Levitin;Maria Levitin;;算法谜题[J];中国科技信息;2014年08期

8 杜刚;陆黎明;;一修路问题的算法解决分析[J];太原师范学院学报(自然科学版);2006年02期

9 许之民;;砝码称重问题的多种算法分析与探究[J];合肥学院学报(自然科学版);2011年01期

10 李亚楠;;菌群优化算法分析[J];贵州大学学报(自然科学版);2011年02期

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

1 俞洋;田亚菲;;一种新的变步长LMS算法及其仿真[A];通信理论与信号处理新进展——2005年通信理论与信号处理年会论文集[C];2005年

2 周颢;刘振华;赵保华;;构造型的D~2FA生成算法[A];中国通信学会通信软件技术委员会2009年学术会议论文集[C];2009年

3 赖桃桃;冯少荣;张东站;;一种基于划分和密度的快速聚类算法[A];第二十五届中国数据库学术会议论文集（一）[C];2008年

4 刘远新;邓飞其;罗艳辉;舒添慧;;ERP柔性平台下物流运输配送系统算法分析[A];第二十六届中国控制会议论文集[C];2007年

5 王树西;白硕;姜吉发;;模式合一的“减首去尾”算法[A];第二届全国学生计算语言学研讨会论文集[C];2004年

6 王万青;张晓辉;;改进的A~*算法的高效实现[A];2009全国测绘科技信息交流会暨首届测绘博客征文颁奖论文集[C];2009年

7 孙焕良;邱菲;刘俊岭;朱叶丽;;IncSNN——一种基于密度的增量聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

8 韩建民;岑婷婷;于娟;;实现敏感属性l-多样性的l-MDAV算法[A];第二十七届中国控制会议论文集[C];2008年

9 张悦;尤枫;赵瑞莲;;利用蚁群算法实现基于程序结构的主变元分析[A];第五届中国测试学术会议论文集[C];2008年

10 王旭东;刘渝;邓振淼;;正弦波频率估计的修正Rife算法及其FPGA实现[A];全国第十届信号与信息处理、第四届DSP应用技术联合学术会议论文集[C];2006年

中国重要报纸全文数据库 前1条

1 科文;VIXD算法分析Web异常[N];中国计算机报;2008年

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

1 魏哲学;样本断点距离问题的算法与复杂性研究[D];山东大学;2015年

2 刘春明;基于增强学习和车辆动力学的高速公路自主驾驶研究[D];国防科学技术大学;2014年

3 刘新旺;多核学习算法研究[D];国防科学技术大学;2013年

4 于滨;城市公交系统模型与算法研究[D];大连理工大学;2006年

5 曾国强;改进的极值优化算法及其在组合优化问题中的应用研究[D];浙江大学;2011年

6 肖永豪;蜂群算法及在图像处理中的应用研究[D];华南理工大学;2011年

7 陈耿;面向中观审计的规则发现算法研究[D];东南大学;2005年

8 王维博;粒子群优化算法研究及其应用[D];西南交通大学;2012年

9 鱼亮;蛋白质网络模块结构识别算法研究[D];西安电子科技大学;2011年

10 李玉英;混沌蚂蚁群优化算法及其应用研究[D];北京邮电大学;2009年

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

1 黄厦;基于改进蚁群算法的柔性作业车间调度问题研究[D];昆明理工大学;2015年

2 李平;基于Hadoop的信息爬取与舆情检测算法研究[D];昆明理工大学;2015年

3 赵官宝;基于位表的关联规则挖掘算法研究[D];昆明理工大学;2015年

4 殷文华;移动容迟网络中基于社会感知的多播分发算法研究[D];内蒙古大学;2015年

5 徐翔燕;人工鱼群优化算法及其应用研究[D];西南交通大学;2015年

6 李德福;基于小世界模型的启发式寻路算法研究[D];华中师范大学;2015年

7 郑海彬;一种面向MAPREDUCE的DATASHUFFLE的优化方法[D];苏州大学;2015年

8 赵晓寒;轮换步长PSO算法及SMVSC参数优化[D];沈阳理工大学;2015年

9 安丰洋;基于无线网络的广播算法研究[D];曲阜师范大学;2015年

10 李智明;基于改进FastICA算法的混合语音盲分离[D];上海交通大学;2015年

  本文关键词：样本断点距离问题的算法与复杂性研究，，由笔耕文化传播整理发布。

本文编号：399348