Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Efficiently calculating evolutionary tree measures using SAT

Autor
Bonet, M.; St. John, K.
Tipus d'activitat
Article en revista
Revista
Lecture notes in computer science
Data de publicació
2009
Volum
5584
Pàgina inicial
4
Pàgina final
17
DOI
https://doi.org/10.1007/978-3-642-02777-2 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/12674 Obrir en finestra nova
Resum
We develop techniques to calculate important measures in evolutionary biology by encoding to CNF formulas and using powerful SAT solvers. Comparing evolutionary trees is a necessary step in tree reconstruction algorithms, locating recombination and lateral gene transfer, and in analyzing and visualizing sets of trees. We focus on two popular comparison measures for trees: the hybridization number and the rooted subtree-prune-and-regraft (rSPR) distance. Both have recently been shown to be NP-har...
Citació
Bonet, M.; John, K. Efficiently calculating evolutionary tree measures using SAT. "Lecture notes in computer science", 2009, vol. 5584, p. 4-17.
Grup de recerca
LOGPROG - Lògica i Programació

Participants

Arxius