Files
Abstract
Many important bioinformatics problems are NP-hard and it is thus difficult to find efficient algorithms to solve them exactly. However, these problems often require efficient and exact solutions for the accurate understanding of biological systems, presenting a great challenge in computation. This dissertation initiates an algorithmic framework to address this challenge, which is established on the theory and techniques of parameterized computation. In particular, the framework is to model bioinformatics problems with graphs of small tree width, where existing elegant graph theoretic results, such as the Courcelle's theorem, may be applied to achieve efficient (e.g., linear-time) exact algorithms. The dissertation investigates two technically difficult issues in implementing this frame-work: (1) how to model bioinformatics problems as monadic second order (MSO) logic expressible problems on graphs of small tree width; (2) how to develop parameterized techniques that can reduce other problems to MSO logic expressible graph problems while maintaining small tree width. Various bioinformatics problems in proteomics and structural genomics are studied to address these two issues. Experiments were conducted which demonstrate the advantages of this new algorithmic framework over other methods in both accuracy and efficiency.