Busca avançada
Ano de início
Entree


Finding Attractors in Biological Models Based on Boolean Dynamical Systems Using Hitting Set

Texto completo
Autor(es):
Tovar, Carlos R. P. ; Araujo, Eloi ; Carastan-Santos, Danilo ; Martins-, David C., Jr. ; Rozante, Luiz C. S. ; IEEE
Número total de Autores: 6
Tipo de documento: Artigo Científico
Fonte: 2019 IEEE 19TH INTERNATIONAL CONFERENCE ON BIOINFORMATICS AND BIOENGINEERING (BIBE); v. N/A, p. 5-pg., 2019-01-01.
Resumo

Boolean networks are discrete-time dynamic systems that have been used as a model for a wide range of applications in different areas, especially in Systems Biology. The analysis of Boolean networks includes the search for attractors, which may represent important biological conditions such as gene expression patterns in models of gene regulatory networks, among others. Attractors can be found through exploring the network paths by achieving the solution to the SAT problem, which is known to be NP-complete. In this paper, we propose an approach to find all attractors by first transforming the corresponding instance of the SAT problem to a Hitting Set instance in linear time through a new direct linear reduction. Finally, the instance of the Hitting Set problem is solved by applying a fast parallel algorithm implemented in GPU. As a proof of principle, we tested the method for Boolean networks with 3 and 4 variables, returning the result in about 3 seconds and 9 hours respectively. However, for larger networks the execution time grows substantially due to the algorithm used in the Hitting Set problem solver. But the result achieved for networks with 3 and 4 variables encourages improvements in the method for dealing with large-scale Boolean networks, specially by incorporating some parameter restrictions based on prior information about the state diagram transition graphs structure and optimizing the method by means of dynamic programming and parallelism. (AU)

Processo FAPESP: 15/01587-0 - Armazenagem, modelagem e análise de sistemas dinâmicos para aplicações em e-Science
Beneficiário:João Eduardo Ferreira
Modalidade de apoio: Auxílio à Pesquisa - Programa eScience e Data Science - Temático