SGER: Algorithmic Challenges in Computational Biology

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

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.