Computational Genomics, IBM T J Watson Research, Yorktown, New York, USA.
BMC Bioinformatics. 2011 Feb 15;12 Suppl 1(Suppl 1):S6. doi: 10.1186/1471-2105-12-S1-S6.
Ancestral Recombinations Graph (ARG) is a phylogenetic structure that encodes both duplication events, such as mutations, as well as genetic exchange events, such as recombinations: this captures the (genetic) dynamics of a population evolving over generations.
In this paper, we identify structure-preserving and samples-preserving core of an ARG G and call it the minimal descriptor ARG of G. Its structure-preserving characteristic ensures that all the branch lengths of the marginal trees of the minimal descriptor ARG are identical to that of G and the samples-preserving property asserts that the patterns of genetic variation in the samples of the minimal descriptor ARG are exactly the same as that of G. We also prove that even an unbounded G has a finite minimal descriptor, that continues to preserve certain (graph-theoretic) properties of G and for an appropriate class of ARGs, our estimate (Eqn 8) as well as empirical observation is that the expected reduction in the number of vertices is exponential.
Based on the definition of this lossless and bounded structure, we derive local properties of the vertices of a minimal descriptor ARG, which lend itself very naturally to the design of efficient sampling algorithms. We further show that a class of minimal descriptors, that of binary ARGs, models the standard coalescent exactly (Thm 6).
祖先重组图（ARG）是一种系统发育结构，它同时编码了复制事件，如突变，以及遗传交换事件，如重组：这捕获了一个种群在几代人的进化过程中的（遗传）动态。
在本文中，我们确定了 ARG G 的结构保持和样本保持核心，并将其称为 G 的最小描述符 ARG。其结构保持特性确保了最小描述符 ARG 的边缘树的所有分支长度都与 G 的分支长度相同，而样本保持特性则断言了最小描述符 ARG 的样本中的遗传变异模式与 G 的完全相同。我们还证明了即使是无界的 G 也有一个有限的最小描述符，它仍然保留了 G 的某些（图论）性质，并且对于适当的 ARG 类，我们的估计（公式 8）以及经验观察表明，顶点数量的预期减少是指数级的。
基于这个无损且有界结构的定义，我们推导出了最小描述符 ARG 的顶点的局部性质，这使得它非常自然地适用于设计高效的采样算法。我们进一步表明，一类最小描述符，即二进制 ARG，完全模拟了标准合并（定理 6）。
