EFFICIENTLY FINDING REGULATORY ELEMENTS USING CORRELATION WITH GENE EXPRESSION

1 June 2004

journal article
research article
Published by World Scientific Pub Co Pte Ltd in Journal of Bioinformatics and Computational Biology

Vol. 02 (02) , 273-288
https://doi.org/10.1142/s0219720004000612

Abstract

We present an efficient algorithm for detecting putative regulatory elements in the upstream DNA sequences of genes, using gene expression information obtained from microarray experiments. Based on a generalized suffix tree, our algorithm looks for motif patterns whose appearance in the upstream region is most correlated with the expression levels of the genes. We are able to find the optimal pattern, in time linear in the total length of the upstream sequences. We implement and apply our algorithm to publicly available microarray gene expression data, and show that our method is able to discover biologically significant motifs, including various motifs which have been reported previously using the same data set. We further discuss applications for which the efficiency of the method is essential, as well as possible extensions to our algorithm.

Keywords

This publication has 9 references indexed in Scilit:

Estimating gene networks from gene expression data by combining Bayesian network model with promoter element detection
Bioinformatics, 2003
Regulatory element detection using correlation with expression
Nature Genetics, 2001
Efficient Construction of Regression Trees with Range and Region Splitting
Machine Learning, 2001
Systematic determination of genetic network architecture
Nature Genetics, 1999
SCPD: a promoter database of the yeast Saccharomyces cerevisiae.
Bioinformatics, 1999
Comprehensive Identification of Cell Cycle–regulated Genes of the YeastSaccharomyces cerevisiaeby Microarray Hybridization
Molecular Biology of the Cell, 1998
Algorithms on Strings, Trees and Sequences
Published by Cambridge University Press (CUP) ,1997
On-line construction of suffix trees
Algorithmica, 1995
Fast Algorithms for Finding Nearest Common Ancestors
SIAM Journal on Computing, 1984