A telescopic algorithm for two-dimensional hidden Markov models with application to genetic studies

以家庭为基础的遗传研究使用许多统计技术来了解遗传信息如何从父母流向后代。研究人员将开发计算效率高的算法，利用一种被称为隐马尔可夫模型的技术，从家庭数据中识别遗传信息。该模型在广泛的科学学科领域取得了相当大的成功，包括电话对话中的语音识别和图像序列中的面部识别等领域。当问题的复杂性增加时，计算算法面临着在现实和实际的时间框架内找到模型解的挑战。研究者对新颖的计算和统计方法的研究将提供具有广泛科学相关性的有效算法和软件工具。在他们的工作中，开发的工具将为寻找复杂疾病的基因提供更有力的方法。合作小组还将直接将他们的技术应用于描述多年植物育种计划的林业遗传数据。在教育方面，参与的学员将融入一个充满活力的跨学科研究团队，获得解决现实世界问题的技术。多维马尔可夫过程在现实世界中无处不在。相互作用的粒子系统、图像、视频、数字化文档和基因传递中的依赖关系都是多维马尔可夫过程的例子。马尔可夫过程是一种随机过程（即，一种统计现象，其中一系列事件或变量的可能结果会发生变化），其中对未来状态的预测仅使用当前状态的信息，独立于过去的历史和未知的未来状态。这个想法推广到更高的维度。例如，基因从父母传递给孩子是一个二维马尔可夫过程，未来状态的确定，孩子，取决于邻居在二维，父母。然而，大多数感兴趣的情况是隐马尔可夫过程，其中变量的当前状态不能被观察到，但必须通过考虑所有可能的未来状态来推断给定所有可能的当前状态。随着需要确定的数量的增加，计算机内存和计算时间的计算需求都急剧增加。因此，要将这个概念应用到许多重要的实际应用中，需要开发新颖而强大的计算算法。这个项目的重点是设计一个新颖的软件包，专门为解决隐马尔可夫模型而设计。所开发的技术将适用于解决来自广泛学科的问题，不仅适用于更广泛的基于家庭的遗传研究，而且也适用于诸如图像文本分析等领域。因此，该项目将增加解决许多工程、地球科学和生物学科的现实问题的计算能力，并具有相应的潜在积极的社会影响。在这种情况下，通过与林业科学专家的合作，在植物育种方面出现了一个有趣的应用。

Family-based genetic studies use a number of statistical techniques to understand how genetic information flows from parent to offspring. The investigators will develop computationally efficient algorithms for identifying genetic information from family data using a technique known as a Hidden Markov model. This model has demonstrated considerable success in a broad range of scientific disciplines, including areas such as speech recognition in telephone conversations and face identification from sequences of images. When the complexity of the problem increases, computational algorithms confront challenges with finding the solution of the model in realistic and practical time frames. The investigators' research on novel computational and statistical approaches will provide efficient algorithms, and software tools, of broad scientific relevance. In their work the tools developed will yield a more powerful approach for finding genes underlying complex diseases. The collaborative team will also directly apply their techniques to forestry genetic data describing a multi-year plant-breeding program. Educationally, the trainees involved will be integrated into a vibrant interdisciplinary research team, gaining exposure to techniques for the solution of real world problems. Multi-dimensional Markov processes are ubiquitous in the real world. Dependencies in interacting particle systems, images, videos, digitized documents, and gene transmission are all examples of multi-dimensional Markov processes. A Markov process is a random process (i.e., a statistical phenomenon in which the possible outcomes of a sequence of events or variables vary) in which the prediction of the future state is made just using the information of the current state, independent of both past history and unknown future states. This idea generalizes for higher dimensions. For example, gene transmission from parent to child is a two-dimensional Markov process, the determination of the future state, the child, depends on the neighbors in two dimensions, the parents. Most cases of interest, however, are hidden Markov processes, in which the current state of a variable cannot be observed, but must be inferred by consideration of all possible future states given all possible current states. As the number of quantities to be determined increases, the computational demand in both computer memory and computing time increases dramatically. To apply the concept, therefore, to many important real applications requires the development of novel and powerful computational algorithms. This project is focused on the design of a novel software package, specifically designed for the solution of hidden Markov models. The techniques developed will be relevant for the solution of problems from a broad array of disciplines, not only for wider family based genetic studies but also areas such as text analysis from images. Thus, this project will increase the computational ability to solve real-world problems across many engineering, geosciences and biological disciplines, with commensurate potential positive societal impact. In this case an interesting application arises in plant breeding through the collaboration with experts in forestry science.