An efficient top-down search algorithm for learning Boolean networks of gene expression |
| |
Authors: | Dougu Nam Seunghyun Seo Sangsoo Kim |
| |
Affiliation: | (1) National Genome Information Center, Korea Research Institute of Bioscience and Biotechnology, Eoun-dong 52, Yusong-gu, Daejeon, 305-333, Rep. of Korea;(2) Department of Mathematics, Seoul National University, Shinlim-dong, Kwanak-gu, Seoul, 151-747, Rep. of Korea;(3) Department of Bioinformatics, Soongsil Univ., Sangdo 5-Dong, Dongjak-Gu, Seoul, 156-743, Rep. of Korea |
| |
Abstract: | Boolean networks provide a simple and intuitive model for gene regulatory networks, but a critical defect is the time required
to learn the networks. In recent years, efficient network search algorithms have been developed for a noise-free case and
for a limited function class. In general, the conventional algorithm has the high time complexity of O(22k
mn
k+1) where m is the number of measurements, n is the number of nodes (genes), and k is the number of input parents. Here, we suggest a simple and new approach to Boolean networks, and provide a randomized
network search algorithm with average time complexity O
(mn
k+1/ (log m)(k−1)). We show the efficiency of our algorithm via computational experiments, and present optimal parameters. Additionally, we
provide tests for yeast expression data.
Editor: David Page |
| |
Keywords: | Boolean network Data consistency Random superset selection Core search Coupon collection problem |
本文献已被 SpringerLink 等数据库收录! |
|