Identifying TF Binding Motifs from a Partial Set of Target Genes and its Application to Regulatory Network Inference

Motif identification has been one of the most widely studied problems in bioinformatics. Many methods have been developed to discover binding motifs from a large set of genes. But when the given genes are only a partial set of target genes, the statistical significance usually contains a bias towards the input. If we can identify the TF binding motif from a partial set of target genes, we can save the labor costs and resources for doing many experiments. In this paper, we propose a method MISA (Motif Identification through Segments Assembly) to identify binding motifs from a subset of target genes. By ranking and assembling the segments, MISA discovers a set of binding motifs with the best length to fit our proposed objective function. We also predict the additional target genes as an application of regulatory network inference. We compare our approach with two widely used methods MEME and AlignACE by analyzing both the quality of the binding motif and network inference. Using two model organisms S. cerevisiae and E. coli, we show that with 20 percent of the target genes (minimum sample size of 20), we can achieve a motif similarity of 82 percent with the known motifs. Our results also show that 73 percent of target genes on average can be correctly predicted without introducing many false target genes.