Efficiently Calculating Evolutionary Tree Measures Using SAT

DOI10.1007/978-3-642-02777-2_3MaRDI QIDQ3637154zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Maria Luisa Bonet, Katherine St. John

Publication date 7 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02777-2_3

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Problems related to evolution (92D15)

Recommendations

• scientific article; zbMATH DE number 1302179
• Better practical algorithms for rSPR distance and hybridization number
• Minimizing phylogenetic number to find good evolutionary trees
• scientific article; zbMATH DE number 1541304
• scientific article; zbMATH DE number 1088267

Cites work

• Combining Adaptive Noise and Look-Ahead in Local Search for SAT
• Computing and Combinatorics
• Computing the minimum number of hybridization events for a consistent evolutionary history
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• March\_dl: adding adaptive heuristics and a new branching strategy
• On the complexity of comparing evolutionary trees
• On the computational complexity of the rooted subtree prune and regraft distance
• Optimal algorithms for comparing trees with labeled leaves
• SATzilla: portfolio-based algorithm selection for SAT
• Subtree transfer operations and their induced metrics on evolutionary trees
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing

Cited in

(6)

• Gene tree reconciliation including transfers with replacement is NP-hard and FPT
• Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope
• Empirical study of the anatomy of modern SAT solvers
• The agreement distance of unrooted phylogenetic networks
• Extending Clause Learning of SAT Solvers with Boolean Gröbner Bases
• On CDCL-Based Proof Systems with the Ordered Decision Strategy

Describes a project that uses

Uses Software

• Walksat
• fastDNAml
• TreeJuxtaposer
• MiniSat
• SATzilla
• UBCSAT
• RIATA-HGT

This page was built for publication: Efficiently Calculating Evolutionary Tree Measures Using SAT

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