Minimal Triangulation Algorithms for Perfect Phylogeny Problems

DOI10.1007/978-3-319-04921-2_34MaRDI QIDQ5404932zbMATH OpenOpenAlexFDO

Authors Rob Gysel

Publication date 31 March 2014

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.3931

zbMATH Keywords

minimal triangulationperfect phylogeny

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: Kloks, Kratsch, and Spinrad showed how treewidth and minimum-fill, NP-hard combinatorial optimization problems related to minimal triangulations, are broken into subproblems by block subgraphs defined by minimal separators. These ideas were expanded on by Bouchitt'e and Todinca, who used potential maximal cliques to solve these problems using a dynamic programming approach in time polynomial in the number of minimal separators of a graph. It is known that solutions to the perfect phylogeny problem, maximum compatibility problem, and unique perfect phylogeny problem are characterized by minimal triangulations of the partition intersection graph. In this paper, we show that techniques similar to those proposed by Bouchitt'e and Todinca can be used to solve the perfect phylogeny problem with missing data, the two- state maximum compatibility problem with missing data, and the unique perfect phylogeny problem with missing data in time polynomial in the number of minimal separators of the partition intersection graph.

Recommendations

• SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
• scientific article; zbMATH DE number 2102787
• A Polynomial-Time Algorithm for Near-Perfect Phylogeny
• A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
• A linear-time algorithm for the perfect phylogeny haplotype problem
• A novel insight into the perfect phylogeny problem
• Approximation algorithms for tree alignment with a given phylogeny
• Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks

Cited in

(12)

• Research in Computational Molecular Biology
• scientific article; zbMATH DE number 1945176 (Why is no real title available?)
• scientific article; zbMATH DE number 7764113 (Why is no real title available?)
• Approximately counting locally-optimal structures
• Maximal sub-triangulation in pre-processing phylogenetic data
• Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• Finding optimal triangulations parameterized by edge clique cover
• Graph triangulations and the compatibility of unrooted phylogenetic trees
• Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction
• scientific article; zbMATH DE number 6851886 (Why is no real title available?)
• Approximately Counting Locally-Optimal Structures

This page was built for publication: Minimal Triangulation Algorithms for Perfect Phylogeny Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404932)