Compatibility of unrooted phylogenetic trees is FPT |
| |
Authors: | David Bryant Jens Lagergren |
| |
Affiliation: | 1. McGill Centre for Bioinformatics, Montreal, Que., Canada;2. Stockholm Bioinformatics Center and Department of Numerical Analysis and Computer Science, KTH, Stockholm, Sweden |
| |
Abstract: | A collection of T1,T2,…,Tk of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible if there exists a tree T such that each tree Ti can be obtained from T by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(nk) time, n being the number of leaves. Here, we present an O(nf(k)) algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable (FPT) with respect to the number k of trees. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|