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.