Algorithms for Identifying Boolean Networks and Related Biological Networks Based on Matrix Multiplication and Fingerprint Function

Abstract

Due to the recent progress of the DNA microarray technology, a large number of gene expression profile data are being produced. How to analyze gene expression data is an important topic in computational molecular biology. Several studies have been done using the Boolean network as a model of a genetic network. This paper proposes efficient algorithms for identifying Boolean networks of bounded indegree and related biological networks, where identification of a Boolean network can be formalized as a problem of identifying many Boolean functions simultaneously. For the identification of a Boolean network, an O(mn^D+1) time naive algorithm and a simple O(mn^D) time algorithm are known, where n denotes the number of nodes, m denotes the number of examples, and D denotes the maximum indegree. This paper presents an improved O(m^ω-2n ^D + mn^D+ω-3) time Monte-Carlo type randomized algorithm, where ω is the exponent of matrix multiplication (currently, ω < 2.376). The algorithm is obtained by combining fast matrix multiplication with the randomized fingerprint function for string matching. Although the algorithm and its analysis are simple, the result is nontrivial and the technique can be applied to several related problems.