d2_cluster: A validated method for clustering EST and full-length cDNA sequences
d2_cluster: A validated method for clustering EST and full-length cDNA sequences
复制标题
DOI：
10.1101/gr.9.11.1135
复制
发表时间：
1999-11-01
期刊：
影响因子：
7
通讯作者：
Hide, W
中科院分区：
文献类型：
--
作者：
Burke, J;Davison, D;Hide, W
目前正在进行多项努力，通过聚类或组装的方式大规模压缩单读表达序列标签 (EST) 和全长转录本数据。这些项目的目标之一是构建基因索引，其中转录本被划分为索引类别（或簇），当且仅当它们代表相同的基因时，它们才被放入相同的索引类别。准确的基因索引有助于基因表达研究以及通过组装源自尚未定位克隆或直接通过基因组测序获得的基因的 EST 的廉价且早期的部分基因序列发现。我们描述了 d2_cluster，这是一种凝聚算法，用于通过根据最小链接或“传递闭包”规则对序列进行聚类来快速准确地将转录本数据库划分为索引类。然后我们评估 d2_duster 相对于其他聚类工具的相对效率。选择 UniGene 进行比较是因为其高质量和广泛接受度。结果表明，虽然 d2_cluster 和 UniGene 产生的结果在 83% 到 90% 之间相同，但 d2_cluster 的加入率比 UniGene 高 8% 到 20%。最后，我们首次发表了对序列聚类算法的聚类不足和过度聚类（即 I 型和 II 型错误）的严格评估，尽管高度相同的基因旁系同源物的存在意味着在解释 II 型错误时必须小心。这些 d2_cluster 错误率的上限估计分别为 0.4% 和 0.8%。换句话说，d2_cluster 的灵敏度和选择性估计 >99.6% 和 99.2%。
Several efforts are under way to condense single-read expressed sequence tags (ESTs) and full-length transcript data on a large scale by means of clustering or assembly. One goal of these projects is the construction of gene indices where transcripts are partitioned into index classes (or clusters) such that they are put into the same index class if and only if they represent the same gene. Accurate gene indexing facilitates gene expression studies and inexpensive and early partial gene sequence discovery through the assembly of ESTs that are derived from genes that have yet to be positionally cloned or obtained directly through genomic sequencing. We describe d2_cluster, an agglomerative algorithm for rapidly and accurately partitioning transcript databases into index classes by clustering sequences according to minimal linkage or "transitive closure" rules. We then evaluate the relative efficiency of d2_duster with respect to other clustering tools. UniGene is chosen for comparison because of its high quality and wide acceptance. It is shown that although d2_cluster and UniGene produce results that are between 83% and 90% identical, the joining rate of d2_cluster is between 8% and 20% greater than UniGene. Finally, we present the first published rigorous evaluation of under and over clustering (in other words, of type I and type II errors) of a sequence clustering algorithm, although the existence of highly identical gene paralogs means that care must be taken in the interpretation of the type II error. Upper bounds for these d2_cluster error rates are estimated at 0.4% and 0.8%, respectively. In other words, the sensitivity and selectivity of d2_cluster are estimated to be >99.6% and 99.2%.