A novel hierarchical clustering algorithm for gene sequences

BMC Bioinformatics

Methodology Article

Dan Wei¹  Shengrui Wang²  Yanjie Wei³  Qingshan Jiang³ 

[1] Cognitive Science Department & Fujian Key Laboratory of the Brain-like Intelligent Systems, Xiamen University, Xiamen, China;Shenzhen Key Lab for High Performance Data Mining, Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, China;Department of Computer Sciences, University of Sherbrooke, Sherbrooke, QC, Canada;Shenzhen Key Lab for High Performance Data Mining, Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, China;

关键词: Cluster Algorithm;    Cluster Result;    H1N1 Virus;    Cluster Performance;    Hierarchical Cluster Algorithm;   

DOI  :  10.1186/1471-2105-13-174

 received in 2011-11-05, accepted in 2012-06-30,  发布年份 2012

来源: Springer

【 摘 要 】

BackgroundClustering DNA sequences into functional groups is an important problem in bioinformatics. We propose a new alignment-free algorithm, mBKM, based on a new distance measure, DMk, for clustering gene sequences. This method transforms DNA sequences into the feature vectors which contain the occurrence, location and order relation of k-tuples in DNA sequence. Afterwards, a hierarchical procedure is applied to clustering DNA sequences based on the feature vectors.ResultsThe proposed distance measure and clustering method are evaluated by clustering functionally related genes and by phylogenetic analysis. This method is also compared with BlastClust, CD-HIT-EST and some others. The experimental results show our method is effective in classifying DNA sequences with similar biological characteristics and in discovering the underlying relationship among the sequences.ConclusionsWe introduced a novel clustering algorithm which is based on a new sequence similarity measure. It is effective in classifying DNA sequences with similar biological characteristics and in discovering the relationship among the sequences.

【 授权许可】

CC BY   
© Wei et al.; licensee BioMed Central Ltd. 2012