Computing the minimum number of hybridisation events for a consistent evolutionary history

Simple item page
dc.contributor.authorBordewich, M.
dc.contributor.authorSemple, C.
dc.date.accessioned2016-05-26T01:49:33Z
dc.date.available2016-05-26T01:49:33Z
dc.date.issued2004en
dc.description.abstractIt 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.issn1172-8531
dc.identifier.urihttp://hdl.handle.net/10092/12205
dc.language.isoen
dc.publisherUniversity of Canterburyen
dc.rightsAll Rights Reserveden
dc.rights.urihttps://canterbury.libguides.com/rights/theses
dc.subject.anzsrcFields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematicsen
dc.subject.anzsrcFields of Research::31 - Biological sciences::3104 - Evolutionary biology::310410 - Phylogeny and comparative analysisen
dc.titleComputing the minimum number of hybridisation events for a consistent evolutionary historyen
dc.typeDiscussion / Working Papers
uc.collegeFaculty of Engineering
uc.departmentSchool of Engineeringen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
bordewich_semple_ucdms2004-21_report.pdf
Size:
1.64 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Engineering: Reports