Markus Chimani
ABSTRACT
In computational phylogenetics, the problem of constructing a consensus tree or supertree of a given set of rooted input trees can be formalized in different ways. We consider the Minimum Flip Consensus Tree and Minimum Flip Supertree problem, where input trees are transformed into a 0/1/?-matrix, such that each row represents a taxon, and each column represents a subtree membership. For the consensus tree problem, all input trees contain the same set of taxa, and no ?-entries occur. For the supertree problem, the input trees may contain different subsets of the taxa, and unrepresented taxa are coded with ?-entries. In both cases, the goal is to find a perfect phylogeny for the input matrix requiring a minimum number of 0/1-flips, i.e., matrix entry corrections. Both optimization problems are NP-hard.
We present the first efficient Integer Linear Programming (ILP) formulations for both problems, using three distinct characterizations of a perfect phylogeny. Although these three formulations seem to differ considerably at first glance, we show that they are in fact polytope-wise equivalent. Introducing a novel column generation scheme, it turns out that the simplest, purely combinatorial formulation is the most efficient one in practice. Using our framework, it is possible to find exact solutions for instances with ~100 taxa.
- S. Böcker, Q. B. A. Bui, and A. Truss. An improved fixed-parameter algorithm for minimum-flip consensus trees. In Proc. of International Workshop on Parameterized and Exact Computation (IWPEC 2008), volume 5018 of Lect. Notes Comput. Sc., pages 43--54. Springer, 2008. Google Scholar
Digital Library
- D. Chen, L. Diao, O. Eulenstein, D. Fernández-Baca, and M. J. Sanderson. Flipping: A supertree construction method. In Bioconsensus, volume 61 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 135--160. American Mathematical Society, 2003.Google Scholar
- D. Chen, O. Eulenstein, D. Fernández-Baca, and J. G. Burleigh. Improved heuristics for minimum-flip supertree construction. Evol. Bioinform. Online, 2:391--400, 2006.Google ScholarCross Ref
- D. Chen, O. Eulenstein, D. Fernández-Baca, and M. Sanderson. Supertrees by flipping. In Proc. of Conference on Computing and Combinatorics (COCOON 2002), volume 2387 of Lect. Notes Comput. Sc., pages 391--400. Springer, 2002. Google ScholarDigital Library
- D. Chen, O. Eulenstein, D. Fernández-Baca, and M. Sanderson. Minimum-flip supertrees: complexity and algorithms. IEEE/ACM Trans. Comput. Biol. Bioinform., 3(2):165--173, 2006. Google ScholarDigital Library
- W. Day, D. Johnson, and D. Sankoff. The computational complexity of inferring rooted phylogenies by parsimony. Math. Biosci., 81:33--42, 1986.Google ScholarCross Ref
- G. Estabrook, C. Johnson, and F. McMorris. An idealized concept of the true cladistic character. Math. Bioscience, 23:263--272, 1975.Google ScholarCross Ref
- O. Eulenstein, D. Chen, J. G. Burleigh, D. Fernández-Baca, and M. J. Sanderson. Performance of flip supertree construction with a heuristic algorithm. Syst. Biol., 53(2):299--308, Apr 2004.Google ScholarCross Ref
- D. Gusfield. Efficient algorithms for inferring evolutionary trees. Networks, 21:19--28, 1991.Google ScholarCross Ref
- S. Kannan, T. Warnow, and S. Yooseph. Computing the local consensus of trees. SIAM J. Comput., 27(6):1695--1724, 1998. Google ScholarDigital Library
- C. Komusiewicz and J. Uhlmann. A cubic-vertex kernel for flip consensus tree. In Proc. of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008), Leibniz International Proceedings in Informatics, pages 280--291, 2008.Google Scholar
- G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. Discrete Mathematics and Optimization. Wiley-Interscience, 1999.Google Scholar
- M. P. Ng and N. C. Wormald. Reconstruction of rooted trees from subtrees. Discrete Appl. Math., 69(1--2):19--31, 1996. Google ScholarDigital Library
- M. A. Ragan. Phylogenetic inference based on matrix representation of trees. Mol. Phylogenet. Evol., 1(1):53--58, Mar 1992.Google ScholarCross Ref
- C. Semple and M. Steel. A supertree method for rooted trees. Discrete Appl. Math., 105(1--3):147--158, 2000. Google ScholarDigital Library
Index Terms
- Exact ILP solutions for phylogenetic minimum flip problems
Recommendations
Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees
In computational phylogenetics, the problem of constructing a consensus tree for a given set of rooted input trees has frequently been addressed. In this article we study the Minimum-Flip Problem: the input trees are transformed into a binary matrix, ...
Reconstructing Phylogenetic Trees from Multipartite Quartet Systems
AbstractA phylogenetic tree is a graphical representation of an evolutionary history of taxa in which the leaves correspond to the taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a ...
On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems
The aim of this paper is to give a complete picture of approximability for two tree consensus problems which are of particular interest in computational biology: Maximum Agreement SubTree (MAST) and Maximum Compatible Tree (MCT). Both problems take as ...
Comments