Miguel Miranda, Inês Lynce and Vasco Manquinho
Phylogenetic inference concerns the construction of the most probable tree of evolution, taking into account the knowledge about organisms we have at our disposal. There are various inference methods for building a phylogenetic tree, each with its set of assumptions about what can happen in Nature. Assumptions limit the expressiveness of the methods, but are necessary for making them viable to use. More recently, computational methods are being used to validate results obtained from manual methods. Computational methods allow to address problems that require the analysis of larger sets of data in order to construct more complete phylogenies.
In this paper we propose new Pseudo-Boolean Optimization (PBO) formulations, a well known extension of Propositional Satisfiability (SAT), in order to solve the Maximum Compatibility (MC) problem. Assuming that each organism is associated with a set of characteristics, the goal in the MC problem is to find a phylogenetic tree such that the maximum number of characteristics are compatible. Our contribution is a set of new PBO formulations that improve on the performance of the state of the art tool. Comparative results, using real and generated instances, show that the proposed implementations allow the resolution of problem instances with twice the size of the state of the art implementation.
Phylogenetic Inference, Maximum Compatibility, Pseudo-Boolean Optimization
All downloadable archives contain a README file with more insight about their content.
To use the generator you should pass it a model, the number of species and the number of characteristics, for example:
[~/]$ phyloGenpb [# species] [# characteristics] < ./random.model > ./instance.raw
To use any of the translators you should just pass them an instance (like the ones made available in the links above), for example:
[~/]$ translator_pbo < ./instance.raw > ./instance.pbo
[~/]$ raw2asp < ./instance.raw > ./instance.asp
To solve an instance with minisatp, just pass the instance to the solver, for example:
[~/]$ minisatp ./instance.pbo
To solve an instance with clingo, pass the instance and the program to the solver, for example:
[~/]$ clingo --compat ./instance.asp ./program.lp
If you have any comments or questions, please .