Distribution of Patterns and Statistics in Random Sequences

随机序列中的模式和统计分布

• 批准号: 1107084
• 负责人: Donald Martin
• 金额: $ 10万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2015-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1107084&HistoricalAwards=false
• 关键词: Distribution; Patterns; Statistics; Random; Sequences

This project targets the development and application of tools for efficient computation of distributions associated with patterns and statistics in random sequences, both realizations of observation sequences as well as hidden state sequences conditional on observed data. Due to the massive size of data sets that are available, computational methods that are not only accurate but also efficient are important. The proposed research seeks to contribute in this area. Minimal deterministic finite automata, probability generating functions, the sum-product algorithm and matrix-vector updates are the primary tools used to form algorithms for efficiently computing distributions of patterns and statistics. The goals of this research are threefold: (i) to further develop efficient methods for quantifying uncertainty in statistics of hidden state sequences of probabilistic graphical models; (ii) to efficiently compute exact probability distributions of complex patterns that have not previously been computed; (iii) to apply the probabilistic tools of (i) and (ii) to statistical tests and data analysis. The quantification of uncertainty in statistics of hidden states is frequently dealt with by determining the state sequence that is optimal for a particular criterion, with the statistic then evaluated from the optimal state sequence in a deterministic fashion. However, that approach does not account for uncertainty in the states. An alternate approach is to sample from the conditional distribution of states given the observed data, and then approximate the distribution of the statistic empirically. However, many samples are needed so that the approximation is accurate, leading to problems with scalability. We give a way to compute exact distributions in an efficient manner. The goals of the project are integrated, in that distributions of patterns and statistics are needed for statistical inference in applications, and in turn those applications drive the need for computing distributions in increasingly complex situations. Objectives of the work include computing a model-based distribution of prediction error rates for protein-protein interactions, computing exact distributions of coverage of spaced seeds for homology searches in DNA sequences, and computing the exact distribution of the one-dimensional scan statistic for multi-state higher-order Markovian trials. The need for distributional properties associated with patterns and statistics in random sequences arises in many practical fields of study with massive data sets, such as bioinformatics, time series, information theory, economics, data mining, and quality control. In this research computational tools are developed for computing such distributions. Results for distributions of patterns and statistics may be applied to many practical problems, such as detecting genes, promoters, or other functionally significant patterns in DNA sequences, determining probabilities related to classifications of observations in health-related studies, change points that indicate new regimes in economic data, patterns that indicate an intrusion in a computer system, or patterns associated with surveillance work. The theory will be used to compute distributions of statistics that are intractable by combinatorial or other means, and to provide exact probabilities in an efficient manner in situations that are typically handled by simulation of many data sets. Thus this research facilitates new scientific studies that rely on results for distributions associated with patterns or statistics that have not been computed to date.

该项目的目标是开发和应用工具，用于有效计算与随机序列中的模式和统计相关的分布，实现观察序列以及以观察数据为条件的隐藏状态序列。 由于可用的数据集规模庞大，不仅准确而且高效的计算方法非常重要。 拟议的研究旨在为这一领域作出贡献。 最小确定性有限自动机，概率生成函数，和积算法和矩阵向量更新是用于形成有效计算模式和统计分布的算法的主要工具。 本研究的目标有三个方面：（i）进一步开发有效的方法来量化概率图模型的隐藏状态序列的统计不确定性;（ii）有效地计算以前没有计算过的复杂模式的精确概率分布;（iii）将（i）和（ii）的概率工具应用于统计测试和数据分析。 隐藏状态统计数据中的不确定性的量化通常通过确定对于特定标准最佳的状态序列来处理，然后以确定性方式从最佳状态序列中评估统计数据。 然而，这种方法并没有考虑到各州的不确定性。 另一种方法是从给定观测数据的状态的条件分布中采样，然后根据经验近似统计量的分布。 然而，需要许多样本以使近似是准确的，从而导致可扩展性的问题。 我们给出了一种方法来计算精确的分布在一个有效的方式。 该项目的目标是集成的，因为应用程序中的统计推断需要模式和统计数据的分布，反过来这些应用程序又推动了在日益复杂的情况下计算分布的需求。 目标的工作包括计算一个基于模型的分布预测错误率的蛋白质-蛋白质相互作用，计算精确分布的覆盖间隔种子同源搜索的DNA序列，并计算精确分布的一维扫描统计的多态高阶马尔可夫试验。 随机序列中与模式和统计相关的分布特性的需求出现在许多具有大量数据集的实际研究领域，例如生物信息学，时间序列，信息论，经济学，数据挖掘和质量控制。 在这项研究中，计算工具的开发计算这样的分布。 模式和统计分布的结果可以应用于许多实际问题，例如检测基因、启动子或DNA序列中其他功能重要的模式，确定与健康相关研究中观察结果分类相关的概率，指示经济数据中新制度的变化点，指示计算机系统中入侵的模式，或与监视工作相关的模式。 该理论将被用来计算统计分布是棘手的组合或其他手段，并提供准确的概率在一个有效的方式，通常是由许多数据集的模拟处理的情况下。 因此，这项研究促进了新的科学研究，这些研究依赖于与迄今尚未计算的模式或统计数据相关的分布结果。