title: A maximum entropy algorithm for rhythmic analysis of genome-wide expression patterns.
abstract: We introduce a maximum entropy-based analysis technique for extracting and characterizing rhythmic expression profiles from DNA microarray hybridization data. These patterns are clues to discovering genes implicated in cell-cycle, circadian, and other periodic biological processes. The algorithm, implemented in a program called ENRAGE (Entropy-based Rhythmic Analysis of Gene Expression), treats the task of estimating an expression profile's periodicity and phase as a simultaneous bicriterion optimization problem. Specifically, a frequency domain spectrum is reconstructed from a time-series of gene expression data, subject to two constraints: (a) the likelihood of the spectrum and (b) the Shannon entropy of the reconstructed spectrum. Unlike Fourier-based spectral analysis, maximum entropy spectral reconstruction is well suited to signals of the type generated in DNA microarray experiments. Our algorithm is optimal, running in linear time in the number of expression profiles. Moreover, an implementation of our algorithm runs an order of magnitude faster than previous methods. Finally, we demonstrate that ENRAGE is superior to other methods at identifying and characterizing periodic expression profiles on both synthetic and actual DNA microarray hybridization data.
authors.affiliation: Computer Science Department, Dartmouth College, Hanover, NH 03755, USA.
authors.forename: Christopher James
authors.initials: CJ
authors.lastname: Langmead
authors.forename: C Robertson
authors.initials: CR
authors.lastname: McClung
authors.forename: Bruce Randall
authors.initials: BR
authors.lastname: Donald
mesh_terms: D000465:Algorithms; D002453:Cell Cycle / Q000502:physiology; D002874:Chromosome Mapping / Q000379:methods*; D002940:Circadian Rhythm / Q000502:physiology*; D029721:Drosophila Proteins / Q000235:genetics / Q000378:metabolism*; D019277:Entropy; D020869:Gene Expression Profiling / Q000379:methods*; D005786:Gene Expression Regulation / Q000502:physiology; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods; D010507:Periodicity; D029701:Saccharomyces cerevisiae Proteins / Q000235:genetics / Q000378:metabolism*
chemical_list: D029721:Drosophila Proteins; D029701:Saccharomyces cerevisiae Proteins