A proof of the DBRF-MEGN method, an algorithm for deducing minimum equivalent gene networks

Koji Kyoda; Kotaro Baba; Hiroaki Kitano; Shuichi Onami

doi:10.1186/1751-0473-6-12

A proof of the DBRF-MEGN method, an algorithm for deducing minimum equivalent gene networks

Source Code Biol Med. 2011 Jun 24;6(1):12. doi: 10.1186/1751-0473-6-12.

Authors

Koji Kyoda¹, Kotaro Baba, Hiroaki Kitano, Shuichi Onami

Affiliation

¹ Laboratory for Developmental Dynamics, RIKEN Quantitative Biology Center, and Advanced Computational Sciences Department, RIKEN Advanced Science Institute, 1-7-22 Suehirocho, Tsurumi, Yokohama 230-0045, Japan. sonami@riken.jp.

Abstract

Background: We previously developed the DBRF-MEGN (difference-based regulation finding-minimum equivalent gene network) method, which deduces the most parsimonious signed directed graphs (SDGs) consistent with expression profiles of single-gene deletion mutants. However, until the present study, we have not presented the details of the method's algorithm or a proof of the algorithm.

Results: We describe in detail the algorithm of the DBRF-MEGN method and prove that the algorithm deduces all of the exact solutions of the most parsimonious SDGs consistent with expression profiles of gene deletion mutants.

Conclusions: The DBRF-MEGN method provides all of the exact solutions of the most parsimonious SDGs consistent with expression profiles of gene deletion mutants.