Algorithms On Motif Finding And Closest String Problems

Bioinformatics (computational biology in another word) is a new science field. Research in this field involves multi-disciplines such as biology, computer science, applied mathematics, etc. Computational biology is subject to expose the biological signification of large amount of biological data and explore the mystery of life activities. Motif Finding problem and Closest String problem are basic and important in the research of computational biology, which find applications in many fields, even, outside computational biology, in coding theory. Both of them are widely and deeply studied in the last few years, and how to create better solution strategy with latest research technology, such as distributed system and Fixed-Parameter theory, is the key point of this thesis.After the deep analysis of existent algorithms, this thesis presents a new distributed parameterized algorithm to solve Motif Finding problem, and design of the distributed system cooperating with the algorithm as well, then proves it's right and efficient by analysing test results on the distributed system; a new strategy, combining advantages of a branch-and-bound algorithm and a Fixed-Parameter algorithm, to compute optimal upper bound of general Closest String problem; formula of deducing lower bound and the design and optimization of new algorithms on lower bound. The algorithms complement the consuming too much time disadvantage of the Fixed-Parameter algorithm when d is a little larger and there is no solution, and are suitable to check whether there exists solution on the lower bound and compute all solutions as well.The design and realization of these algorithms are presented in detail in this thesis, as well as the analysis of testing results, which indicate that the proposed algorithms are of high efficiency and feasible.