Algorithms for finding small attractors in boolean networks

Shu Qin Zhang*, Morihiro Hayashida, Tatsuya Akutsu, Wai Ki Ching, Kwok Po NG

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

59 Citations (Scopus)

Abstract

A Boolean network is a model used to study the interactions between different genes in genetic regulatory networks. In this paper, we present several algorithms using gene ordering and feedback vertex sets to identify singleton attractors and small attractors in Boolean networks. We analyze the average case time complexities of some of the proposed algorithms. For instance, it is shown that the outdegree-based ordering algorithm for finding singleton attractors works in O( 1.19 n) time for K=2, which is much faster than the naive O( 2n) time algorithm, where n is the number of genes and K is the maximum indegree. We performed extensive computational experiments on these algorithms, which resulted in good agreement with theoretical results. In contrast, we give a simple and complete proof for showing that finding an attractor with the shortest period is NP-hard.

Original languageEnglish
Article number20180
JournalEurasip Journal on Bioinformatics and Systems Biology
Volume2007
DOIs
Publication statusPublished - 2007

Scopus Subject Areas

  • Biochemistry, Genetics and Molecular Biology(all)
  • Computer Science Applications
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Algorithms for finding small attractors in boolean networks'. Together they form a unique fingerprint.

Cite this