Data from: SATé-II: very fast and accurate simultaneous estimation of multiple sequence alignments and phylogenetic trees

Highly accurate estimation of phylogenetic trees for large datasets is difficult, in part because multiple sequence alignments must be accurate for phylogeny estimation methods to be accurate. Co-estimation of alignments and trees has been attempted, but currently only SATé estimates reasonably accurate trees and alignments for large datasets in practical time frames (Liu et al., 2009b). Here, we present a modification to the original SATé algorithm that improves upon SATé (which we now call SATé-I) in terms of speed and of phylogenetic and alignment accuracy. SATé-II uses a different divide-and-conquer strategy than SATé-I, and so produces smaller, more closely related subsets than SATé-I; as a result, SATé-II produces more accurate alignments and trees, can analyze larger datasets, and runs more efficiently than SATé-I. SATé-II is a meta-method that takes an existing multiple sequence alignment method as an input parameter and boosts the quality of that alignment method. SATé-II-boosted alignment methods are significantly more accurate than their unboosted versions, and trees based upon these improved alignments are more accurate than trees based upon the original alignments. Finally, because SATé-I used maximum likelihood methods that treat gaps as missing data to estimate trees, and because we found a correlation between the quality of tree/alignment pairs and maximum likelihood scores, we explored the degree to which SATé’s performance depends on using maximum likelihood with gaps treated as missing data to determine the best tree/alignment pair. We present two lines of evidence that using maximum likelihood with gaps treated as missing data to optimize the alignment and tree produces very poor results. First, we show that the optimization problem where a set of unaligned DNA sequences is given and the output is the tree and alignment of those sequences that maximize likelihood under the Jukes-Cantor model is uninformative in the worst possible sense: for all inputs, all trees optimize the likelihood score. Second, we show that a greedy heuristic that uses GTR+Gamma maximum likelihood to optimize the alignment and the tree can produce very poor alignments and trees. Therefore, the excellent performance of SATé-II and SATé-I is not because maximum likelihood is used as an optimization criterion for choosing the best tree/alignment pair, but rather due to the particular divide-and-conquer re-alignment techniques employed.

针对大型数据集开展高精度系统发育树（phylogenetic trees）估计极具挑战性，部分原因在于：系统发育树估计方法的精度依赖于准确的多序列比对（multiple sequence alignments）。此前已有研究尝试开展比对与树的联合估计（co-estimation），但目前仅有SATé能够在合理的时间框架内为大型数据集生成精度尚可的树与比对结果（Liu等，2009b）。在此，我们提出对原始SATé算法的改进方案，该方案在运行速度、系统发育树与比对精度方面均优于原SATé（我们将其命名为SATé-I）。SATé-II采用了与SATé-I截然不同的分治策略，因此相较于SATé-I，其生成的子集规模更小、亲缘关系更紧密；由此，SATé-II可生成精度更高的比对结果与系统发育树，能够处理规模更大的数据集，且运行效率优于SATé-I。SATé-II是一种元方法（meta-method），可将现有多序列比对方法作为输入参数，提升该比对方法的性能。经SATé-II增强的比对方法，其精度显著优于未增强的原始版本；基于这些优化后比对结果构建的系统发育树，精度也高于基于原始比对结果的树。此外，由于SATé-I采用将空位视为缺失数据的最大似然法（maximum likelihood methods）估计系统发育树，且我们发现树/比对对的质量与最大似然得分存在相关性，因此我们探究了：SATé的性能在多大程度上依赖于以“空位视为缺失数据的最大似然法”来选择最优树/比对对。我们提供了两类证据，证明采用“空位视为缺失数据的最大似然法”优化比对与树会得到极差的结果。第一，我们证明了以下优化问题在最坏情况下完全不具备信息量：给定一组未比对的DNA序列，输出可在Jukes-Cantor模型下最大化似然值的序列比对与对应系统发育树——对于所有输入而言，所有树的似然得分均一致。第二，我们证明了一种采用GTR+Gamma最大似然法优化比对与树的贪心启发式算法，可能生成精度极低的比对结果与系统发育树。因此，SATé-II与SATé-I的优异性能并非源于以最大似然法作为选择最优树/比对对的优化准则，而是得益于其所采用的特定分治重比对技术。

搜集汇总

背景与挑战

背景概述

该数据集包含用于SATé-II算法研究的生物序列数据，包括16S.B.ALL和16S.T两个子集的比对文件和树文件，总大小约354.61 MB。数据集支持评估SATé-II算法在同时估计多序列比对和系统发育树方面的改进性能，相比SATé-I具有更高的速度和准确性。