Finding a Periodic Attractor of a Boolean Network

No Thumbnail Available
Files
There are no files associated with this item.
Date
2012
Authors
Akutsu, Tatsuya
Melkman, Avraham A.
Tamura, Takeyuki
Editors
Contact
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
URI (citable link)
DOI (citable link)
ArXiv-ID
International patent number
Link to the license
oops
EU project number
Project
Open Access publication
Collections
Informatik und Informationswissenschaft
Restricted until
Title in another language
Research Projects
Organizational Units
Journal Issue
Publication type
Journal article
Publication status
Published
Published in
IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) ; 9 (2012), 5. - pp. 1410-1421. - ISSN 1545-5963. - eISSN 1557-9964
Abstract
In this paper, we study the problem of finding a periodic attractor of a Boolean network (BN), which arises in computational systems biology and is known to be NP-hard. Since a general case is quite hard to solve, we consider special but biologically important subclasses of BNs. For finding an attractor of period 2 of a BN consisting of $n$ OR functions of positive literals, we present a polynomial time algorithm. For finding an attractor of period 2 of a BN consisting of $n$ AND/OR functions of literals, we present an $O(1.985^n)$ time algorithm. For finding an attractor of a fixed period of a BN consisting of $n$ nested canalyzing functions and having constant treewidth $w$ , we present an $O(n^{2p(w+1)} poly(n))$ time algorithm.
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
Boolean network, periodic attractor, SAT, nested canalyzing function, treewidth
Conference
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690AKUTSU, Tatsuya, Sven KOSUB, Avraham A. MELKMAN, Takeyuki TAMURA, 2012. Finding a Periodic Attractor of a Boolean Network. In: IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB). 9(5), pp. 1410-1421. ISSN 1545-5963. eISSN 1557-9964
BibTex
@article{Akutsu2012Findi-44543,
  year={2012},
  title={Finding a Periodic Attractor of a Boolean Network},
  url={https://www.computer.org/csdl/trans/tb/2012/05/ttb2012051410.html},
  number={5},
  volume={9},
  issn={1545-5963},
  journal={IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)},
  pages={1410--1421},
  author={Akutsu, Tatsuya and Kosub, Sven and Melkman, Avraham A. and Tamura, Takeyuki}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/44543">
    <dc:contributor>Kosub, Sven</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44543"/>
    <dc:language>eng</dc:language>
    <dc:creator>Kosub, Sven</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-14T09:55:28Z</dc:date>
    <dc:contributor>Akutsu, Tatsuya</dc:contributor>
    <dc:creator>Akutsu, Tatsuya</dc:creator>
    <dcterms:abstract xml:lang="eng">In this paper, we study the problem of finding a periodic attractor of a Boolean network (BN), which arises in computational systems biology and is known to be NP-hard. Since a general case is quite hard to solve, we consider special but biologically important subclasses of BNs. For finding an attractor of period 2 of a BN consisting of $n$ OR functions of positive literals, we present a polynomial time algorithm. For finding an attractor of period 2 of a BN consisting of $n$ AND/OR functions of literals, we present an $O(1.985^n)$ time algorithm. For finding an attractor of a fixed period of a BN consisting of $n$ nested canalyzing functions and having constant treewidth $w$ , we present an $O(n^{2p(w+1)} poly(n))$ time algorithm.</dcterms:abstract>
    <dc:creator>Melkman, Avraham A.</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Melkman, Avraham A.</dc:contributor>
    <dc:contributor>Tamura, Takeyuki</dc:contributor>
    <dcterms:title>Finding a Periodic Attractor of a Boolean Network</dcterms:title>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-14T09:55:28Z</dcterms:available>
    <dc:creator>Tamura, Takeyuki</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:issued>2012</dcterms:issued>
  </rdf:Description>
</rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Contact
URL of original publication
https://www.computer.org/csdl/trans/tb/2012/05/ttb2012051410.html
Test date of URL
Examination date of dissertation
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
Yes
Refereed
Yes