ESPRIT-Tree: hierarchical clustering analysis of millions of 16S rRNA pyrosequences in quasilinear computational time.
ESPRIT-Tree: hierarchical clustering analysis of millions of 16S rRNA pyrosequences in quasilinear computational time.
复制标题
DOI：
10.1093/nar/gkr349
复制
发表时间：
2011-08
影响因子：
14.9
通讯作者：
Sun Y
中科院分区：
文献类型：
--
作者：
Cai Y;Sun Y
分类独立分析在微生物群落分析中起着至关重要的作用。分层聚类是寻找可操作的分类单位的最广泛使用的方法之一，是许多下游分析的基础。大多数现有算法具有二次空间和计算复杂性，因此只能用于中小型问题。我们提出了一种新的基于在线学习的算法，同时解决了先前工作的空间和计算问题。其基本思想是使用伪度量构造的划分树将序列空间划分为一组子空间，然后在这些子空间中递归地细化聚类结构。该技术依赖于快速搜索最接近对和高效动态插入和删除树节点的新方法。为了避免集群之间的成对距离的穷尽计算，我们将每个序列集群表示为一个概率序列，并定义一组操作来对齐这些概率序列并计算它们之间的遗传距离。我们提出了空间和计算复杂性的分析，并使用超过一百万个序列的人类肠道微生物群数据集证明了我们的新算法的有效性。该算法具有与贪婪启发式聚类算法相当的拟线性时间和空间复杂度，同时具有与标准分层聚类算法相似的精度。
Taxonomy-independent analysis plays an essential role in microbial community analysis. Hierarchical clustering is one of the most widely employed approaches to finding operational taxonomic units, the basis for many downstream analyses. Most existing algorithms have quadratic space and computational complexities, and thus can be used only for small or medium-scale problems. We propose a new online learning-based algorithm that simultaneously addresses the space and computational issues of prior work. The basic idea is to partition a sequence space into a set of subspaces using a partition tree constructed using a pseudometric, then recursively refine a clustering structure in these subspaces. The technique relies on new methods for fast closest-pair searching and efficient dynamic insertion and deletion of tree nodes. To avoid exhaustive computation of pairwise distances between clusters, we represent each cluster of sequences as a probabilistic sequence, and define a set of operations to align these probabilistic sequences and compute genetic distances between them. We present analyses of space and computational complexity, and demonstrate the effectiveness of our new algorithm using a human gut microbiota data set with over one million sequences. The new algorithm exhibits a quasilinear time and space complexity comparable to greedy heuristic clustering algorithms, while achieving a similar accuracy to the standard hierarchical clustering algorithm.
登录
查看更多内容
影响因子：
48
作者：
Quince, Christopher;Lanzen, Anders;Sloan, William T.
通讯作者：
Sloan, William T.
影响因子：
5.1
作者：
Sait, M;Hugenholtz, P;Janssen, PH
通讯作者：
Janssen, PH
影响因子：
4.4
作者：
Schloss, Patrick D.;Westcott, Sarah L.;Weber, Carolyn F.
通讯作者：
Weber, Carolyn F.
影响因子：
14.9
作者：
Cole JR;Wang Q;Cardenas E;Fish J;Chai B;Farris RJ;Kulam-Syed-Mohideen AS;McGarrell DM;Marsh T;Garrity GM;Tiedje JM
通讯作者：
Tiedje JM
影响因子：
14.9
作者：
Sun Y;Cai Y;Mai V;Farmerie W;Yu F;Li J;Goodison S
通讯作者：
Goodison S