research-article

Exact ILP solutions for phylogenetic minimum flip problems

Authors:

Markus Chimani,

Sebastian BöckerAuthors Info & Claims

BCB '10: Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology

Pages 147 - 153

https://doi.org/10.1145/1854776.1854800

Published: 02 August 2010 Publication History

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.

References

[1]

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.

Digital Library

[2]

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.

[3]

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.

[4]

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.

Digital Library

[5]

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.

Digital Library

[6]

W. Day, D. Johnson, and D. Sankoff. The computational complexity of inferring rooted phylogenies by parsimony. Math. Biosci., 81:33--42, 1986.

[7]

G. Estabrook, C. Johnson, and F. McMorris. An idealized concept of the true cladistic character. Math. Bioscience, 23:263--272, 1975.

[8]

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.

[9]

D. Gusfield. Efficient algorithms for inferring evolutionary trees. Networks, 21:19--28, 1991.

[10]

S. Kannan, T. Warnow, and S. Yooseph. Computing the local consensus of trees. SIAM J. Comput., 27(6):1695--1724, 1998.

Digital Library

[11]

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.

[12]

G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. Discrete Mathematics and Optimization. Wiley-Interscience, 1999.

[13]

M. P. Ng and N. C. Wormald. Reconstruction of rooted trees from subtrees. Discrete Appl. Math., 69(1--2):19--31, 1996.

Digital Library

[14]

M. A. Ragan. Phylogenetic inference based on matrix representation of trees. Mol. Phylogenet. Evol., 1(1):53--58, Mar 1992.

[15]

C. Semple and M. Steel. A supertree method for rooted trees. Discrete Appl. Math., 105(1--3):147--158, 2000.

Digital Library

Cited By

Fernández-Baca DLiu L(2019)Tree Compatibility, Incomplete Directed Perfect Phylogeny, and Dynamic Graph Connectivity: An Experimental StudyAlgorithms10.3390/a1203005312:3(53)Online publication date: 28-Feb-2019
https://doi.org/10.3390/a12030053
Malikic SMehrabadi FCiccolella SRahman MRicketts CHaghshenas ESeidman DHach FHajirasouliha ISahinalp S(2019)PhISCS: a combinatorial approach for subperfect tumor phylogeny reconstruction via integrative use of single-cell and bulk sequencing dataGenome Research10.1101/gr.234435.11829:11(1860-1877)Online publication date: 18-Oct-2019
https://doi.org/10.1101/gr.234435.118
Gusfield D(2019)Integer Linear Programming in Computational and Systems Biology10.1017/9781108377737Online publication date: 31-May-2019
https://doi.org/10.1017/9781108377737
Show More Cited By

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
Abstract
A 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

BCB '10: Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology

August 2010

705 pages

ISBN:9781450304382

DOI:10.1145/1854776

General Chairs:
Aidong Zhang
SUNY at Buffalo
,
Mark Borodovsky
Georgia Tech
,
Program Chairs:
Gultekin Ozsoyoglu
Case Western Reserve University
,
Armin Mikler
University of North Texas

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGBio: ACM Special Interest Group on Bioinformatics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 August 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

BCB'10

Sponsor:

SIGBio

BCB'10: ACM International Conference on Bioinformatics and Computational Biology

August 2 - 4, 2010

New York, Niagara Falls

Acceptance Rates

Overall Acceptance Rate 254 of 885 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
116
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fernández-Baca DLiu L(2019)Tree Compatibility, Incomplete Directed Perfect Phylogeny, and Dynamic Graph Connectivity: An Experimental StudyAlgorithms10.3390/a1203005312:3(53)Online publication date: 28-Feb-2019
https://doi.org/10.3390/a12030053
Malikic SMehrabadi FCiccolella SRahman MRicketts CHaghshenas ESeidman DHach FHajirasouliha ISahinalp S(2019)PhISCS: a combinatorial approach for subperfect tumor phylogeny reconstruction via integrative use of single-cell and bulk sequencing dataGenome Research10.1101/gr.234435.11829:11(1860-1877)Online publication date: 18-Oct-2019
https://doi.org/10.1101/gr.234435.118
Gusfield D(2019)Integer Linear Programming in Computational and Systems Biology10.1017/9781108377737Online publication date: 31-May-2019
https://doi.org/10.1017/9781108377737
Gusfield DKühne O(2019)Integer Linear Programming in Computational Biology: Overview of ILP, and New Results for Traveling Salesman Problems in BiologyLandscape Theories10.1007/978-3-030-10837-3_15(373-404)Online publication date: 9-Apr-2019
https://doi.org/10.1007/978-3-030-10837-3_15
El-Kebir M(2018)SPhyR: tumor phylogeny estimation from single-cell sequencing data under loss and errorBioinformatics10.1093/bioinformatics/bty58934:17(i671-i679)Online publication date: 8-Sep-2018
https://doi.org/10.1093/bioinformatics/bty589
KOPONEN LOIKARINEN EJANHUNEN TSÄILÄ L(2015)Optimizing phylogenetic supertrees using answer set programmingTheory and Practice of Logic Programming10.1017/S147106841500026515:4-5(604-619)Online publication date: 3-Sep-2015
https://doi.org/10.1017/S1471068415000265
Brinkmeyer MGriebel TBöcker S(2012)FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial TimeAlgorithmica10.1007/s00453-012-9698-367:2(142-160)Online publication date: 11-Oct-2012
https://doi.org/10.1007/s00453-012-9698-3
Komusiewicz CUhlmann J(2012)A Cubic-Vertex Kernel for Flip Consensus TreeAlgorithmica10.1007/s00453-012-9663-168:1(81-108)Online publication date: 26-Jun-2012
https://doi.org/10.1007/s00453-012-9663-1
Brinkmeyer MGriebel TBöcker S(2011)FlipCut supertreesProceedings of the 17th annual international conference on Computing and combinatorics10.5555/2033094.2033098(37-48)Online publication date: 14-Aug-2011
https://dl.acm.org/doi/10.5555/2033094.2033098
Brinkmeyer MGriebel TBöcker S(2011)FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial TimeComputing and Combinatorics10.1007/978-3-642-22685-4_4(37-48)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22685-4_4

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents