Engineering: Reports
http://hdl.handle.net/10092/611
2016-07-30T00:55:20ZOn approximation of optimizing phylogenetic diversity for cluster systems
http://hdl.handle.net/10092/12533
On approximation of optimizing phylogenetic diversity for cluster systems
Faller, Beáta; Semple, Charles; Steel, M. A.
A basic question in conservation biology is how to maximize future
biodiversity as species face extinction. One way to approach this question
is by measuring the diversity of a set of species in terms of the evolutionary
history that those species span in a phylogenetic tree. Maximizing the resulting
'phylogenetic diversity' (PD) is one prominent selection criteria for deciding
which species to conserve. The basic PD optimization problem aims to find a
k-element subset of a given species set that has maximum PD among all such
subsets. In this paper, we consider a generalization of this problem, which
arises in situations where we do not know the true tree, or where evolution is
not tree-like. We show that a greedy algorithm gives a (1-e⁻¹)-approximation
to the general PD optimization problem, and that there is no polynomial-time
algorithm that achieves a better approximation ratio unless P=NP.
2009-01-01T00:00:00ZPhylogenetic diversity and the greedy algorithm
http://hdl.handle.net/10092/12532
Phylogenetic diversity and the greedy algorithm
Steel, M. A.
Given a phylogenetic tree with leaves labelled by a collection of
species, and with weighted edges, the 'phylogenetic diversity' of any subset of
the species is the sum of the edge weights of the minimal subtree connecting
the species. This measure is relevant in biodiversity conservation where one
may wish to compare different subsets of species according to how much evolutionary
variation they encompass. In this note we show that phylogenetic
diversity has an attractive mathematical property that ensures that we can
solve the following problem easily by the greedy algorithm: find a subset of
the species of any given size k of maximal phylogenetic diversity. We also
describe an extension of this result that also allows weights to be assigned to
species.
2004-01-01T00:00:00ZA cluster reduction for computing the subtree distance between phylogenies
http://hdl.handle.net/10092/12531
A cluster reduction for computing the subtree distance between phylogenies
Linz, Simone; Semple, Charles
Calculating the rooted subtree prune and regraft (rSPR) distance
between two rooted binary phylogenetic trees is a frequently applied process in
various areas of molecular evolution. However, computing this distance is an
NP-hard problem and practical algorithms for computing it exactly are rare.
In this paper, a divide-and-conquer approach to calculating the rSPR distance
is established. This approach breaks the problem instance into a number of
smaller and more tractable subproblems. Two reduction rules which were
previously used to show that computing the rSPR distance is fixed-parameter
tractable can easily be used to complement this new theoretical result, and so
a significant positive impact on the running time of calculating this distance
in practice is likely.
2008-01-01T00:00:00ZLocating a tree in a phylogenetic network
http://hdl.handle.net/10092/12530
Locating a tree in a phylogenetic network
Iersel, Leo van; Semple, Charles; Steel, M. A.
Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of
species. The TREE CONTAINMENT problem asks whether a given phylogenetic tree is embedded in a given
phylogenetic network. Given a phylogenetic network and a cluster of species, the CLUSTER CONTAINMENT
problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network.
Both problems are known to be NP-complete in general. In this article, we consider the restriction of
these problems to several well-studied classes of phylogenetic networks. We show that TREE CONTAINMENT
is polynomial-time solvable for normal networks, for binary tree-child networks, and for level-k networks.
On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both TREE
CONTAINMENT and CLUSTER CONTAINMENT remain NP-complete.
2010-01-01T00:00:00Z