Computing the minimum number of hybridisation events for a consistent evolutionary history
dc.contributor.author | Bordewich, M. | |
dc.contributor.author | Semple, C. | |
dc.date.accessioned | 2016-05-26T01:49:33Z | |
dc.date.available | 2016-05-26T01:49:33Z | |
dc.date.issued | 2004 | en |
dc.description.abstract | It is now well-documented that the structure of evolutionary relationships between a set of present-day species is not necessarily tree-like. The reason for this is that reticulation events such as hybridisations mean that species are a mixture of genes from different ancestors. Since such events are relatively rare, a fundamental problem for biologists is to determine the smallest number of hybridisation events required to explain a given (input) set of data in a single (hybrid) phylogeny. The main results of this paper show that computing this smallest number is both NP-hard and APX-hard in the case the input is a collection of phylogenetic trees on sets of present-day species. This answers a problem which was raised at a recent conference. As a consequence of these results, we also correct a previously published NP-hardness proof in the case the input is a collection of binary sequences, where each sequence represents the attributes of a particular present-day species. The NP and APX-hardness of these problems mean that it is unlikely that there is an efficient algorithm for either computing the result exactly, or approximating it to any arbitrary degree of accuracy. | en |
dc.identifier.issn | 1172-8531 | |
dc.identifier.uri | http://hdl.handle.net/10092/12205 | |
dc.language.iso | en | |
dc.publisher | University of Canterbury | en |
dc.rights | All Rights Reserved | en |
dc.rights.uri | https://canterbury.libguides.com/rights/theses | |
dc.subject.anzsrc | Fields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics | en |
dc.subject.anzsrc | Fields of Research::31 - Biological sciences::3104 - Evolutionary biology::310410 - Phylogeny and comparative analysis | en |
dc.title | Computing the minimum number of hybridisation events for a consistent evolutionary history | en |
dc.type | Discussion / Working Papers | |
uc.college | Faculty of Engineering | |
uc.department | School of Engineering | en |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- bordewich_semple_ucdms2004-21_report.pdf
- Size:
- 1.64 MB
- Format:
- Adobe Portable Document Format
- Description:
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: