<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/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-22T09:45:53Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/10922" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/10922</identifier><datestamp>2026-05-14T13:48:24Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Owen, Megan</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2008-06-26T11:58:24Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2013-06-26T06:21:12Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2008-06-26T11:58:24Z</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/10922</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">6397167</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">A phylogenetic tree represents the evolutionary history of a set of organisms. There &#xd;
are many different methods to construct phylogenetic trees from biological data. &#xd;
To either compare one such algorithm with another, or to find the likelihood that &#xd;
a certain tree is generated from the data, researchers need to be able to compute &#xd;
the distance between trees. In 2001, Billera, Holmes, and Vogtmann introduced a &#xd;
space of phylogenetic trees, and defined the distance between two trees to be the &#xd;
length of the shortest path between them in that space. &#xd;
We use the combinatorial and geometric properties of the tree space to develop &#xd;
two algorithms for computing this geodesic distance. In doing so, we show that &#xd;
the possible shortest paths between two trees can be compactly represented by a &#xd;
partially ordered set. We calculate the shortest distance between the start and &#xd;
target trees for each potential path by converting the problem into one of finding &#xd;
the shortest path through a certain subspace of Euclidean space. In particular, we &#xd;
show there is a linear time algorithm for finding the shortest path between a point &#xd;
in the all positive orthant and a point in the all negative orthant of R^k contained &#xd;
in the subspace of R^k consisting of all orthants with the first i coordinates non- &#xd;
positive and the remaining coordinates non-negative for 0 &#xd;
&lt;= i &lt;= k. This case is &#xd;
of interest, because the general problem of finding a shortest path through higher &#xd;
dimensional Euclidean space with obstacles is NP-hard. The resulting algorithms &#xd;
for computing the geodesic distance appear to be the best available to date.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en_US">en</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">phylogenetic trees</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">tree space</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">geodesic distance</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Euclidean shortest path</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">combinatorics</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">computational geometry</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">Distance Computation in the Space of Phylogenetic Trees</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">Owen, Megan</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="fd544f58-0a4b-480c-b286-486f1f24bc3a">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en&lt;/Language>
   	&lt;Title>Distance Computation in the Space of Phylogenetic Trees&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2008-06-26T11:58:24Z&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Owen, Megan&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>phylogenetic trees&lt;/Keyword>
    &lt;Keyword>tree space&lt;/Keyword>
    &lt;Keyword>geodesic distance&lt;/Keyword>
    &lt;Keyword>Euclidean shortest path&lt;/Keyword>
    &lt;Keyword>combinatorics&lt;/Keyword>
    &lt;Keyword>computational geometry&lt;/Keyword>
   	&lt;Abstract>A phylogenetic tree represents the evolutionary history of a set of organisms. There &#xd;
are many different methods to construct phylogenetic trees from biological data. &#xd;
To either compare one such algorithm with another, or to find the likelihood that &#xd;
a certain tree is generated from the data, researchers need to be able to compute &#xd;
the distance between trees. In 2001, Billera, Holmes, and Vogtmann introduced a &#xd;
space of phylogenetic trees, and defined the distance between two trees to be the &#xd;
length of the shortest path between them in that space. &#xd;
We use the combinatorial and geometric properties of the tree space to develop &#xd;
two algorithms for computing this geodesic distance. In doing so, we show that &#xd;
the possible shortest paths between two trees can be compactly represented by a &#xd;
partially ordered set. We calculate the shortest distance between the start and &#xd;
target trees for each potential path by converting the problem into one of finding &#xd;
the shortest path through a certain subspace of Euclidean space. In particular, we &#xd;
show there is a linear time algorithm for finding the shortest path between a point &#xd;
in the all positive orthant and a point in the all negative orthant of R^k contained &#xd;
in the subspace of R^k consisting of all orthants with the first i coordinates non- &#xd;
positive and the remaining coordinates non-negative for 0 &#xd;
&amp;lt;= i &amp;lt;= k. This case is &#xd;
of interest, because the general problem of finding a shortest path through higher &#xd;
dimensional Euclidean space with obstacles is NP-hard. The resulting algorithms &#xd;
for computing the geodesic distance appear to be the best available to date.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>