Algorithms Of Genome Perfect Rearrangements And The Study Of A QP-Free Feasible Method

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.