title: Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees.
abstract: In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species X; these relationships are often depicted via a phylogenetic tree-a tree having its leaves labeled bijectively by elements of X and without degree-2 nodes-called the "species tree." One common approach for reconstructing a species tree consists in first constructing several phylogenetic trees from primary data (e.g., DNA sequences originating from some species in X), and then constructing a single phylogenetic tree maximizing the "concordance" with the input trees. The obtained tree is our estimation of the species tree and, when the input trees are defined on overlapping-but not identical-sets of labels, is called "supertree." In this paper, we focus on two problems that are central when combining phylogenetic trees into a supertree: the compatibility and the strict compatibility problems for unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of "containing as a minor" and "containing as a topological minor" in the graph community. Both problems are known to be fixed parameter tractable in the number of input trees k, by using their expressibility in monadic second-order logic and a reduction to graphs of bounded treewidth. Motivated by the fact that the dependency on k of these algorithms is prohibitively large, we give the first explicit dynamic programming algorithms for solving these problems, both running in time [Formula: see text], where n is the total size of the input.
authors.affiliation: LIRMM, CNRS, Université de Montpellier, Montpellier, France.
authors.forename: Julien
authors.initials: J
authors.lastname: Baste
authors.affiliation: LIRMM, CNRS, Université de Montpellier, Montpellier, France.
authors.forename: Christophe
authors.initials: C
authors.lastname: Paul
authors.affiliation: LIRMM, CNRS, Université de Montpellier, Montpellier, France.
authors.forename: Ignasi
authors.initials: I
authors.lastname: Sau
authors.affiliation: ISE-M, IBC, Université de Montpellier, CNRS, IRD, EPHE, Montpellier, France. celine.scornavacca@umontpellier.fr.
authors.forename: Celine
authors.initials: C
authors.lastname: Scornavacca
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D005075:Biological Evolution; D008957:Models, Genetic; D010802:Phylogeny
keywords: Compatibility; Dynamic programming; FPT algorithm; Parameterized complexity; Phylogenetics; Unrooted phylogenetic trees