【作者】 张海燕；

【导师】 李国君；

【作者基本信息】 山东大学 ， 运筹学与控制论， 2008， 博士

【摘要】 本文研究了计算生物学中的基因组完美重组问题及QP-free可行域方法．全文共分为四章．基因组完美重组问题在生物种族进化研究、生物分类学研究和生物制药研究等领域中显示出重要的研究价值．在第一章里，我们将简单介绍基因组完美重组问题的提出、相关概念及研究现状．同时，在第一章，我们还简单介绍了QP-free可行域方法—一类求解非线性约束规划问题的方法．非线性约束规划问题是最优化领域中重要的研究课题之一，许多实际问题都可以归结为非线性约束规划问题，并且很多实际应用，比如工程设计、经济平衡等问题都要求数据仅仅在可行域内取值．本章最后，我们给出了本文的主要结果．第二章研究了含有n条染色体的基因组的完美重组问题．对于单条染色体的完美重组问题，Bérard等[4]利用strong interval树的结构，给出了O(2~pn(?))时间的算法．后来，Bérard等[5]改进了此算法，给出了O(2~dn(?))时间的算法，这里d≤p．同时，Bérard等在[5]提出了一个问题：再优化strong interval树，也很难找到一个标号基因组的完美翻转重组问题的多项式算法．本文把strong interval树和断点图结合起来，对含有n条染色体的基因组的完美重组问题，给出了一个O(n~2)时间的算法．部分地解决了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矩阵V_k，提出了一类新方法，并且在比较弱的条件下证明该方法的可行性及收敛性．通过理论证明和例子的数据结果分析可以看出，我们提出的QP-free可行域方法比较令人满意．更多还原

【Abstract】 In this paper, we mainly study the problem of genome perfect rearrangements in bioinformatics and a kind of QP-free feasible method. This paper consists of four chapters.Recently, the studies of genome perfect rearrangements have displayed importance in many fields, such as evolutionary histories of species, taxonomy of biology, biomedicine, etc. Therefore, in Chapter 1, we first give a brief review of genome perfect rearrangements and introduce the corresponding conceptions. We also introduce a kind of QP-free feasible method-which is used to solve a nonlinear constrained optimization problem. The nonlinear constrained optimization problem is an important research topic in mathemtical programming fields. Many practical problems can be reduced to be the nonlinear constrained optimization problems. Moreover, some real-life applications such as in engineering design and economical equilibrium of supply and demand require the datas only defined in the feasible region. Finally, we introduce the main results obtained in our paper.The objective of Chapter 2 is to deal with the problem of genomes perfect rearrangements. For the problem of uni-chromosome (permutation) perfect rearrangements , Berard et al. [4] gave an O(2~pn(?)) algorithm with the strong interval tree framework. Later, Berard et al. [5] improved the algorithm. They can compute a parsimonious perfect scenario for the permutation in worst-case time O(2~dn(?)), where d≤p. In this paper, we connect a strong interval tree with a breakpoint graph. For the problem of TV-chromosomal genomes perfect rearrangements , we design an algorithm and get an optimal perfect sorting sequence for the genomes in worst-case time O(n~2). We solved this problem which was proposed in [5], i.e., it seems difficult to optimize the strong interval tree framework in order to compute perfect scenarios in polynomial time for larger classes of signed permutations.The problem of sorting signed permutation (chromosome) by reversals has been studied intensively. In 1995, Hannehali and Pevzner [26] developed the first polynomial algorithm, denoted by HP algorithm in our paper, and they gave the formula of the reversal distance. Letπand r be the source chromosome (permutation ) and target chromosome (permutatio), respectively. Moreover, they have the different gene content. In Chapter 3, we study the problem of perfectly sortingπand r. Obviously, in such case, some additional steps (insertions or deletions) are needed. We show how to extend the HP algorithm to a polynomial algorithm which can compute the perfect scenarios forπandγby reversals and deletions.In the last chapter, we concern a method of solving the nonlinear constrained optimization problem, namely QP-free feasible method. In 1988, Panier [43] brought forward a kind of available QP-free method on the basis of the former and proved convergence of the method. Subsequently, some people mended this method. We base on the results of the formers to modify the coefficient matrix V_k of linear systems of equations with smoothing Fischer-Burmeister nonlinear complementarity problem (NCP) function. Then we propose a new kind of QP-free feasible method. Under some weaker conditions, our method is implementable and globally convergent . Moverover, some numerical test results are given to indicate that the algorithm is quite promising.更多还原