Completing Networks Using Observed Data
Abstract
This paper studies problems of completing a given Boolean network (Boolean circuit) so that the input/output behavior is consistent with given examples, where we only consider acyclic networks. These problems arise in the study of inference of signaling networks using reporter proteins. We prove that these problems are NP-complete in general and a basic version remains NP-complete even for tree structured networks. On the other hand, we show that these problems can be solved in polynomial time for partial k -trees of bounded (constant) indegree if a logarithmic number of examples are given.
Cite
Text
Akutsu et al. "Completing Networks Using Observed Data." International Conference on Algorithmic Learning Theory, 2009. doi:10.1007/978-3-642-04414-4_14Markdown
[Akutsu et al. "Completing Networks Using Observed Data." International Conference on Algorithmic Learning Theory, 2009.](https://mlanthology.org/alt/2009/akutsu2009alt-completing/) doi:10.1007/978-3-642-04414-4_14BibTeX
@inproceedings{akutsu2009alt-completing,
title = {{Completing Networks Using Observed Data}},
author = {Akutsu, Tatsuya and Tamura, Takeyuki and Horimoto, Katsuhisa},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2009},
pages = {126-140},
doi = {10.1007/978-3-642-04414-4_14},
url = {https://mlanthology.org/alt/2009/akutsu2009alt-completing/}
}