Published online 19 May 2011 Nucleic Acids Research, 2011, Vol. 39, No. 14 e95
doi:10.1093/nar/gkr349
ESPRIT-Tree: hierarchical clustering analysis of millions of 16S rRNA pyrosequences in quasilinear computational time
Yunpeng Cai and Yijun Sun*
Interdisciplinary Center for Biotechnology Research University of Florida, Gainesville, FL 32610, USA
Received October 2, 2010; Revised April 8, 2011; Accepted April 26, 2011
ABSTRACT
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 com- putational complexities, and thus can be used only for small or medium-scale problems. We propose a new online learning-based algorithm that simultan- eously 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 se- quences as a probabilistic sequence, and define a set of operations to align these probabilistic se- quences and compute genetic distances between them. We present analyses of space and computa- tional complexity, and demonstrate the effectiveness of our new algorithm using a human gut microbiota data set with over one million se- quences. 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 clus- tering algorithm.
INTRODUCTION
Microbes play an essential role in processes as diverse as human health and biogeochemical activities critical to life in all environments on earth. The descriptions of complex microbial communities, however, remain poorly characterized. Currently available pyrosequencing technologies easily and inexpensively determine millions of signature sequences in a matter of hours. However, analyzing such massive nucleotide sequence collections can overwhelm existing computational resources and analytic methods, and consequently new computational algorithms are urgently needed (1).
Providing a detailed description of microbial popu- lations, including high, medium and low abundance com- ponents, is typically the first step in microbial community analysis (2,3). PCR amplification of the 16S rRNA gene, followed by DNA sequencing, is now a standard approach to studying microbial community dynamics at high resolution (4–8). Existing algorithms for microbial classi- fication using 16S rRNA sequences can be generally categorized into taxonomy-dependent or -independent analyses (9). In the former methods, query sequences are first compared against a database and then assigned to the organism of the best-matched reference sequences [e.g. BLAST (10)]. Since most microbes have not been formally described yet, these methods are inherently limited by the completeness of reference databases (9). In contrast, taxonomy-independent analysis compares query sequences against each other to form a distance matrix followed by clustering analysis to group sequences into operational taxonomic units (OTUs) at a specified level of sequence similarity (e.g. sequences grouped at 97% identity are often used as proxies for bacterial species). Various ecological metrics can then be estimated from the clustered sequences to characterize a microbial
*To whom correspondence should be addressed. Tel: 1 352 273 8271; Fax: 1 352 273 8070; Email: sunyijun@biotech.ufl.edu The authors wish it to be known that, in their opinion, the first two authors should be regarded as joint First Authors.
copy; The Author(s) 2011. Published by Oxford University Press.
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/ by-nc/3.0), which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
community. This analysis does not rely on any reference database, and can thus enumerate novel pathogenic and uncultured microbes as well as known organisms. In addition to microbial diversity estimation, there is currently increased interest in applying taxonomy- independent analysis to analyze millions of sequences for comparative microbial community analysis (11,12).
The key step in taxonomy-independent analysis is to group sequences into OTUs based on pairwise sequence differences, where hierarchical clustering is one of the most widely employed approaches (13,14). Hierarchical clustering is a classic unsupervised learning technique (15), and has been used in numerous biomedical appli- cations [e.g. (12,16,17)]. The main drawback of hierarch- ical clustering is its high computational and space complexities. In computer science, this computational complexity is represented in so-called lsquo;Big-Orsquo; notation, where the number given indicates how the time or space scales for large problem sizes: for example, an (N) algo- rithm takes time proportional to the size of the input, and an (N2) algorithm takes time proportional to the square of the size of the input (e.g. computing all pairwise dis- tances between sequences takes time proportional to the square of the number of sequences, because each sequence must be compared t
全文共54643字，剩余内容已隐藏，支付完成后下载完整资料
ESPRIT-Tree: 在拟线性计算时间内对数百万个16s rRNA 焦磷酸序列进行级联聚类分析
蔡云鹏
摘要
独立于分类学的分类在微生物群落分析中起着至关重要的作用。级联聚类是找到可操作分类单位最广泛采用的方法之一，这是许多下游分析的基础。大部分现有的算法受限于二次空间和计算的复杂性，只能用于小规模或中等规模的问题。我们提出了一种新的在线学习算法，该算法同时解决了先前工作中的空间和计算问题。其基本思想是使用用伪度量构造的分隔树将序列空间划分为一组子空间，然后递归地构造这些子空间的聚类结构。这个技术依赖于快速最近对搜索和有效的动态插入和删除树节点的新方法。为了避免穷举计算簇之间的成对距离，我们将每个簇序列表示为概率序列，并定义一组操作来对这些概率序列进行比对并计算它们之间的遗传距离。我们介绍了对空间和计算复杂性的分析，并展示了使用超过一百万个序列的人类肠道微生物群数据集的新算法的有效性。在达到与标准级联聚类算法相似精确度的情况下，我们的新算法表现出与贪婪启发式聚类算法相当的拟线性时间和空间复杂度。
介绍
微生物对人类健康和全球所有环境中的生物化学活动都发挥着至关重要的作用。但是，复杂的微生物群落的描述仍然没有得到充分表征。目前可用的焦磷酸测序技术可以在数小时内轻松而廉价地测出数百万个特征序列。然而，现有的计算资源和分析方法很难分析这么大量的核苷酸序列集，因此需要新的计算算法。
获得微生物种群的详细描述包括高、中和低的数量丰度的部分是微生物种群分析典型的第一步。PCR 扩增16S rRNA基因，然后进行DNA测序，已经是研究高分辨率微生物群落动态的标准方法。现有的使用16S rRNA 序列进行微生物分类的算法通常可以分为依赖分类学和不依赖分类学的两种。前一种方法中，首先将查询序列与数据库进行比较，然后将其分配给最佳匹配参考序列的生物体。由于大多数微生物还没有被正式记录，这类方法本质上受限于参考数据库的完整性。相反，不依赖分类学的分析方法将查询序列相互比较形成距离矩阵，然后通过聚类分析，相似度在特定水平（例如：经常用与细菌物种有97%相似度的序列作为细菌物种的替代序列）的序列就被分为可操作的分类单位（OTU）。然后用聚类后的序列可以估计各种生态指标来表征微生物群落。该分析方法不依赖于任何参考数据库，因此可以列举出未培养过的致病微生物以及已知的微生物。除了微生物多样性评估之外，目前人们越来越关注应用不依赖分类学的分析方法到微生物群落分析中。
不依赖分类学的分析方法的关键步骤是基于成对序列的差异来给分组，其中级联聚类是这个步骤中被最广泛采用的方法。级联聚类是一种典型的非监督学习技术，并已经被许多生物医学应用使用。级联聚类的主要缺点是计算和空间复杂性高在计算机科学中，这种计算复杂度用大“O”符号表示，括号内的数字表示大规模数据下的时间或空间度量：例如，一个时间复杂度为O(n)的算法花费的时间和输入的规模成正比，一个时间复杂度为O(n2)的算法花费的时间和输入规模的平方成正比（例如：计算所有序列之间的相互距离花费的时间和序列数目的平方成正比，因为每个序列都要和其他每个序列对比）。给定N个对象，暴力算法花费O(N2logN)时间，而改进算法花费O(n2)。传统方法所需的内存大小会随着数据量增多称二次方增长。在过去的十年中，研究人员开发了几个近似的次二级时间复杂度的级联聚类算法，这些算法的基本思想应用空间划分技术（动态最近对树）来分级地划分对象到对应的单元中，因此用分治策略能在相邻单元中找到每个对象的最邻近对象。这些算法能在O(NlogN)复杂度下进行分析并获得很好的近似结果。然而，它们只能处理数值空间中的低维数据，虽然也可以定义超平面来划分空间和样本。在数学上，为了用超平面划分空间，必须定义内积算子，以便可以指定空间中的方向来指示平面的内测和外侧。对于核苷酸序列数据，不存在这样的内积算子，因此不能定义超平面来有效地划分数据。此外，与数值向量不同，序列对之间的距离只能通过序列比对来计算，因为序列长度不同，需要插入或删除。因此，在没有定义维度的核苷酸空间中，一个序列可以被当成一个数据点，这引出了新的数学挑战。
在过去的十年里，人们为不依赖分类学的分析开发的好几种算法。DOTUR可能是第一个被公开的用于焦磷酸测序数据分析并被微生物学界广泛使用的级联聚类算法。它要求使用者提供距离矩阵并将距离矩阵加载到主内存中。由于其二次复杂性，它只能处理几万个序列。我们最近开发出一种新的称为“ESPRIT”的算法，它使研究员通过使用计算机集群处理多达一百万个序列。使用 ESPRIT 框架开发的在线学习级联聚类算法“hCluster”能够处理集群合并时的内存问题。尽管 ESPRIT 使用k-mer统计来消除大量不必要的序列比较，但它仍然是O(N2）的算法。Hcluster 算法已经取代 DOTUR 算法被纳入知名的 mothur pipeline。与 ESPRIT 不同，mothur 通过将输入序列与预先对齐的参考数据库进行对齐来计算成对距离。由于参考数据库可以离线维护，序列比对步骤的计算复杂度仅相对于输入序列的数据量线性增长。但是，算法也遭遇了和依赖分类学的分析相同的问题。由于大多数细菌基因组还没有被测序，来自未知微生物的大部分输入序列可能无法找到比对的序列，并且只能与较不相关的参考序列比对，导致成对距离的估计不准确。此外，整体的空间和时间复杂度依然是O(N2)。另一个研究路线是开发贪婪启发式聚类方法。两种众所周知的方法是CD-HIT和UCLUST。它们都使用成对序列比对并按顺序处理输入序列。给定一个预定义的阈值，输入一个序列，如果序列与种子序列之间的距离小于阈值那么它就被分配到一个已有的簇中，否则它就成为种子序列。贪婪启发式聚类方法的计算复杂度是O(NM)，其中 M 是种子的数目，通常 M lt;lt; N。CD-HIT和UCLUST是我们找到的唯一两个能够用一台桌面电脑处理数百万个序列的算法。虽然 CD-HIT 和 UCLUST 已层次结构组织数据，但它们不是级联聚类算法，并且不能保证真正的数据结构能够被恢复。在下面的数据研究中，我们将展示，虽然 CD-HIT 和 UCLUST 的运行速度比级联聚类算法快几个数量级，但其准确度要差的多。有兴趣的读者可以参考一片配套文献来全面回顾现有的不依赖分类学的分析方法。
在本文中，我们提出了一种新算法“ESPRIT-Tree“，用于大规模序列数据的级联聚类分析。为了避免混淆，我们先说明，ESPRIT-Tree不是用于确定系统发生树的程序，而是使用树形数据结构并基于序列相似度来生成级联聚类的程序。我们拓展了以前用于处理不同长度序列数据的方法使用的空间划分的概念。通过假定序列数据存在于伪空间中，我们创建了基于距离的数据划分，而没有明确定义内积算子来划分空间，并将划分结果组织为基于伪度量的分区树。通过重复应用三角不等式，使用 ESPRIT-Tree 框架开发了一个快速最近对搜索算法。还开发了一种用于动态插入和删除树节点的高效方法。为了避免穷举计算簇之间的成对距离，我们将一簇序列表示为一个概率序列，然后定义了一组操作来对对齐概率序列并计算概率序列之间的遗传距离和 k-mer 距离。我们给出了该算法的空间分析和计算复杂度分析。我们对包含超过一百万个序列的人类肠道微生物群数据集进行了大规模测试，证明了新提出的算法的有效性。
方法
本节将详细描述新提出的 ESPRIT-Tree 算法。在全文中，我们使用粗体小写字符来表示一个向量或一个序列串，使用粗体大写字符来表示一个矩阵，第 ij 个元素表示为 Mij。
先决条件
伪度量空间
我们假定序列数据存在于伪度量空间。准确地说，给定一个数据集 X 和一个用于计算两个序列之间相似度的计分函数d(.)，对于x， y， z isin; X， 有如下属性：(1) d(x, y) = d(y, x)，(2) d(x, x) = 0 和 (3) d(x, y) le; d(x, z) d(z, y) （这就是三角不等式，保证了不存在一条从 A 到 B 且经过 C 的路径比直接从 A 到 B 的路径短）。前两个属性是平凡的。虽然序列数据不严格遵守三角不等式，但上述假设非常弱。进行蒙特卡洛实验，在十万次实验中只有七次违反了三角不等式（参见“实验结果”部分）。
基于伪度量的划分树
基于伪度量的划分树（PBP树）是一个高度平衡树，由预先指定距离等级的多层节点组成。图1描述了一个有四层的样例树。一种类似的技术首先用于众所周知的 BIRCH 算法中，用于聚类大规模数值数据。在这篇文章中，我们拓展了这个概念来处理不同长度的序列数据。树中的每一个节点表示空间中的超球面区域，并包括位于该区域中的除了被先前节点包含的所有子节点和序列。一个非叶子节点表示为：，其中 J 是该节点的子节点总数，是指向其子节点的指针的有序列表，并且 I 是其父代的子列表中的节点的顺序。CF = { N，r，c }是一个概括节点包含序列的三元组，其中 N 是序列的总数，c 是确定节点中心的序列或概率序列（在下一节中描述），r 是用于决定是否包含一个新序列到节点或创建一个新节点的距离等级。叶子节点仅包含一个单一序列或一个单一簇，为了方便表示，根节点在创建时没有中心和等级，因而可包含所有的后代节点（图1b）。如果两个节点共享同一个父节点，我们称一个节点为另一个节点的兄弟节点。对于两个兄弟节点 A 和 B，如果 A 的顺序小于 B，我们称 A 为 B 的前任。在“构建PBP树”一节中给出了如何在给定序列数据集的情况下构建 PBP 树的详细说明。
图1：
PBP 树。PBP 树将输入空间划分为不同的颜色（a）的圆所指示的各种距离等级的一组非重叠的超球面区域，并以树状级联结构（b）组织输入序列。（a）中的每个点表示一个序列，并且（b）中的节点的对应于（a）中的圆的颜色。为了方便表示，省略了叶节点，并创建了包含所有后代的根节点。（a）中所示的划分可能不一定反映数据集的真实结构，但可以通过除去大多数不必要的序列对齐操作和距离计算来显著加速聚类过程。
概率序列
概率序列是用于描述一组相似序列的统计模型。假设我们有两条序列 a 和 b，其最佳全局比对由下式给出：
（1）
我们创建了一个5 * 11的矩阵 P，其中从顶部到底部的每行分别表示核苷酸A，T，C，G和空位，每列代表对齐序列的核苷酸碱基（矩阵 P 是补充表格 S1）。为了方便表示，我们将矩阵 P 和长度为11的虚拟序列 x 相关联，并称{x，P}为一个概率序列。x 的每个元素都可以按 P 中标明的概率取四个核苷酸或空位中的某一个。例如，上面例子中的 p 的第一列是[0.5, 0, 0, 0.5, 0]T，其中 T 是矩阵转置。通过使用或然 Needleman–Wunsch 算法（将在下面详细介绍），给定新序列时 P 的更新和计算两个概率序列之间的遗传距离只涉及简单线性代数的应用。
或然 Needleman–Wunsch 算法
新提出的或然 Needleman-Wunsch 算法是 Needleman-Wunsch 算法的推广，用于最优地对齐两个虚拟序列。假设我们有两个概率序列 {x，P} 和 {y，Q}。x = [x1, hellip;, xJ] ，y = [y1, hellip;, yL]。给定计分矩阵，{x，P} 和 {y，Q} 之间的最佳比对得分可通过以下递归方程来计算：
（2）
其中C（x j，y l），C（x j，gap）和C（gap，y l）分别是x j对yl，xj对空位和yl对空位的对齐。然而，由于 xj 和 yl 都可以以特定概率取核苷酸碱基或空位，C(xj, yl) 和 C(xj, gap)可以通过下式计算：
（3）
（4）
其中P ij和Q nl分别是矩阵P和Q的第ij和nl个元素，C（x j，y l）和C（x j，gap）可以分别解释为x j与y l或间隙对齐的预期成本。每个位置的对齐分数都存储在一个数组中，并带有一个指针，用于记录当前的最佳操作，并提供回溯最佳对齐的有效路径。在以上描述中，为了简单起见，我们使用线性空位罚分。仿制缺口惩罚的扩展很简单。
新提出的或然 Needleman-Wunsch 算法与用于多序列比对的众所周知的MUSCLE算法中使用的 profile–profile alignment (PPA)具有相同的概念。然而，PPA 适用于两组序列，而不是两个概率序列。利用概率序列的概念，我们可以优于PPA，并根据比对结果直接计算遗传距离，如下所述。
概率序列之间的遗传距离
两个全局比对序列之间的遗传距离为不匹配核苷酸碱基数量除以序列的总长度。两个虚拟序列之间的距离可以类似地计算。令{ x，P }和{ y，Q }为长度为L的两个对齐的概率序列。假设我们随机选择两个遵循由P和Q指定的概率的序列s = [ s1，...，sL]和t = [ t1，...，tL]，两个序列在给定位置（例如l）不同的概率可以计算为：
（5）
虚拟序列 x 和 y 之间的遗传距离可计算为：
（6）
构造之后，矩阵P和Q记录了两个簇的序列的分布。我们称d（x，y）为两个聚类的概率平均距离，并将其用作平均簇间距
全文共11488字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[16989]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
