| Determining a Singleton Attractor of a Boolean Network with Nested Canalyzing Functions. | |
| | |
MedLine Citation:
|
PMID: 21554129 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
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. |
| | |
Authors:
|
Tatsuya Akutsu; Avraham A Melkman; Takeyuki Tamura; Masaki Yamamoto |
Related Documents
:
|
19572269 - Development and validation of the singing voice handicap-10. 11596819 - Self-reported competencies and problems among swedish adolescents: a normative study of... 10846199 - Emergence and preservation of a chronically sick building. 16391509 - The relationship between the biogenetic temperament and character and psychopathology i... 11095039 - How unspecified are disorders of children with a pervasive developmental disorder not o... 15877769 - Ethnic group, acculturation, and psychiatric problems in young immigrants. 16553679 - Effectiveness of an hiv/aids educational programme for chinese nurses. 8980439 - Problems related to the definition of "distal" bypass and "secondary" patency rates. a ... 15529889 - A comparison of dense-to-lean and fixed lean schedules of alternative reinforcement and... |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2011-5-9 |
Journal Detail:
|
Title: Journal of computational biology : a journal of computational molecular cell biology Volume: - ISSN: 1557-8666 ISO Abbreviation: - Publication Date: 2011 May |
Date Detail:
|
Created Date: 2011-5-10 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9433358 Medline TA: J Comput Biol Country: - |
Other Details:
|
Languages: ENG Pagination: - Citation Subset: - |
Affiliation:
|
1 Bioinformatics Center, Institute for Chemical Research, Kyoto University , Kyoto, Japan . |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Recruitment of participants to a clinical trial of botanical therapy for benign prostatic hyperplasi...
Next Document: Natural Products from Garcinia brasiliensis as Leishmania Protease Inhibitors.