Abstract: It is crucial to make inference of genetic regulatory networks from gene expression profiles and protein interaction data for systems biology. This study develops a new approach to reconstruct time delay Boolean networks as a tool for exploring biological pathways. Specifically, we prove that O(log n) state transition pairs are sufficient and necessary to reconstruct the time delay Boolean network of n nodes with high accuracy if the number of input genes to each gene is bounded. In the inference strategy, we compare all pairs of input genes in those basic relationships by their corresponding p-scores for every output gene. Then, we combine those consistent relationships to reveal the most probable relationship. We implement this method on simulated and empirical yeast gene expression data sets. The results show that this proposed method is extensible for realistic networks.