SGER: Algorithmic Challenges in Computational Biology

众所周知，许多与年轮（每年）、昼夜节律（每天）、细胞周期和其他周期性生物过程相关的基因的表达模式具有节律性。相反，与非周期性生物过程（如组织修复）相关的基因的表达谱是没有节奏的。因此，如果先前未表征的基因表现出与某些正在进行的生物过程同步的节律性表达模式，则可以推断其功能意义。当一个时间序列的表达水平被收集时，DNA微阵列实验是识别节律性基因的有效工具。不同于Northern blots和real-time PCR每次只研究一个基因，DNA微阵列杂交实验可以揭示整个基因组的表达模式。因此，时间生物学家能够根据单个实验的结果为大量基因分配假定的功能特性。然而，杂交实验产生的大量数据使得人工检查单个表达谱不切实际。将表达谱具有节律性的基因子集与数以千计或数以万计的非节律性基因子集分开需要计算机辅助。理想情况下，提供这种帮助的算法应该是高效的，并且具有易于理解的性能保证。我们建议设计和实现算法，从DNA微阵列杂交时间序列数据中识别和表征节律性基因的特性。我们的方法将建立在我们最近发表在{\em在合成和实际DNA微阵列杂交数据上识别和表征周期性表达谱的方法比以前的方法要少。因此，本建议的第二个重点是发展新的信号处理方法来分析基因表达模式，并将其与计算几何中的组合算法相结合。}\cite{recomb02}和{\em 计算分子生物学研究国际会议（RECOMB）}\cite{csb02}的论文上。我们将特别讨论计算复杂性、统计显著性和形态相似性的问题。我们希望我们的技术将有助于功能基因组学的努力，通过开发新的算法技术来分析大量并行DNA微阵列表达数据。我们将开发一种基于模型的分析技术，用于从全基因组DNA微阵列杂交数据中提取和表征节律性表达谱。我们的方法，称为{\sc IEEE计算机学会生物信息学会议}（基因表达的节奏分析），解耦了估计图案的波长和相位的问题。具体来说，(I)我们提出{\em 愤怒}使我们的搜索算法与相位无关，（II）我们提出{\em 自相关}来测量自相关信号的相似性。通过使用这些新方法来解决微阵列基因表达时间序列分析的问题，我们希望加强时间生物学家的计算装备。我们的{\sc 豪斯多夫距离}算法在频率和相位分辨率上是线性时间的，比以前的二次时间方法有所改进。与以前的方法不同，{\sc 愤怒}使用基于Hausdorff距离的真实距离度量来测量表达谱相似性。这导致更好的聚类表达谱的节奏分析。使用$Z$ -scores计算每个频率估计的置信度。在初步结果中，{\sc 愤怒}在合成和实际DNA微阵列杂交数据上的表现优于竞争技术。利用Voronoi图\cite{Huttenlocher}组合界的结果，我们可以用精确（组合精确）相位搜索\cite{recomb02}取代我们方法中的离散相位搜索，从而产生更快的算法，并且不依赖于相位分辨率的复杂性。因此，本建议的重点之一是开发用于分析表达模式的组合精确、可证明的算法。令人惊讶的是，最大熵谱分析（MESA）尚未应用于大规模并行基因表达时间序列分析。因此，我们还将开发一种基于最大熵的分析技术，用于从DNA微阵列杂交数据中提取和表征节律表达谱。这种方法称为{\sc 愤怒}（基于熵的基因表达节律分析），将估计表达谱的周期性和相位的任务视为同时的双周期优化问题。具体来说，从基因表达数据的时间序列重构频域谱，受两个约束：(a)谱的似然性和(b)重构谱的香农熵。与基于傅立叶的光谱分析不同，最大熵光谱重建非常适合于DNA微阵列实验中产生的信号类型。{\sc 激怒}算法是最优的，在线性时间内运行的表达式配置文件的数量。此外，我们的算法的初步实现比以前的方法运行速度快一个数量级。在初步结果中，我们发现{\sc 激怒}表现更好

EIA-0305444Bruce R DonaldDartmouth CollegeProject SummaryThe expression patterns of many genes associated with circannual (yearly), circadian (daily), cell-cycle and other periodic biological processes are known to be rhythmic. Conversely, the expression profiles of genes associated with aperiodic biological processes (e.g., tissue repair) are not rhythmic. The functional significance of previously uncharacterized genes, therefore, may be inferred if they exhibit rhythmic patterns of expression synchronized to some ongoing biological process.DNA microarray experiments are an effective tool for identifying rhythmic genes when a time-series of expression levels are collected. Unlike Northern blots and real-time PCR, which study one gene at a time, DNA microarray hybridization experiments can reveal the expression patterns of entire genomes. Chronobiologists are therefore able to assign putative functional properties to large numbers of genes based on the results of a single experiment. However, the large volume of data generated by hybridization experiments makes manual inspection of individual expression profiles impractical. Separating the subset of genes whose expression profiles are rhythmic from the thousands or tens of thousands that are not requires computer assistance. Ideally, the algorithms for providing such assistance should be efficient and have well-understood performance guarantees.We propose to design and implement algorithms to identify and characterize the properties of rhythmic genes from DNA microarray hybridization time-series data. Our approach will build on our recent papers in {\em The International Conference on Research in Computational Molecular Biology (RECOMB)}~\cite{recomb02} and the {\em IEEE Computer Society Bioinformatics Conference}~\cite{csb02}. We will specifically addresses issues of computational complexity, statistical significance and morphological similarity. We hope our techniques will aid efforts in functional genomics, by developing new algorithmic techniques for the analysis of massively-parallel DNA microarray expression data.We will develop a model-based analysis technique for extracting and characterizing rhythmic expression profiles from genome-wide DNA microarray hybridization data. Our approach, called {\sc rage}(Rhythmic Analysis of Gene Expression), decouples the problems of estimating a pattern's wavelength and phase. Specifically (I) we propose the {\em autocorrelation} to render our search algorithm phase-independent, and (II) we propose the {\em Hausdorff distance} to measure the similarity of the autocorrelated signals. By attacking the problem of microarray gene-expression time-series analysis using these new methods, we hope to strengthen the computational armamentarium of the chronobiologist. Our {\sc rage} algorithm is linear-time in frequency and phase resolution, an improvement over previous quadratic-time approaches. Unlike previous approaches, {\sc rage} uses a true distance metric for measuring expression profile similarity, based on the Hausdorff distance. This results in better clustering of expression profiles for rhythmic analysis. The confidence of each frequency estimate is computed using $Z$-scores. In preliminary results,{\sc rage}performed better than competing techniques on synthetic and actual DNA microarray hybridization data. Employing results on combinatorial bounds for Voronoi diagrams~\cite{Huttenlocher}, we can replace the discretized phase search in our method with an exact (combinatorially precise) phase search~\cite{recomb02}, resulting in a faster algorithm with no complexity dependence on phase resolution. Thus, one emphasis of this proposal is the development of combinatorially-precise, provable algorithms for analyzing expression patterns.Surprisingly, maximum entropy spectral analysis (MESA) has not been applied to massively-parallel gene expression time-series analysis before. Therefore, we will also develop a maximum entropy-based analysis technique for extracting and characterizing rhythmic expression profiles from DNA microarray hybridization data. This approach, called {\sc 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. The {\sc enrage} algorithm is optimal, running in linear time in the number of expression profiles. Moreover, a preliminary implementation of our algorithm runs an order of magnitude faster than previous methods. In preliminary results, we found that {\sc enrage} performed better than previous methods in identifying and characterizing periodic expression profiles on both synthetic and actual DNA microarray hybridization data. Thus, a second thrust of this proposal is the development of novel signal-processing approaches to analyze gene expression patterns, and their integration with combinatorial algorithms from computational geometry.