Some Studies On Optimization Topics Of Computational Biology

This paper mainly studies some combinatorial optimization problems on computational molecular biology. The paper consists of six chapters.In Chapter 1, we give a brief introduction for combinatorial optimization, computational biology and algorithm analysis.In Chapter 2, we investigate the genome rearrangement problem. We propose a new transposition operation which is a generalization of the transpositions in the literature. We design an approximation algorithm of sorting the genome by reversals and this new kind of transposition.In Chapter 3, we consider the syntenic distance problem, which is a relax form of the translocation distance between multi-chromosomal genomes. We propose a new special class of instances, which is called uncovering synteny. We present a polynomial time algorithm to solve this class of synteny instances optimally.In Chapter 4, we discuss the recombination distance problem. We study how to optimally solve some special classes of sequences by recombination. We revisit the result for tree class in the literature and show that the greedy algorithm for solving this class is not always optimal. We will propose a revised algorithm which solves the problem optimally. In this chapter, we will further propose a new class of sequences, which is called chain class, and present an optimal algorithm for solving chain class in polynomial time.In Chapter 5, we focus on the recombination distance problem for generalized chains. We propose a new class of sequences, called generalized chain, which greatly extends the definition of chain class to more general case by ignoring some restrictive conditions. We present optimal algorithms for dealing with all cases of a generalized chain.In Chapter 6, we study the group testing problem based on the genomes which cause particular biological phenomenon. We establish the model of searching for many edges in a hypergraph and give a competitive algorithm for solving this problem.