Exact scalable inference for coalescent processes

现代基因数据集是巨大的，无论是在测序个体的数量和测序DNA片段的长度方面。这些数据集中的模式包含有关人口的生物和人口历史的信息，这些信息通常不能直接观察到。将观察到的模式与预测和推断联系起来的核心工具是金曼聚结：一个随机树，为未观察到的样本DNA序列的祖先提供了一个模型。由于祖先是无法观察到的，推论是通过对所有可能的祖先进行平均来进行的。在简单的情况下，祖先的平均值可以分析计算，但在大多数生物学相关的情况下，平均值必须近似。这通常是通过模拟可能的祖先树的集合来完成的，并将集合平均值视为真实的未知平均值的近似值。近似的质量取决于集合代表所有可能祖先集合的程度。确保一个集合既具有代表性，又不是不可行的大，是一个具有挑战性的问题。现有的合成方法分为两类：重要性抽样（IS）和马尔可夫链蒙特卡罗（MCMC），后者通常更灵活，更容易实现。众所周知，这两种方法在数据集的大小和复杂性方面都不能很好地扩展。本提案旨在通过三种相关的方式提高最先进的MCMC方法的可扩展性：1。已经做了很多工作来描述最优的IS算法，这些算法的表现与更灵活的MCMC的朴素实现大致相同。该项目的初步结果表明，IS的最优性结果也可用于表征最优MCMC算法，但这从未完成。这项工作将调查并彻底基准测试结果，优化MCMC算法的性能。通过所谓的最优缩放结果，MCMC算法的实际效用得到了极大的提高，这为如何在数据集增长时调整算法提供了指导。然而，这些通常只适用于被模拟的分布由独立的实值组件组成的设置。在遗传学中，利益的分布是由树构成的，因此要复杂得多。该项目将研究最优缩放结果的扩展到树值设置，使用最近通过狄利克雷形式开发的最优缩放机制，这是分析树值算法的一种自然方式。最近发表的一种名为mprime的算法使用了一种称为稀疏树的新颖数据结构，将朴素合并模拟的速度和内存消耗提高了许多个数量级。这不会立即转化为改进的推理算法，因为天真的模拟通常会导致对真实平均值的较差表示的集成。稀疏树结构不能直接插入到MCMC算法中，但初步工作已经确定了几种方法，可以修改MCMC以使用类似于稀疏树的数据结构。该项目将实现并对所有结果算法进行基准测试，以确定哪种方法最有效。这三个流的最终结果将是一个高度优化的、灵活的、开源的遗传推理算法。由于数学优化（目标1和2）和底层数据结构优化（目标3）的结合，它将在大型数据集上具有前所未有的性能。MCMC算法还为它们的估计提供自动的、严格的不确定性量化，这是许多最先进的竞争对手无法提供的。这使得MCMC特别适合临床实践，在临床实践中，了解不确定性对医疗结果至关重要。

Modern genetic data sets are vast, both in terms of the number of sequenced individuals and the length of the sequenced DNA segments. Patterns within these data sets carry information about the biological and demographic histories of the population, which cannot usually be observed directly.The central tool connecting observed patterns to predictions and inference is the Kingman coalescent: a random tree that provides a model for the unobserved ancestry of the sampled DNA sequences. Since the ancestry is unobserved, inferences are made by averaging over all possible ancestries.In simple cases the average over ancestries can be calculated analytically, but in most biologically relevant scenarios the average has to be approximated. This is usually done by simulating an ensemble of possible ancestral trees, and treating the ensemble average as an approximation of the true, unknown average. The quality of the approximation depends on the degree to which the ensemble is representative of the set of all possible ancestries. Ensuring that an ensemble is both representative, and not infeasibly large, is a challenging problem. Existing methods for producing ensembles split into two categories: importance sampling (IS), and Markov chain Monte Carlo (MCMC), of which the latter is typically more flexible and easier to implement. Both are known to scale poorly with the size and complexity of the data set. This proposal seeks to improve the scalability of state of the art MCMC methods in three related ways:1. Much work has been done to characterise optimal IS algorithms, which have been observed to perform roughly as well as naive implementations of the more flexible MCMC. Preliminary results for this project show that optimality results for IS can also be used to characterise optimal MCMC algorithms, but this has never been done. This work will investigate and thoroughly benchmark the performance of the resulting, optimised MCMC algorithms.2. The practical utility of MCMC algorithms has improved dramatically through so-called optimal scaling results, which provide a guide for how to tweak the algorithm as the data set grows. However, these typically apply only to settings in which the distribution being simulated consists of independent, real-valued components. In genetics, the distributions of interests consist of trees, and is hence much more complicated. This project will investigate extensions of optimal scaling results to tree-valued settings using recently developed machinery of optimal scaling via Dirichlet forms, which are a natural way to analyse tree-valued algorithms.3. A recently published algorithm called msprime uses a novel data structure, called a sparse tree, to improve the speed and memory consumption of naive coalescent simulation by many orders of magnitude. This does not immediately translate to improved inference algorithms, because naive simulation typically results in ensembles that are poor representations of the true average. The sparse tree structure cannot be directly inserted into an MCMC algorithm, but preliminary work has identified several ways in which MCMC can be modified to use data structures resembling sparse trees. This project will implement and benchmark all of the resulting algorithms to determine which of these ways is the most effective.The end result of these three streams will be a highly optimised, flexible, open source algorithm for inference in genetics. It will have unprecedented performance on large data sets due to a combination of mathematical optimisation (objectives 1 and 2) and optimisation of the underlying data structure (objective 3). MCMC algorithms also provide automatic, rigorous uncertainty quantification for their estimates, which many state-of-the-art competitors are not able to provide. This makes MCMC particularly well suited to e.g. clinical practice, where understanding uncertainties is crucial for medical outcomes.