Evaluation of properties over phylogenetic trees using stochastic logics.
BACKGROUND
Model checking has been recently introduced as an integrated framework for extracting information of the phylogenetic trees using temporal logics as a querying language, an extension of modal logics that imposes restrictions of a boolean formula along a path of events. The phylogenetic tree is considered a transition system modeling the evolution as a sequence of genomic mutations (we understand mutation as different ways that DNA can be changed), while this kind of logics are suitable for traversing it in a strict and exhaustive way. Given a biological property that we desire to inspect over the phylogeny, the verifier returns true if the specification is satisfied or a counterexample that falsifies it. However, this approach has been only considered over qualitative aspects of the phylogeny.


RESULTS
In this paper, we repair the limitations of the previous framework for including and handling quantitative information such as explicit time or probability. To this end, we apply current probabilistic continuous-time extensions of model checking to phylogenetics. We reinterpret a catalog of qualitative properties in a numerical way, and we also present new properties that couldn't be analyzed before. For instance, we obtain the likelihood of a tree topology according to a mutation model. As case of study, we analyze several phylogenies in order to obtain the maximum likelihood with the model checking tool PRISM. In addition, we have adapted the software for optimizing the computation of maximum likelihoods.


CONCLUSIONS
We have shown that probabilistic model checking is a competitive framework for describing and analyzing quantitative properties over phylogenetic trees. This formalism adds soundness and readability to the definition of models and specifications. Besides, the existence of model checking tools hides the underlying technology, omitting the extension, upgrade, debugging and maintenance of a software tool to the biologists. A set of benchmarks justify the feasibility of our approach.
Department of Computer Science and Systems Engineering (DIIS), Universidad de Zaragoza, C/ María de Luna 1, Zaragoza, 50018, Spain. nrequeno@unizar.es.
José Ignacio
JI
Requeno
Department of Computer Science and Systems Engineering (DIIS), Universidad de Zaragoza, C/ María de Luna 1, Zaragoza, 50018, Spain.
José Manuel
JM
Colom
D000465:Algorithms; D004247:DNA / Q000235:genetics; D016013:Likelihood Functions; D008128:Logic; D008957:Models, Genetic; D015233:Models, Statistical; D009154:Mutation / Q000235:genetics; D010802:Phylogeny; D011336:Probability; D012984:Software; D013269:Stochastic Processes; D013997:Time Factors
D004247:DNA
DNA mutation models; Maximum likelihood; Model checking; Phylogenetics; Stochastic temporal logic