Hereditary Stratigraphy: Genome Annotations to Enable Phylogenetic Inference over Distributed Populations
Hereditary Stratigraphy: Genome Annotations to Enable Phylogenetic Inference over Distributed Populations
复制标题
遗传地层学：基因组注释可对分布式种群进行系统发育推断
DOI：
10.1162/isal_a_00550
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ofria, Charles
中科院分区：
文献类型：
--
作者：
Moreno, Matthew Andres;Dolson, Emily;Ofria, Charles
系统发育分析还可以深入了解进化和生态动态，例如数字进化系统中的选择压力和频率依赖选择。传统的数字进化系统通过完美的跟踪来记录用于系统发育分析的数据，其中每个出生事件都记录在集中式数据结构中。然而，这种方法不容易扩展到分布式计算环境，在分布式计算环境中，进化个体可能在大量不相交的处理元素之间迁移。为了在这些环境中提供系统发育分析，我们提出了一种通过可遗传的遗传注释推断系统发育的方法，而不是直接跟踪它们。我们引入了一种“遗传地层学”算法，该算法能够实现高效、准确的系统发育重建，并在注释内存占用和重建精度之间进行可调、明确的权衡。例如，这种方法可以估计两个基因组的 MRCA 生成，相对误差在 10% 以内，置信度高达 95%，深度可达万亿代，基因组注释小于 1 KB。我们还模拟对已知谱系的推理，使用 64 位注释恢复原始树中包含的高达 85.70% 的信息。
Phylogenetic analyses can also enable insight into evolutionary and ecological dynamics such as selection pressure and frequency dependent selection in digital evolution systems. Traditionally digital evolution systems have recorded data for phylogenetic analyses through perfect tracking where each birth event is recorded in a centralized data structures. This approach, however, does not easily scale to distributed computing environments where evolutionary individuals may migrate between a large number of disjoint processing elements. To provide for phylogenetic analyses in these environments, we propose an approach to infer phylogenies via heritable genetic annotations rather than directly track them. We introduce a "hereditary stratigraphy" algorithm that enables efficient, accurate phylogenetic reconstruction with tunable, explicit trade-offs between annotation memory footprint and reconstruction accuracy. This approach can estimate, for example, MRCA generation of two genomes within 10% relative error with 95% confidence up to a depth of a trillion generations with genome annotations smaller than a kilobyte. We also simulate inference over known lineages, recovering up to 85.70% of the information contained in the original tree using a 64-bit annotation.