Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 6
Encontrada(s) 1 página(s)

Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Phylogenetic analysis using an SMV tool

  • Requeno, J.I.
  • Blanco, R.
  • De Miguel Casado, Gregorio
  • Colom, J.M.
The need for general methods to verify biological properties in phylogenetics motivates research in formal frameworks so that biologists can focus their efforts exclusively in evolution modeling and property specification. Model checking is proposed to this end. Three pillars found this approach: modeling evolution dynamics as transition systems; specifying phylogenetic properties using temporal logic formulae; and verifying the former by means of automated computer tools. As prominent advantages for studying biological properties under our approach, different models of evolution can be considered, complex properties can be specified as the logical composition of others, and the refinement of unfulfilled properties as well as the discovery of new ones can be undertaken by exploiting the results of verification. Preliminary experimental results using the Cadence Symbolic Model Verifier support the feasibility of the methodology.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Speeding Up Phylogenetic Model Checking

  • Requeno, J.I.
  • Colom, J.M.
Model checking is a generic and formal technique that the authors have proposed for the study of properties that emerge from the biological labeling of the states defined over the phylogenetic tree [3] [10]. This strategy allows us to use generic software tools already present in the industry. However, the performance of traditional model checking is penalized when scaling the system for large phylogenies. To this end, two strategies are presented here. The first one consists of partitioning the phylogenetic tree into a set of related subproblems so as to speed up the computation time and distribute the memory consumption. The second strategy is based on uncoupling the information associated to each state of the phylogenetic tree (mainly, the DNA sequence) and exporting it to an external tool for the management of large information systems. The integration of all these approaches outperformed the results of monolithic model checking and helped us to execute the verification of properties in a real phylogenetic tree.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Temporal logics for phylogenetic analysis via model checking

  • Requeno, J.I.
  • De Miguel Casado, G.
  • Blanco, R.
  • Colom, J.M.
The need for general-purpose algorithms for studying biological properties in phylogenetics motivates research into formal verification frameworks. Researchers can focus their efforts exclusively on evolution trees and property specifications. To this end, model checking, a mature automated verification technique originating in computer science, is applied to phylogenetic analysis. Our approach is based on three cornerstones: a logical modeling of the evolution with transition systems; the specification of both phylogenetic properties and trees using flexible temporal logic formulas; and the verification of the latter by means of automated computer tools. The most conspicuous result is the inception of a formal framework which allows for a symbolic manipulation of biological data (based on the codification of the taxa). Additionally, different logical models of evolution can be considered, complex properties can be specified in terms of the logical composition of others, and the refinement of unfulfilled properties as well as the discovery of new properties can be undertaken by exploiting the verification results. Some experimental results using a symbolic model verifier support the feasibility of the approach.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Sliced model checking for phylogenetic analysis

  • Requeno, J.I.
  • Blanco, R.
  • De Miguel Casado, Gregorio
  • Colom, J.M.
Model checking provides a powerful and flexible formal framework to state and verify biological properties on phylogenies. However, current model checking techniques fail to scale up the big amount of biological information relevant to each state of the system. This fact motivates the development of novel cooperative algorithms and slicing techniques that distribute not the graph structure of a phylogenetic system but the state information contained in its nodes.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Compact representation of biological sequences using set decision diagrams

  • Requeno, J.I.
  • Colom, J.M.
Nowadays, the exponential availability of biological sequences and the complexity of the computational methods that use them as input motivate the research of new compact representations. To this end, we propose an alternative method for storing sets of sequences based on set decision diagrams instead of classical compression techniques. The set decision diagrams are an extension of the reduced ordered binary decision diagrams, a graph data structure used as a symbolic compact representation of sets or relations between sets. Some experiments with genes of the mitochondrion DNA support the feasibility of our approach.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Timed and Probabilistic Model Checking over Phylogenetic Trees

  • Requeno, José Ignacio
  • Colom, José Manuel
Model checking is a generic verification technique that allows the phylogeneticist to focus on models and specifications instead of on implementation issues. Phylogenetic trees are considered as transition systems over which we interrogate phylogenetic questions written as formulas of temporal logic. Nonetheless, standard logics become insuficient for the usual practices of phylogenetic analysis since they don't allow the inclusion of explicit time and probabilities. The aim of this paper is to extend the application of model checking techniques beyond qualitative phylogenetic properties and adapt the existing logical extensions and tools to the field of phylogeny. The introduction of time and probabilities in phylogenetic specifications is motivated by a real example.