Idioma:

Efficiently calculating evolutionary tree measures using SAT

Bonet Carbonell, M. Luisa ; John, Katherine St

Texto completo disponível

Citações Citado por

Título:
Efficiently calculating evolutionary tree measures using SAT
Autor: Bonet Carbonell, M. Luisa ; John, Katherine St
Assuntos: Evolució (Biologia) ; Evolution (Biology) ; Evolutionary tree measures ; Informàtica ; Informàtica teòrica ; Mathematical models ; Models matemàtics ; SAT solvers ; Àrees temàtiques de la UPC
Descrição: 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-hard, and effcient algorithms are needed to compute and approximate these measures. We encode these as a Boolean formula such that two trees have hybridization number k (or rSPR distance k) if and only if the corresponding formula is satisfiable. We use state-of-the-art SAT solvers to determine if the formula encoding the measure has a satisfying assignment. Our encoding also provides a rich source of real-world SAT instances, and we include a comparison of several recent solvers (minisat, adaptg2wsat, novelty+p, Walksat, March KS and SATzilla).
Data de criação/publicação: 2009
Idioma: Inglês

Links

Voltar para lista de resultados