Self consistency grouping: a stringent clustering method

BMC Bioinformatics

Research

Bong-Hyun Kim¹  Nick V Grishin²  Bhadrachalam Chitturi³ 

[1] Biochemistry Department, UT Southwestern Medical Center, Dallas, TX, USA;Biochemistry Department, UT Southwestern Medical Center, Dallas, TX, USA;Howard Hughes Medical Institute, UT Southwestern Medical Center, Dallas, TX, USA;Department of Computer Science, Amrita Vishwa Vidyapeetham University, Amritapuri Campus, Kerala, India;School of Biotechnology, Amrita Vishwa Vidyapeetham University, Amritapuri Campus, Kerala, India;

关键词: Average Linkage;    Single Linkage;    Complete Linkage;    Complete Structure;    Rank Matrix;   

DOI  :  10.1186/1471-2105-13-S13-S3

来源: Springer

【 摘 要 】

BackgroundNumerous types of clustering like single linkage and K-means have been widely studied and applied to a variety of scientific problems. However, the existing methods are not readily applicable for the problems that demand high stringency.MethodsOur method, self consistency grouping, i.e. SCG, yields clusters whose members are closer in rank to each other than to any member outside the cluster. We do not define a distance metric; we use the best known distance metric and presume that it measures the correct distance. SCG does not impose any restriction on the size or the number of the clusters that it finds. The boundaries of clusters are determined by the inconsistencies in the ranks. In addition to the direct implementation that finds the complete structure of the (sub)clusters we implemented two faster versions. The fastest version is guaranteed to find only the clusters that are not subclusters of any other clusters and the other version yields the same output as the direct implementation but does so more efficiently.ResultsOur tests have demonstrated that SCG yields very few false positives. This was accomplished by introducing errors in the distance measurement. Clustering of protein domain representatives by structural similarity showed that SCG could recover homologous groups with high precision.ConclusionsSCG has potential for finding biological relationships under stringent conditions.

【 授权许可】

Unknown   
© Kim et al; licensee BioMed Central Ltd. 2012. This article is published under license to BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.