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

摘要

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

目录

文摘

英文文摘

论文说明：Symbobls

声明

第一章 绪论

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总结

参考文献

致谢

作者简历

Chapter 1 Introduction

Chapter 2 An Algorithm for Genome Perfect Sorting Problems

Chapter 3 Perfect Sorting by Reversals and Deletions

Chapter 4 A Kind of QP．Free Feasible Method

Reference

Acknowledgement

Curriculum Vitae