AI Article Synopsis
- The article explores the challenge of finding a singleton attractor in Boolean networks (BNs), a problem that is generally NP-hard, especially for certain subclasses of BNs.
- It introduces an efficient algorithm with a time complexity of O(1.799(n)) for BNs that use nested canalyzing functions and offers a specialized approach for the satisfiability problem in this context.
- Furthermore, the authors present an O(1.619(n)) time algorithm for BNs that consist of chain functions, highlighting that the problem remains NP-hard despite some solvable cases in polynomial time for certain subcategories.
Article Abstract
In this article, we study the problem of finding a singleton attractor for several biologically important subclasses of Boolean networks (BNs). The problem of finding a singleton attractor in a BN is known to be NP-hard in general. For BNs consisting of n nested canalyzing functions, we present an O(1.799(n)) time algorithm. The core part of this development is an O(min(2(k/2) · 2(m/2), 2(k)) · poly(k, m)) time algorithm for the satisfiability problem for m nested canalyzing functions over k variables. For BNs consisting of chain functions, a subclass of nested canalyzing functions, we present an O(1.619(n)) time algorithm and show that the problem remains NP-hard, even though the satisfiability problem for m chain functions over k variables is solvable in polynomial time. Finally, we present an o(2(n)) time algorithm for bounded degree BNs consisting of canalyzing functions.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1089/cmb.2010.0281 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Want AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!