序列及序列二级结构联配问题的若干算法研究

发布时间：2017-04-17 18:21

  本文关键词：序列及序列二级结构联配问题的若干算法研究，，由笔耕文化传播整理发布。

【摘要】：序列联配以及序列二级结构联配是生物信息处理中最基本最重要的问题。自1970年Needleman和Wunsch提出的经典的动态规划算法以来,如何获得结果准确,时间空间效率更高的序列联配算法和软件一直是生物信息学研究中的一项重要课题。考虑实际序列联配问题中的序列具有较高的相识度,也就是说在最佳联配中各个序列中插入的空格数将不会太大,本文将待插入的空格数上限作为限制来设计序列联配算法,从而降低算法的运行时间和空间的复杂度。Needleman和Wunsch给出的运行时间和空间为O(m?n)的动态规划算法至今仍然是最为实用和有效的双序列联配算法之一,其中m,n为两条序列的长度。本文在Needleman和Wunsch的动态规划算法的基础上提出了一种在k插缺数限制下双序列联配的算法,其运行时间和空间复杂度都为O k?min?,(m n?)。同时,文中将该思想引入Hirschberg线性空间算法中,给出了一种在k插缺数限制下的双序列联配线性空间算法,其运行时间仍然为O k?min?,(m n?),但只使用线性的内存空间。大量实际数据说明一般最佳联配下插入空格数在序列长度的20%以内,因此在实验中,大部分序列将k规定在序列长度的20%,新算法可以将运行时间直接减少近50%的情况下仍然保证找到最优解,对于部分相似度高的序列,甚至可以将运行时间直接减少近85%的情况下仍然保证找到最优解。接下来,文中将参数k的思想应用到三条序列联配算法中,设计了在k插缺数限制下三条序列联配的算法,时间复杂度和空间复杂度都为2O(k?n),其中k为参数表示允许插入的最大空格数,三条序列长度均为n。在多序列联配问题中由于序列数量增加而导致计算难度陡增,引入参数k的概念也不能获得实际有效的算法。因此本文给出一种基于双序列联配的快速多序列联配启发式算法。然后以BAliBASE数据库来测试与其他算法比较,实验也验证我们的算法明显比之前的算法的准确性更好。对序列二级结构联配问题,文中同样经典的Bafna算法中引入参数k的概念。将原本时间和空间复杂度都为3 2 2O(mn?m n)的算法改进为时间和空间复杂度都为2 2 21 1O(k mn?k n)的算法,其中m、n为两条序列长度,1k是序列中允许插入的最大空格数。最后本文总结了引入参数k的概念的序列联配及序列二级结构联配问题的研究结果,并对相关工作的未来的研究方向做了展望及提出了一些问题可能的解决方法。
【关键词】：序列联配 多序列联配 动态规划 分治算法
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：Q811.4;O221.3
【目录】：

• 摘要5-6
• Abstract6-10
• 第一章 绪论10-16
• 1.1 背景10-12
• 1.2 研究现状及发展态势12-15
• 1.3 结论15
• 1.4 论文组织结构15-16
• 第二章 双序列联配16-34
• 2.1 双序列联研究现状、定义及基本问题16-18
• 2.1.1 双序列联研究现状16-17
• 2.1.2 双序列联配定义17
• 2.1.3 双序列联配基本问题17-18
• 2.2 Needleman和Wunsch的全局联配算法18-19
• 2.3 Hirschberg的线性空间算法19-23
• 2.3.1 Hirschberg算法基本思想19-21
• 2.3.2 Hirschberg算法21-23
• 2.4 双序列仿射空位罚分联配算法23-24
• 2.5 在插入空格数k约束条件下的动态规划算法24-26
• 2.5.1 算法思想24-25
• 2.5.2 算法25-26
• 2.6 在插入空格数k约束条件下的线性空间算法26-28
• 2.7 在插缺数k限制下的双序列仿射空位罚分联配算法28-29
• 2.8 实验结果29-32
• 2.9 本章小结32-34
• 第三章 三条序列联配34-49
• 3.1 三条序列联研究现状、定义及基本问题34-36
• 3.1.1 三条序列联研究现状34-35
• 3.1.2 三条序列联配定义35
• 3.1.3 三条序列联配基本问题35-36
• 3.2 三条序列联配经典动态规划算法36-37
• 3.3 三条序列仿射罚分联配动态规划算法37-39
• 3.4 在插入空格数k约束条件下的三条序列联配动态规划算法39-44
• 3.4.1 算法思想39-42
• 3.4.2 算法42-44
• 3.5 在插入空格数k约束条件下三条序列仿射空位罚分联配算法44-47
• 3.6 本章小结47-49
• 第四章 基于双序列联配的快速多序列联配算法研究49-61
• 4.1 多序列联配问题启发式算法研究现状49-50
• 4.2 基于双序列联配的算法思想50-52
• 4.3 随机联配算法及结果52-54
• 4.3.1 随机联配算法52-53
• 4.3.2 随机联配结果53-54
• 4.4 星联配算法54-55
• 4.5 一种贪心策略的多序列联配算法55-58
• 4.5.1 一种贪心策略的多序列联配算法思想56-57
• 4.5.2 一种贪心策略的多序列联配算法57-58
• 4.6 实验结果58-59
• 4.7 本章小结59-61
• 第五章 序列二级结构联配61-71
• 5.1 序列二级结构联配研究现状、定义及基本问题61-65
• 5.1.1 序列二级结构联配研究现状61
• 5.1.2 序列二级结构联配定义61-64
• 5.1.3 序列二级结构联配基本问题64-65
• 5.2 序列二级结构联配算法65-67
• 5.3 在约束条件下的序列二级结构联配算法67-70
• 5.4 本章小结70-71
• 第六章 全文总结与展望71-74
• 6.1 全文总结71-73
• 6.2 后续工作展望73-74
• 致谢74-75
• 参考文献75-79

【参考文献】

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

1 李昭;生物序列相似性比较算法的研究[D];中国科学院研究生院（计算技术研究所）;2002年

  本文关键词：序列及序列二级结构联配问题的若干算法研究，由笔耕文化传播整理发布。

本文编号：314055