Abstract Motivation: Large-scale gene expression profiles measured in gene deletion mutants are invaluable sources for identifying gene regulatory networks. Signed directed graph (SDG) is the most common representation of gene networks in genetics and cell biology. However, no practical procedure that deduces SDGs consistent with such profiles has been developed. Results: We developed the DBRF–MEGN (difference-based regulation finding–minimum equivalent gene network) method in which an algorithm deduces the most parsimonious SDGs consistent with expression profiles of gene deletion mutants. Positive (or negative) directed edges representing positive (or negative) gene regulations are deduced by comparing the gene expression level between the wild-type and mutant. The most parsimonious SDGs are deduced using graph theoretical procedures. Compensation for excess removal of edges by restoring a minimum number of edges makes the method applicable to cyclic gene networks. Use of independent groups of edges greatly reduces the computational cost, thus making the method applicable to large-scale expression profiles. We confirmed the applicability of our method by applying it to the gene expression profiles of 265 Saccharomyces cerevisiae deletion mutants, and we confirmed our method's validity by comparing the pheromone response pathway, general amino acid control system, and copper and iron homeostasis system deduced by our method with those reported in the literature. Interpretation of the gene network deduced from the S. cerevisiae expression profiles by using our method led to the prediction of 132 transcriptional targets and modulators of transcriptional activity of 18 transcriptional regulators. Availability: The software is available on request. Supplementary information: http://www.so.bio.keio.ac.jp/dbrf-megn/