Find in Library

The problem of constructing a <em>minimally resolved phylogenetic supertree</em> (i.e., a rootedtree having the smallest possible number of internal nodes) that contains all of the rooted triplets froma consistent set <em>R</em> is known to be NP-hard. In this article, we prove that constructing a phylogenetictree consistent with <em>R</em> that contains the minimum number of additional rooted triplets is also NP-hard,and develop exact, exponential-time algorithms for both problems. The new algorithms are applied toconstruct two variants of the <em>local consensus tree</em>; for any set <em>S</em> of phylogenetic trees over some leaflabel set <em>L</em>, this gives a minimal phylogenetic tree over L that contains every rooted triplet present in alltrees in <em>S</em>, where “minimal” means either having the smallest possible number of internal nodes or thesmallest possible number of rooted triplets. (The second variant generalizes the <em>RV-II tree</em>, introducedby Kannan <em>et al</em>. in 1998.) We also measure the running times and memory usage in practice of thenew algorithms for various inputs. Finally, we use our implementations to experimentally investigatethe non-optimality of Aho <em>et al</em>.’s well-known BUILD algorithm from 1981 when applied to the localconsensus tree problems considered here.