2016/04/11 by Julien Baste, Baste, Julien, Christophe Paul +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #05C85 #92Dxx #Bioinformatics and Genomic Networks #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2 #Genomics and Phylogenetic Studies #J.3
paper · pdf · doi:10.48550/arxiv.1604.03008
openalex publication_date 2016/04/11 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
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 univocally labeled 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 so-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 2O(k2) ⋅ n, where n is the total size of the input.