Title :
Research on Greedy Clique Partition-GCP Algorithm
Author_Institution :
Sch. of Inf. & Electron. Eng., Shandong Inst. of Bus. & Technol., Yantai
Abstract :
Clustering of binary fingerprints is used in the classification of gene expression data. It is known that the clustering of binary fingerprints with 3 bits of missing value is NP-hard. The greedy clique partition (GCP for short) algorithm is a heuristic algorithm used to clustering of binary fingerprints with missing values. In this paper, we firstly study the feature of instances which can not be resolved by the GCP based on hash table. Then a new property of problem instances is given, which can further improve the heuristic algorithm based on linked list. Finally, an empirical formula is presented, which is used to judge the accuracy and credibility of the GCP algorithm
Keywords :
DNA; biocomputing; computational complexity; fingerprint identification; greedy algorithms; pattern classification; pattern clustering; GCP algorithm; NP-hard; binary fingerprint clustering; gene expression classification; greedy clique partition; hash table; heuristic algorithm; Clustering algorithms; Cybernetics; DNA; Data engineering; Electronic mail; Fingerprint recognition; Gene expression; Heuristic algorithms; Machine learning; Machine learning algorithms; Partitioning algorithms; Probes; Sequences; Clustering; algorithm; clique partition; gene expression data;
Conference_Titel :
Machine Learning and Cybernetics, 2006 International Conference on
Conference_Location :
Dalian, China
Print_ISBN :
1-4244-0061-9
DOI :
10.1109/ICMLC.2006.259018
