Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/6995
Title: | Algorithms for Multiple Sequences Alignment, Comparison of Trees, and Steiner Trees |
Authors: | Wang, Lusheng |
Advisor: | Jiang, Tao |
Department: | Electrical and Computer Engineering |
Keywords: | Electrical and Computer Engineering;Electrical and Computer Engineering |
Publication Date: | Mar-1995 |
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> |
URI: | http://hdl.handle.net/11375/6995 |
Identifier: | opendissertations/2296 3258 1370646 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 2.43 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.