Back to search

McMaster University

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

Abstract

dc:description.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>

Degree

thesis:*
Department dc:contributor.department
Electrical and Computer Engineering
Year dc:date.issued
1995

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Lusheng
Advisor dc:contributor.advisor
  • Jiang, Tao

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/2296
3258
1370646

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Wang, Lusheng. Algorithms for Multiple Sequences Alignment, Comparison of Trees, and Steiner Trees. 1995. http://hdl.handle.net/11375/6995