skip to main content
article

Quartet-Based Phylogeny Reconstruction with Answer Set Programming

Published: 01 January 2007 Publication History

Abstract

In this paper, a new representation is presented for the Maximum Quartet Consistency (MQC) problem, where solving the MQC problem becomes searching for an ultrametric matrix that satisfies a maximum number of given quartet topologies. A number of structural properties of the MQC problem in this new representation are characterized through formulating into answer set programming, a recent powerful logic programming tool for modeling and solving search problems. Using these properties, a number of optimization techniques are proposed to speed up the search process. The experimental results on a number of simulated data sets suggest that the new representation, combined with answer set programming, presents a unique perspective to the MQC problem.

References

[1]
{1} H. Bandelt and A. Dress, "Reconstructing the Shape of a Tree from Observed Dissimilarity Data," Advances in Applied Math., vol. 7, pp. 309-343, 1986.
[2]
{2} A. Ben-Dor, B. Chor, D. Graur, R. Ophir, and D. Pelleg, "From Four-Taxon Trees to Phylogenies: The Case of Mammalian Evolution," Proc. Fourth Ann. Int'l Computing and Combinatorics Conf. (RECOMB), pp. 9-19, 1998.
[3]
{3} V. Berry, D. Bryant, T. Jiang, P. Kearney, M. Li, T. Wareham, and H. Zhang, "A Practical Algorithm for Recovering the Best Supported Edges of an Evolutionary Tree," Proc. 11th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 287-296, Jan. 2000.
[4]
{4} V. Berry, T. Jiang, P.E. Kearney, M. Li, and H.T. Wareham, "Quartet Cleaning: Improved Algorithms and Simulations," Proc. Seventh Ann. European Symp. Algorithms (ESA '99), pp. 313-324, 1999.
[5]
{5} B. Borchers and J. Furman, "A Two-Phase Exact Algorithm for MAX-SAT and Weighted MAX-SAT Problems," J. Combinatorial Optimization, vol. 2, pp. 299-306, 1999.
[6]
{6} D.R. Brooks, E. Erdem, J.W. Minett, and D. Ringe, "Character-Based Cladistics and Answer Set Programming," Proc. Seventh Int'l Symp. Practical Aspects of Declarative Languages (PADL '05), pp. 37-51, 2005.
[7]
{7} M.C.H. Dekker, "Reconstruction Methods for Derivation Trees," master's thesis, Vrije Univ., Amsterdam, 1986.
[8]
{8} P. Erdos, M. Steel, L. Szekely, and T. Warnow, "A Few Logs Suffice to Build (Almost) All Trees (Part 1)," Random Structures and Algorithms, vol. 14, pp. 153-184, 1999.
[9]
{9} P.L. Erdos, M.A. Steel, L.A. Szekely, and T.J. Warnow, "Inferring Big Trees from Short Sequences," Proc. Int'l Congress on Automata, Languages, and Programming, pp. 827-837, 1997.
[10]
{10} J. Felsenstein, "The Number of Evolutionary Trees," Systematic Zoology, vol. 27, pp. 27-33, 1978.
[11]
{11} M. Gelfond and V. Lifschitz, "The Stable Model Semantics for Logic Programming," Proc. Fifth Int'l Conf. Logic Programming, pp. 1070-1080, 1988.
[12]
{12} I.P. Gent, P. Prosser, B.M. Smith, and W. Wei, "Supertree Construction with Answer Set Programming," Proc. Ninth Int'l Conf. Principles and Practice of Constraint Programming (CP '03), pp. 837-841, 2003.
[13]
{13} J. Gramm and R. Niedermeier, "A Fixed-Parameter Algorithm for Minimum Quartet Inconsistency," J. Computer and System Sciences, vol. 67, pp. 723-741, 2003.
[14]
{14} D. Gusfield, Algorithms on Strings, Trees, and Sequences. Cambridge, 1997.
[15]
{15} T. Jiang, P.E. Kearney, and M. Li, "Orchestrating Quartets: Approximation and Data Correction," Proc. 39th Symp. Foundations of Computer Science, pp. 416-425, 1998.
[16]
{16} T. Jiang, P.E. Kearney, and M. Li, "Some Open Problems in Computational Molecular Biology," J. Algorithms, vol. 34, pp. 194- 201, 2000.
[17]
{17} Y. Lierler and M. Maratea, "Cmodels-2: SAT-Based Answer Set Solver Enhanced to Non-Tight Programs," Proc. Seventh Int'l Conf. Logic Programming and Nonmonotonic Reasoning (LPNMR '04), pp. 346-350, 2004.
[18]
{18} F. Lin and Y. Zhao, "ASSAT: Computing Answer Sets of a Logic Program by SAT Solvers," Artificial Intelligence, vol. 157, pp. 115- 137, 2004.
[19]
{19} M.W. Moskewicz, C.F. Madigan, Y. Zhao, L. Zhang, and S. Malik, "Chaff: Engineering an Efficient SAT Solver," Proc. 38th Design Automation Conf. (DAC '01), pp. 530-535, 2001.
[20]
{20} I. Niemelä, "Logic Programs with Stable Model Semantics as a Constraint Programming Paradigm," Annals of Math. and Artificial Intelligence, vol. 25, pp. 241-273, 1999.
[21]
{21} D. Pelleg, "Algorithms for Constructing Phylogenies from Quartets," master's thesis, Israel Inst. of Technology, 1998.
[22]
{22} S. Sattath and A. Tversky, "Additive Similarity Trees," Psychometrika , vol. 42, pp. 319-345, 1977.
[23]
{23} P. Simons, "Smodels: An Implementation of the Stable Model Semantics for Logic Programs," http://www.tcs.hut.fi/Software /smodels/, 2000.
[24]
{24} M. Steel, "The Complexity of Reconstructing Trees from Qualitative Characters and Subtrees," J. Classification, vol. 9, pp. 91-116, 1992.
[25]
{25} K. Strimmer and A. von Haeseler, "Quartet Puzzling: A Quartet Maximum-Likelihood Method for Reconstructing Tree Topologies," Molecular Biology and Evolution, vol. 13, pp. 964-969, 1996.
[26]
{26} Z. Xing and W. Zhang, "MaxSolver: An Efficient Exact Algorithm for (Weighted) Maximum Satisfiability," Artificial Intelligence, vol. 164, pp. 47-60, 2005.
[27]
{27} J. You, G. Liu, L. Yuan, and C. Onuczko, "Lookahead in Smodels Compared to Local Consistencies in CSP," Proc. Eighth Int'l Conf. Logic Programming and Nonmonotonic Reasoning (LPNMR '05), pp. 266-278, 2005.
[28]
{28} H. Zhang, "SATO: An Efficient Propositional Prover," Proc. Int'l Conf. Automated Deduction, pp. 272-275, 1997.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics
IEEE/ACM Transactions on Computational Biology and Bioinformatics  Volume 4, Issue 1
January 2007
160 pages

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 January 2007
Published in TCBB Volume 4, Issue 1

Author Tags

  1. Answer Set Programming (ASP)
  2. Maximum Quartet Consistency (MQC)
  3. Phylogeny
  4. quartet
  5. ultrametric matrix.

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)1
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Exploring lifeDeclarative Logic Programming10.1145/3191315.3191323(359-412)Online publication date: 1-Sep-2018
  • (2017)A semantic model for action-based adaptive securityProceedings of the Symposium on Applied Computing10.1145/3019612.3019755(1130-1135)Online publication date: 3-Apr-2017
  • (2011)Fast error-tolerant quartet phylogeny algorithmsProceedings of the 22nd annual conference on Combinatorial pattern matching10.5555/2018243.2018259(147-161)Online publication date: 27-Jun-2011
  • (2010)Combinatorial Optimization Solutions for the Maximum Quartet Consistency ProblemFundamenta Informaticae10.5555/1890507.1890513102:3-4(363-389)Online publication date: 1-Aug-2010
  • (2008)The ultrametric constraint and its application to phylogeneticsJournal of Artificial Intelligence Research10.5555/1622673.162269632:1(901-938)Online publication date: 1-Aug-2008
  • (2007)Faster phylogenetic inference with MXGProceedings of the 14th international conference on Logic for programming, artificial intelligence and reasoning10.5555/1779419.1779450(423-437)Online publication date: 15-Oct-2007
  • (2007)Faster Phylogenetic Inference with MXGLogic for Programming, Artificial Intelligence, and Reasoning10.1007/978-3-540-75560-9_31(423-437)Online publication date: 15-Oct-2007

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media