Document Open Access Logo

On the Weighted Quartet Consensus Problem

Authors Manuel Lafond, Celine Scornavacca

PDF
Thumbnail PDF

File

LIPIcs.CPM.2017.28.pdf
  • Filesize: 0.68 MB
  • 18 pages

Document Identifiers

Author Details

Manuel Lafond
Celine Scornavacca

Cite As Get BibTex

Manuel Lafond and Celine Scornavacca. On the Weighted Quartet Consensus Problem. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CPM.2017.28

Abstract

In phylogenetics, the consensus problem consists in summarizing a set of phylogenetic trees that all classify the same set of species into a single tree. Several definitions of consensus exist in the literature; in this paper we focus on the Weighted Quartet Consensus problem, a problem  with unknown complexity status so far. Here we prove that the Weighted Quartet Consensus problem is NP-hard and we give a 1/2-factor approximation for this problem.  During the process, we propose a derandomization procedure of a previously known randomized 1/3-factor approximation.  We also investigate the fixed-parameter tractability of this problem.

Subject Classification

Keywords
  • phylogenetic tree
  • consensus tree
  • quartets
  • complexity
  • fixed-parameter tractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alfred V. Aho, Yehoshua Sagiv, Thomas G. Szymanski, and Jeffrey D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comput., 10(3):405-421, 1981. URL: http://dx.doi.org/10.1137/0210030.
  2. Mukul S. Bansal, Jianrong Dong, and David Fernández-Baca. Comparing and aggregating partially resolved trees. Theor. Comput. Sci., 412(48):6634-6652, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.08.027.
  3. Jean-Pierre Barthélemy and Fred R. McMorris. The median procedure for n-trees. J. Classif., 3(2):329-334, 1986. URL: http://dx.doi.org/10.1007/BF01894194.
  4. Vincent Berry, David Bryant, Tao Jiang, Paul Kearney, Ming Li, Todd Wareham, and Haoyong Zhang. A practical algorithm for recovering the best supported edges of an evolutionary tree (extended abstract). In David B. Shmoys, editor, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pages 287-296. ACM/SIAM, 2000. URL: http://dl.acm.org/citation.cfm?id=338219.338265.
  5. Vincent Berry, Tao Jiang, Paul Kearney, Ming Li, and Todd Wareham. Quartet cleaning: Improved algorithms and simulations. In Jaroslav Nešetřil, editor, Proceedings of the 7th Annual European Symposium on Algorithms (ESA 1999), volume 1643 of LNCS, pages 313-324. Springer Berlin Heidelberg, 1999. URL: http://dx.doi.org/10.1007/3-540-48481-7_28.
  6. David Bryant. Building trees, hunting for trees, and comparing trees. PhD thesis, University of Canterbury, New Zealand, 1997. URL: http://hdl.handle.net/10092/7914.
  7. David Bryant. A classification of consensus methods for phylogenetics. In Melvin F. Janowitz, François-Joseph Lapointe, Fred R. McMorris, Boris Mirkin, and Fred S. Roberts, editors, Proceedings of DIMACS Working Group Meetings on Bioconsensus, volume 61 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 163-184. Americal Mathematical Society, 2003. URL: http://dx.doi.org/10.1090/dimacs/061/11.
  8. David Bryant and Mike Steel. Constructing optimal trees from quartets. J. Algorithms, 38(1):237-259, 2001. URL: http://dx.doi.org/10.1006/jagm.2000.1133.
  9. Jaroslaw Byrka, Sylvain Guillemot, and Jesper Jansson. New results on optimizing rooted triplets consistency. Discrete Appl. Math., 158(11):1136-1147, 2010. URL: http://dx.doi.org/10.1016/j.dam.2010.03.004.
  10. Maw-Shang Chang, Chuang-Chieh Lin, and Peter Rossmanith. New fixed-parameter algorithms for the minimum quartet inconsistency problem. Theory Comput. Syst., 47(2):342-367, 2010. URL: http://dx.doi.org/10.1007/s00224-009-9165-y.
  11. Richard Cole and Ramesh Hariharan. Dynamic LCA queries on trees. SIAM J. Comput., 34(4):894-923, 2005. URL: http://dx.doi.org/10.1137/S0097539700370539.
  12. Joseph Felsenstein. Inferring phylogenies. Sinauer Associates Sunderland, 2004. Google Scholar
  13. Zvi Galil and Nimrod Megiddo. Cyclic ordering is NP-complete. Theor. Comput. Sci., 5(2):179-182, 1977. URL: http://dx.doi.org/10.1016/0304-3975(77)90005-6.
  14. Jens Gramm and Rolf Niedermeier. Minimum quartet inconsistency is fixed parameter tractable. In Amihood Amir, editor, Proceedings of the 12th Annual Symposium of Combinatorial Pattern Matching (CPM 2001), volume 2089 of LNCS, pages 241-256. Springer Berlin Heidelberg, 2001. URL: http://dx.doi.org/10.1007/3-540-48194-X_23.
  15. Jesper Jansson. On the complexity of inferring rooted evolutionary trees. Electron. Notes Discrete Math., 7:50-53, 2001. URL: http://dx.doi.org/10.1016/S1571-0653(04)00222-7.
  16. Tao Jiang, Paul Kearney, and Ming Li. A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application. SIAM J. Comput., 30(6):1942-1961, 2001. URL: http://dx.doi.org/10.1137/S0097539799361683.
  17. Timothy Margush and Fred R. McMorris. Consensus n-trees. Bull. Math. Biol., 43(2):239-244, 1981. URL: http://dx.doi.org/10.1007/BF02459446.
  18. Fred R. McMorris, David B. Meronk, and Dean A. Neumann. A view of some consensus methods for trees. In Joseph Felsenstein, editor, Proceedings of the NATO Advanced Study Institute on Numerical Taxonomy, volume 1 of NATO Advanced Science Institutes Series, Series G: Ecological Sciences, pages 122-126. Springer, 1983. URL: http://dx.doi.org/10.1007/978-3-642-69024-2_18.
  19. Siavash Mirarab. Novel scalable approaches for multiple sequence alignment and phylogenomic reconstruction. PhD thesis, University of Texas at Austin, 2015. URL: http://hdl.handle.net/2152/31377.
  20. Siavash Mirarab, Rezwana Reaz, Md. Shamsuzzoha Bayzid, Théo Zimmermann, M. Shel Swenson, and Tandy Warnow. ASTRAL: genome-scale coalescent-based species tree estimation. Bioinformatics, 30(17):i541-i548, 2014. URL: http://dx.doi.org/10.1093/bioinformatics/btu462.
  21. António Morgado and Joao Marques-Silva. A pseudo-boolean solution to the maximum quartet consistency problem, 2008. URL: http://arxiv.org/abs/0805.0202.
  22. António Morgado and Joao Marques-Silva. Combinatorial optimization solutions for the maximum quartet consistency problem. Fundam. Inform., 102(3-4):363-389, 2010. URL: http://dx.doi.org/10.3233/FI-2010-311.
  23. Robert R. Sokal and F. James Rohlf. Taxonomic congruence in the leptopodomorpha re-examined. Syst. Zool., 30(3):309-325, 1981. URL: http://dx.doi.org/10.2307/2413252.
  24. Michael Steel. The complexity of reconstructing trees from qualitative characters and subtrees. J. Classif., 9(1):91-116, 1992. URL: http://dx.doi.org/10.1007/BF02618470.
  25. Gang Wu, Jia-Huai You, and Guohui Lin. A lookahead branch-and-bound algorithm for the maximum quartet consistency problem. In Rita Casadio and Gene Myers, editors, Proceedings of the 5th International Workshop on Algorithms in Bioinformatics (WABI 2005), volume 3692 of LNCS, pages 65-76. Springer, Springer, 2005. URL: http://dx.doi.org/10.1007/11557067_6.
  26. Gang Wu, Jia-Huai You, and Guohui Lin. Quartet-based phylogeny reconstruction with answer set programming. IEEE/ACM Trans. Comput. Biol. Bioinform., 4(1):139-152, 2007. URL: http://dx.doi.org/10.1109/TCBB.2007.1008.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact