基因组完美重组算法及一类QP-Free可行域方法的研究

论文摘要

本文研究了计算生物学中的基因组完美重组问题及QP-free可行域方法．全文共分为四章．基因组完美重组问题在生物种族进化研究、生物分类学研究和生物制药研究等领域中显示出重要的研究价值．在第一章里，我们将简单介绍基因组完美重组问题的提出、相关概念及研究现状．同时，在第一章，我们还简单介绍了QP-free可行域方法—一类求解非线性约束规划问题的方法．非线性约束规划问题是最优化领域中重要的研究课题之一，许多实际问题都可以归结为非线性约束规划问题，并且很多实际应用，比如工程设计、经济平衡等问题都要求数据仅仅在可行域内取值．本章最后，我们给出了本文的主要结果．第二章研究了含有n条染色体的基因组的完美重组问题．对于单条染色体的完美重组问题，Bérard等[4]利用strong interval树的结构，给出了O（2pn（?））时间的算法．后来，Bérard等[5]改进了此算法，给出了O（2dn（?））时间的算法，这里d≤p．同时，Bérard等在[5]提出了一个问题：再优化strong interval树，也很难找到一个标号基因组的完美翻转重组问题的多项式算法．本文把strong interval树和断点图结合起来，对含有n条染色体的基因组的完美重组问题，给出了一个O（n2）时间的算法．部分地解决了Bérard等[5]中提出的问题．设源染色体和目标染色体分别为π和r，它们含有不同基因集合．在第三章里，我们研究了含有不同基因集合的染色体π和r的完美重组问题．很明显，在这种情况下，“插入”或“删除”将成为必需的操作．我们推广了Hannehali和Pevzner[26]提出的多项式算法（简称HP算法），使之能够处理含有不同基因集合π和r的完美重组问题．在最后一章，我们研究了一类求解非线性约束规划问题的方法—QP-free可行域方法．我们知道SQP方法，即序列二次规划方法，是解决非线性约束规划问题的一种有效方法，但是，这种方法在每次迭代点处都要解决二次规划子问题，计算量很大，并且在某些迭代点处不一定有解．而QP-free可行域方法，是把求解一个非线性约束规划问题等价于线性方程组的求解问题．在每次迭代中，只需解若干个具有相同系数矩阵的线性方程组，因此减少了计算量，并且QP-free可行域方法能保证在每一个迭代点处都有解．1988年，Partier等[43]在前人的基础上提出了一类有效的QP-free方法，并且证明了这类方法的收敛性．之后，有很多的研究者对其进行了改进．我们利用光滑化的Fischer-Burmeister（FB）非线性互补函数，修改了QP-free可行域方法线性方程组系数矩阵的近似Jacobian矩阵Vk，提出了一类新方法，并且在比较弱的条件下证明该方法的可行性及收敛性．通过理论证明和例子的数据结果分析可以看出，我们提出的QP-free可行域方法比较令人满意．

论文目录

• 中文部分
• 中文摘要
• 英文摘要
• 符号说明
• 第一章 绪论
• §1.1 基因组完美重组问题
• §1.2 QP-Free可行域方法
• §1.3 本文的主要结果
• 第二章 基因组完美重组问题
• §2.1 引言
• §2.2 基本概念
• §2.3 计算完美重组序列
• §2.4 总结
• 第三章 基于翻转和删除操作的染色体的完美重组问题
• §3.1 引言
• §3.2 基本概念
• §3.3 基于翻转和删除操作的染色体的完美重组问题
• §3.4 基于翻转和删除操作的染色体的完美重组算法
• 第四章 一类QP-Free可行域方法
• §4.1 引言
• §4.2 算法
• §4.3 算法的可行性
• §4.4 算法的收敛性
• §4.5 超线性收敛
• §4.6 算法数据分析
• §4.7 总结
• 参考文献
• 致谢
• 作者简历
• 学位论文评阅及答辩情况表
• 英文部分
• 中文摘要
• Abstract
• Symbols
• Chapter 1 Introduction
• §1.1 Combinatoric Problems of Genome Perfect Rearrangements
• §1.2 A Kind of QP-Free Feasible Method
• §1.3 Main Contributions of This Dissertation
• Chapter 2 An Algorithm for Genome Perfect Sorting Problems
• §2.1 Introduction
• §2.2 Preliminaries
• §2.3 Computing Perfect Sorting Sequences
• §2.4 Conclusions
• Chapter 3 Perfect Sorting by Reversals and Deletions
• §3.1 Introduction
• §3.2 Preliminaries
• §3.3 Perfect Sorting by Reversals and Deletions
• §3.4 An Algorithm for Perfect Sorting by Reversals and Deletions
• Chapter 4 A Kind of QP-Free Feasible Method
• §4.1 Introduction
• §4.2 Algorithm
• §4.3 Implement of Algorithm
• §4.4 Golable Convergence
• §4.5 Superlinear Convergence
• §4.6 Numerical Tests
• §4.7 Conclusions
• References
• Acknowledgement
• Curriculum Vitae
• 学位论文评阅及答辩情况表