Tools
Tools
Spillner, Andreas, Nguyen, Binh T. and Moulton, Vincent 
ORCID: https://orcid.org/0000-0001-9371-6435
(2008)
Computing phylogenetic diversity for split systems.
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5 (2).
pp. 235-244.
ISSN 1545-5963
Abstract
In conservation biology, it is a central problem to measure, predict, and preserve biodiversity as species face extinction. In 1992, Faith proposed measuring the diversity of a collection of species in terms of their relationships on a phylogenetic tree and using this information to identify collections of species with high diversity. Here, we are interested in some variants of the resulting optimization problem that arise when considering species whose evolution is better represented by a network rather than a tree. More specifically, we consider the problem of computing phylogenetic diversity relative to a split system on a collection of species of size n. We show that, for general split systems, this problem is NP-hard. In addition, we provide some efficient algorithms for some special classes of split systems, in particular presenting an optimal O(n) time algorithm for phylogenetic trees and an O(n log n + nk) time algorithm for choosing an optimal subset of size k relative to a circular split system.
| Item Type: | Article |
|---|---|
| Faculty \ School: | Faculty of Science > School of Computing Sciences |
| UEA Research Groups: | Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre |
| Related URLs: | |
| Depositing User: | Vishal Gautam |
| Date Deposited: | 07 Mar 2011 13:36 |
| Last Modified: | 10 Jan 2024 01:23 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/23128 |
| DOI: | 10.1109/TCBB.2007.70260 |
Actions (login required)
 |
View Item |