Hartuv E, Schmitt A O, Lange J, Meier-Ewert S, Lehrach H, Shamir R
Department of Computer Science, Tel-Aviv University, Tel-Aviv, 69978, Israel.
Genomics. 2000 Jun 15;66(3):249-56. doi: 10.1006/geno.2000.6187.
Clustering large data sets is a central challenge in gene expression analysis. The hybridization of synthetic oligonucleotides to arrayed cDNAs yields a fingerprint for each cDNA clone. Cluster analysis of these fingerprints can identify clones corresponding to the same gene. We have developed a novel algorithm for cluster analysis that is based on graph theoretic techniques. Unlike other methods, it does not assume that the clusters are hierarchically structured and does not require prior knowledge on the number of clusters. In tests with simulated libraries the algorithm outperformed the Greedy method and demonstrated high speed and robustness to high error rate. Good solution quality was also obtained in a blind test on real cDNA fingerprints.
对大型数据集进行聚类是基因表达分析中的一项核心挑战。合成寡核苷酸与阵列cDNA的杂交可为每个cDNA克隆生成一个指纹图谱。对这些指纹图谱进行聚类分析可以识别出对应于同一基因的克隆。我们开发了一种基于图论技术的新型聚类分析算法。与其他方法不同，它不假定聚类具有层次结构，也不需要关于聚类数量的先验知识。在对模拟文库的测试中，该算法的性能优于贪婪方法，并在高错误率情况下表现出高速性和稳健性。在对真实cDNA指纹图谱的盲测中也获得了良好的解决方案质量。
