Real-time phylogenetics using sequential Monte Carlo with tree sequences

2019冠状病毒病大流行凸显了许多不同科学领域在帮助应对传染病传播方面的重要性。其中一个领域是病原体基因组学，通过对SARS-CoV-2基因组测序的分析，可以检测和跟踪该病毒的不同变体。英国在这一领域尤为强大，英国COVID-19基因组学联盟（COG-UK）为政府应对大流行提供了重要投入。病原体基因组的快速测序现在是可能的。这些数据的一个可能用途是通过重建测序基因组的祖先历史（系统发育推断）实时跟踪病原体的进化和传播。大流行显示了获得此类信息的价值（例如，参见Nextstrain的工作，https://nextstrain.org/）.The系统发育推断的最新技术是使用马尔可夫链蒙特卡罗（MCMC）算法对祖先历史进行贝叶斯推断，由于其严格描述与从数据中得出的推断相关的不确定性的理念，因此受到青睐。这种方法是在BEAST （https://beast.community/）和BEAST2 （beast2.org）包中实现的，但在它们目前的形式中，这些不适合“实时”推理，因为它们对一批基因组序列执行推理。如果在软件中启动MCMC运行后出现新的序列，则必须重新启动算法以考虑新数据。这些MCMC算法通常要运行数千万次迭代，因此这种重新启动算法的过程在计算上是浪费的，并且阻碍了实时推理的目标。该项目提出了一种替代方法，旨在使实时贝叶斯推断对大量序列可行，为在大流行期间使用的可部署系统奠定基础。

The COVID-19 pandemic has highlighted the importance of a number of different scientific fields in helping to tackle the spread of an infectious disease. One of these fields is pathogen genomics, which has, through the analysis of sequenced SARS-CoV-2 genomes, enabled the detection and tracking of different variants of the virus. The UK is particularly strong in this area, with the COVID-19 Genomics UK Consortium (COG-UK) providing important inputs into the government response to the pandemic.Rapid sequencing of pathogen genomes is now possible. One possible use of this data is in real-time tracking of pathogen evolution and transmission through reconstruction of the ancestral history of sequenced genomes (phylogenetic inference). The pandemic has shown the value of having such information available (see, for example, the work of Nextstrain, https://nextstrain.org/).The state-of-the-art in phylogenetic inference is to use Markov chain Monte Carlo (MCMC) algorithms for the Bayesian inference of the ancestral history, preferred due to its philosophy of rigorously describing the uncertainty associated with inferences drawn from the data. This approach is implemented in the BEAST (https://beast.community/) and BEAST2 (beast2.org) packages but in their current form these are unsuitable for "real-time" inference, since they perform inference on a batch of genome sequences. If a new sequence becomes available after starting the a run of the MCMC in the software, the algorithm must be restarted to take account of the new data. These MCMC algorithms are often run for tens of millions of iterations, so this process of restarting the algorithm is computationally wasteful and hinders the goal of real-time inference. This project proposes an alternative approach, with the aim of making real-time Bayesian inference feasible for large numbers of sequences, preparing the ground for a deployable system that could be used during a pandemic.