<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T10:22:29Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1110" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1110</identifier><datestamp>2017-03-21T19:13:23Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="55d17895-eeab-4058-b756-151e5dc1be47" confidence="600">Tsang, John</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:22:56Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:22:56Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2000</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2000</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1110</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">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.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">520818 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2000, 
  Tsang, John. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">phylogenetic analysis</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">phylogeny reconstruction</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">combinatorial algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">algorithm analysis</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">bioinformatics</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">An Approximation Algorithm for Character Compatibility and Fast Quartet-based Phylogenetic Tree Comparison</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>