dc.contributor.author | Li, Zhijiang | |
dc.date.accessioned | 2014-08-21T15:23:49Z | |
dc.date.available | 2014-08-21T15:23:49Z | |
dc.date.issued | 2014-08-21 | |
dc.identifier.uri | http://hdl.handle.net/10222/53976 | |
dc.description.abstract | Phylogenetic trees are used to represent the evolution of a set of species. However, this history may include reticulation events where taxa acquire genes from more than one ancestor or from contemporaries, which leads to non-tree-like ancestry relationships that cannot be represented using trees alone. Hybridization networks can be used to model such histories. The hybridization number is NP-hard to compute and we present a fixed-parameter algorithm to compute the hybridization number (and a corresponding network) of two multifurcating trees. The running time of our algorithm is $O(4.83^{k}n)$, where $k$ is the computed hybridization number, which is more efficient than two previous algorithms with complexity $O(2^{n}poly(n))$ and $O((6^{k}k!)poly(n))$, respectively. We verified the practicality of our algorithm by implementing it and evaluating its performance on real data. Our algorithm is obtained using a non-trivial combination of novel ideas with techniques from previous algorithms for multifurcating SPR distance and binary hybridization number. | en_US |
dc.language.iso | en | en_US |
dc.subject | Phylogenetic trees | en_US |
dc.subject | Hybridization network | en_US |
dc.subject | Hybridization number | en_US |
dc.subject | FPT | en_US |
dc.subject | Multifurcation | en_US |
dc.title | Fixed-Parameter Algorithm for Hybridization Number of Two Multifurcating Trees | en_US |
dc.date.defence | 2014-08-07 | |
dc.contributor.department | Faculty of Computer Science | en_US |
dc.contributor.degree | Master of Computer Science | en_US |
dc.contributor.external-examiner | n/a | en_US |
dc.contributor.graduate-coordinator | Evangelos E. Milios | en_US |
dc.contributor.thesis-reader | Dr. Andrew Rau-Chaplin | en_US |
dc.contributor.thesis-reader | Dr. Robert Beiko | en_US |
dc.contributor.thesis-supervisor | Dr. Norbert Zeh | en_US |
dc.contributor.ethics-approval | Not Applicable | en_US |
dc.contributor.manuscripts | Not Applicable | en_US |
dc.contributor.copyright-release | Not Applicable | en_US |