Fast Dating Using Least-Squares Criteria and Algorithms.
Fast Dating Using Least-Squares Criteria and Algorithms.
复制标题
DOI：
10.1093/sysbio/syv068
复制
发表时间：
2016-01
影响因子：
6.5
通讯作者：
Gascuel O
中科院分区：
文献类型：
--
作者：
To TH;Jung M;Lycett S;Gascuel O
系统发育学为了解遗传样本的进化史提供了一种有用的方式，拥有一千多个分类群的数据集正变得越来越常见，尤其是病毒(例如人类免疫缺陷病毒(HIV))。确定祖先事件的年代是使用这些数据的第一个、也是最基本的目标之一。然而，目前复杂的概率方法很难处理这种规模的数据集。在这里，我们提出了非常快速的测年算法，基于与兰利-费奇分子钟模型密切相关的高斯模型。我们证明了该模型对分子时钟的不相关破坏是健壮的。我们的算法适用于序列数据，其中树的顶端经过时间采样。他们估计了所有祖先节点的替换率和日期。当输入树无根时，它们可以提供对根位置的估计，从而代表了标准根方法(例如中点)的新的、实用的替代方案。我们的算法利用了手头问题的树(递归)结构，以及最小二乘和线性代数之间的密切关系。我们区分不受约束的设置和考虑时间优先约束(即，祖先节点必须比其子节点更老)的情况。对于有根树，前者在线性计算时间内(即与类群数目成正比)使用线性代数求解，而后者的求解是基于近线性时间运行的有效集方法。对于无根树，计算时间变得(几乎)二次(即，与分类群数量的平方成比例)。在所有情况下，都可以很容易地处理非常大的输入树(>；10,000个分类群)并将其转换为按时间缩放的树。我们将这些算法与标准方法(根到尖、R8s版本的Langley-Fitch方法和Beast)进行比较。仿真数据表明，它们的估计精度与最复杂的方法相近，而计算时间要快得多。我们将这些算法应用于包含来自pdm09 H1N1人类大流行的1194株流感病毒的大型数据集。结果再次表明，这些算法提供了一种非常快速的替代方案，其结果与其他计算机程序的结果相似。这些算法是在最小二乘法(LSD)软件中实现的，该软件可以从http://www.atgc-montpellier.fr/LSD/，下载，以及我们所有的数据集和详细结果。提供更多算法描述、表格和图表的在线附录可在Dryad上的补充材料中找到，网址为http://dx.doi.org/10.5061/dryad.968t3.
Phylogenies provide a useful way to understand the evolutionary history of genetic samples, and data sets with more than a thousand taxa are becoming increasingly common, notably with viruses (e.g., human immunodeficiency virus (HIV)). Dating ancestral events is one of the first, essential goals with such data. However, current sophisticated probabilistic approaches struggle to handle data sets of this size. Here, we present very fast dating algorithms, based on a Gaussian model closely related to the Langley–Fitch molecular-clock model. We show that this model is robust to uncorrelated violations of the molecular clock. Our algorithms apply to serial data, where the tips of the tree have been sampled through times. They estimate the substitution rate and the dates of all ancestral nodes. When the input tree is unrooted, they can provide an estimate for the root position, thus representing a new, practical alternative to the standard rooting methods (e.g., midpoint). Our algorithms exploit the tree (recursive) structure of the problem at hand, and the close relationships between least-squares and linear algebra. We distinguish between an unconstrained setting and the case where the temporal precedence constraint (i.e., an ancestral node must be older that its daughter nodes) is accounted for. With rooted trees, the former is solved using linear algebra in linear computing time (i.e., proportional to the number of taxa), while the resolution of the latter, constrained setting, is based on an active-set method that runs in nearly linear time. With unrooted trees the computing time becomes (nearly) quadratic (i.e., proportional to the square of the number of taxa). In all cases, very large input trees (>10,000 taxa) can easily be processed and transformed into time-scaled trees. We compare these algorithms to standard methods (root-to-tip, r8s version of Langley–Fitch method, and BEAST). Using simulated data, we show that their estimation accuracy is similar to that of the most sophisticated methods, while their computing time is much faster. We apply these algorithms on a large data set comprising 1194 strains of Influenza virus from the pdm09 H1N1 Human pandemic. Again the results show that these algorithms provide a very fast alternative with results similar to those of other computer programs. These algorithms are implemented in the LSD software (least-squares dating), which can be downloaded from http://www.atgc-montpellier.fr/LSD/, along with all our data sets and detailed results. An Online Appendix, providing additional algorithm descriptions, tables, and figures can be found in the Supplementary Material available on Dryad at http://dx.doi.org/10.5061/dryad.968t3.