Back to results

University of Waterloo

An Approximation Algorithm for Character Compatibility and Fast Quartet-based Phylogenetic Tree Comparison

Abstract

dc:description.abstract

Phylogenetic analysis, or the inference of evolutionary history is done routinely by biologists and is one of the most important problems in systematic biology. In this thesis, we study two computational problems in the area. First, we study the evolutionary tree reconstruction problem under the character compatibility (CC) paradigm and give a polynomial time approximation scheme (PTAS) for a variation of the formulation called fractional character compatibility (FCC), which has been proven to be NP-hard. We also present a very simple algorithm called the Ordinal Split Method (OSM) to generate bipartitions given sequence data, which can be served as a front-end to the PTAS. The performance of the OSM and the validity of the FCC formulation are studied through simulation experiments. The second part of this thesis presents an efficient algorithm to compare evolutionary trees using the quartet metric. Different evolutionary hypothesis arises when different data sets are used or when different tree inference methods are applied to the same data set. Tree comparisons are routinely done by biologists to evaluate the quality of their tree inference experiments. The quartet metric has many desirable properties but its use has been hindered by its relatively heavy computational requirements. We address this problem by giving the first O(n^2) time algorithm to compute the quartet distance between two evolutionary trees.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2000

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tsang, John

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Copyright: 2000, Tsang, John. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/1110

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Tsang, John. An Approximation Algorithm for Character Compatibility and Fast Quartet-based Phylogenetic Tree Comparison. University of Waterloo, 2000. http://hdl.handle.net/10012/1110