On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we consider the problem of inferring a Boolean network (BN) from a given set of singleton attractors, where it is required that the resulting BN has the same set of singleton attractors as the given one. We show that the problem can be solved in linear time if the number of singleton attractors is at most two and each Boolean function is restricted to be a conjunction or disjunction of literals. We also show that the problem can be solved in polynomial time if more general Boolean functions can be used. In addition to the inference problem, we study two network completion problems from a given set of singleton attractors: adding the minimum number of edges to a given network, and determining Boolean functions to all nodes when only network structure of a BN is given. In particular, we show that the latter problem cannot be solved in polynomial time unless P=NP, by means of a polynomial-time Turing reduction from the complement of the another solution problem for the Boolean satisfiability problem.

• The Institute of Electronics, Information and Communication Engineersの論文

著者

• Ching Wai-ki

  Department Of Mathematics The University Of Hong Kong

• Tamura Takeyuki

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Jiang Hao

  Department Of Bioprocess Development

• Akutsu Tatsuya

  Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.

• JIANG Hao

  Department of Mathematics, Renmin University of China

関連論文

• Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
• Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences(Discrete Mathematics and Its Applications)
• A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
• Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints(Discrete Mathematics and Its Applications)
• The Potential Cardioprotective Effects of Hydrogen in Irradiated Mice
• Back-Illuminated GaN Metal-Semiconductor-Metal UV Photodetector With High Internal Gain : Semiconductors
• Optical Absorption and Photoluminescence Studies of n-type GaN
• GaN Metal-Semiconductor-Metal UV Photodetector with Recessed Electrodes : Semiconductors
• Inferring pedigree graphs from genetic distances
• Integer Programming and Dynamic Programming-based Methods of Optimizing Control Policy in Probabilistic Boolean Networks with Hard Constraints
• Hardness Results on Local Multiple Alignment of Biological Sequences
• 1P-279 酸化ストレス下におけるアポトーシス制御機構の数理的解明(放射線生物/活性酸素,第46回日本生物物理学会年会)
• Efficient Computation of Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
• Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms
• Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks
• On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
• Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics
• Message from the Editor-in-Chief
• Message from the Editor-in-Chief
• Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
• A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
• A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
• Message from the Editor-in-Chief
• Message from the Editor-in-Chief
• Hardness Results on Local Multiple Alignment of Biological Sequences
• Kernel Methods for Chemical Compounds: From Classification to Design
• Conservation Laws and Symmetries in Competitive Systems
• Measuring the Similarity of Protein Structures Using Image Compression Algorithms
• Investigation of the biosynthesis of the pipecolate moiety of neuroprotective polyketide meridamycin
• An Efficient Method of Computing Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
• Conservation Laws and Symmetries in Competitive Systems
• HOMOMORPHIC IMAGE OF A FUZZY IDEAL OF A BCH-ALGEBRA
• Integer Programming-Based Approach to Attractor Detection and Control of Boolean Networks
• On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors

もっと見る 閉じる

スポンサーリンク