Algorithms for Finding Small Attractors in Boolean Networks. (12th April 2007)

• Record Type: Journal Article
• Authors: Zhang, Shu-Qin; Hayashida, Morihiro; Akutsu, Tatsuya; Ching, Wai-Ki; Ng, Michael K.
• Other Names: Dougherty Edward R. Academic Editor.
• Is Part Of: EURASIP journal on bioinformatics and systems biology. Volume 2007(2007)
• Publication Date: 2007-04-12
• Subjects: Bioinformatics -- Periodicals; Systems biology -- Periodicals; Systems Biology; Signal Processing, Computer-Assisted; Bio-informatique; Biologie systémique; Bioinformatics; Systems biology; Systems Biology; Bioinformatics; Electronic journals; Periodical; Fulltext; Internet Resources; Periodicals; Periodicals; 570.285
• DOI: 10.1155/2007/20180
• Languages: English
• ISSNs: 1687-4145

Abstract

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 inO ( 1.19 n ) time forK = 2, which is much faster than the naiveO ( 2 n ) time algorithm, wheren is the number of genes andK 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.