Distributions of patterns and statistics in Markovian sequences

在这个项目中，研究人员研究了通过辅助马尔可夫链计算序列中模式和统计量的分布。在该方法中，利用原始序列中的马尔可夫结构来将辅助马尔可夫链与该序列相关联，使得原始序列中感兴趣的事件当且仅当辅助马尔科夫链处于与该事件相对应的状态类别中时才发生。一旦建立了辅助链，就可以通过跟踪通过链的移动然后提取所需的概率来计算事件的概率。这项工作的目标有三个：(1)计算迄今尚未解决的复杂模式的分布；(2)将开发的概率工具应用于统计测试和数据分析；以及(3)量化由概率图形模型建模的标记和分段数据的统计不确定性。这些目标是综合的，因为计算模式和统计分布的概率方法为目标(2)和(3)的统计应用提供了必要的数学工具，反过来，这些应用又推动了在日益复杂的情况下计算分布的需要。虽然满足前两个目标将对文献做出重要贡献，但该研究的主要贡献由目标(3)表示。隐藏状态序列统计量的抽样分布的计算提供了一种量化标记和分割数据中的不确定性的方法，这是一个尚未得到充分解决的领域。在人们对标签数据的统计量感兴趣的情况下，典型的方法是确定给定观测的最可能的状态序列，然后从该状态序列获得感兴趣的统计量的值。然而，尽管如果人们对最佳标签集感兴趣，则最可能的状态是最优的，但对于标签的统计推断可能不是这样。这项工作为计算标号数据统计量的精确抽样分布提供了一种新的方法，为更准确的推理提供了一种手段。还将考虑计算分布对估计参数的敏感度和对变化点的应用。与序列中的模式和统计相关联的分布属性的需求出现在许多具有海量数据集的实际研究领域，例如生物信息学、时间序列、信息论、经济学、数据挖掘和质量控制。序列中的数据既来自模型的实现，也包括用于标记和分割观测数据的隐藏序列。在这项研究中，开发了计算工具来计算这种分布。模式和统计分布的结果可应用于许多实际问题，例如检测DNA序列中的基因、启动子或其他功能上重要的模式，并确定与健康相关研究中观察到的分类有关的概率、指示经济数据中新制度的变化点、指示入侵的模式或与监测工作相关的模式。该理论可用于计算被噪声或遗漏观测破坏的底层序列中的图案的分布，以及通过组合或其他手段难以处理的统计量的分布。因此，这项研究促进了新的科学研究，这些研究依赖于迄今尚未计算的模式或统计的结果。

In this project the investigator studies the computation of distributions of patterns and statistics in sequences through auxiliary Markov chains. In the method, Markovian structure in the original sequence is exploited to associate an auxiliary Markov chain with the sequence in such a manner that an event of interest in the original sequence occurs if and only if the auxiliary Markov chain lies in a class of states that corresponds to the event. Once the auxiliary chain is set up, probabilities for the event may be computed by tracking movements through the chain and then extracting the desired probabilities. The goals of this work are threefold: (1) to compute distributions of complex patterns that have not been addressed to date; (2) to apply probabilistic tools that are developed to statistical testing and data analysis; and (3) to quantify uncertainty in statistics of labeled and segmented data modeled by probabilistic graphical models. These goals are integrated, since probabilistic approaches to computing distributions of patterns and statistics provide the mathematical tools necessary for the statistical applications of goals (2) and (3), and in turn those applications drive the need for computing distributions in increasingly complex situations. Whereas satisfying the first two goals will provide an important contribution to the literature, the major contribution of the research is represented by goal (3). The computation of sampling distributions of statistics of hidden state sequences provides a method of quantifying uncertainty in labeled and segmented data, an area that has not been adequately addressed. In cases where one is interested in inference on statistics of labeled data, a typical approach is to determine the most likely sequence of states given the observations, and then obtain the value of the statistic of interest from that state sequence. However, whereas the most likely states are optimal if one is interested in the best set of labels, it may not be so for inference on statistics of the labels. This work provides a novel approach to compute the exact sampling distribution of statistics of labeled data, providing a means for more accurate inference. Sensitivity of computed distributions to estimated parameters and applications to change points will also be considered. The need for distributional properties associated with patterns and statistics in sequences, both realizations of data emanating from a model and hidden sequences used to label and segment observed data, 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, and determining probabilities related to classification of observations in health-related studies, change points that indicate new regimes in economic data, patterns that indicate an intrusion, or of patterns associated with surveillance work. The theory may be used to compute distributions of patterns in underlying sequences that are corrupted by noise or missing observations, and also distributions of statistics that are intractable by combinatorial or other means. Thus this research facilitates new scientific studies that rely on results for patterns or statistics that have not been computed to date.