An efficient top-down search algorithm for learning Boolean networks of gene expression

Cited 24 time in scopus
Metadata Downloads
Title
An efficient top-down search algorithm for learning Boolean networks of gene expression
Author(s)
Dougu Nam; S Seo; S Kim
Bibliographic Citation
Machine Learning, vol. 65, no. 1, pp. 229-245
Publication Year
2006
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(22kmn 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.
Keyword
Boolean networkCore searchCoupon collection problemData consistencyRandom superset selection
ISSN
0885-6125
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s10994-006-9014-z
Type
Article
Appears in Collections:
1. Journal Articles > Journal Articles
Files in This Item:
  • There are no files associated with this item.


Items in OpenAccess@KRIBB are protected by copyright, with all rights reserved, unless otherwise indicated.