Efficiently Calculating Evolutionary Tree Measures Using SAT

DOI10.1007/978-3-642-02777-2_3zbMath1247.68247OpenAlexW2121505045WikidataQ60512131 ScholiaQ60512131MaRDI QIDQ3637154

Katherine St. John, Maria Luisa Bonet

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

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

Related Items

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

Uses Software

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Optimal algorithms for comparing trees with labeled leaves
• On the computational complexity of the rooted subtree prune and regraft distance
• Combining Adaptive Noise and Look-Ahead in Local Search for SAT
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Computing and Combinatorics
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees