Accurate, context-specific regulation of gene expression is essential for all organisms. Accordingly, it is very important to understand the complex relations within cellular gene regulatory networks. A tool to describe and analyze the behavior of such networks are Boolean models. The reconstruction of a Boolean network from biological data requires identification of dependencies within the network. This task becomes increasingly computationally demanding with large amounts of data created by recent high-throughput technologies. Thus, we developed a method that is especially suited for network structure reconstruction from large-scale data. In our approach, we took advantage of the fact that a specific transcription factor often will consistently either activate or inhibit a specific target gene, and this kind of regulatory behavior can be modeled using monotone functions.