Algorithms for Multiple Sequences Alignment, Comparison of Trees, and Steiner Trees

Abstract

<p>Comparison of sequences and trees is an essential problem in computational biology. In this thesis, we investigate some algorithmic problems in sequence and tree comparison. Theoretical issues such as computational complexity, the efficiency of algorithms, and the performance of approximation algorithms are stressed.</p> <p>The most popular approach for comparing a set of sequences is multiple sequence alignment. We show that two popular variants of multiple sequence alignment, multiple alignment with SP-score and tree alignment, are NP-complete. We also design a polynomial time approximation scheme (PTAS) for tree alignment, which is believed to be the first PTAS in computational biology.</p> <p>Tree comparison has applications in the study of RNA secondary structures and evolutionary trees. We propose the notion of alignment of trees as a new method for comparing RNA secondary structure trees and give an efficient algorithm for computing the optimal alignment of such trees. Several other methods for comparing evolutionary trees are also considered.</p> <p>Steiner trees have been studied extensively in the literature, and are closely related to tree alignment. We also design a PTAS for some planar Steiner tree problems.</p>