Parallel Clustering Algorithm for Large Data Sets with Applications in Bioinformatics

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel Clustering Algorithm for Large Data Sets with Applications in Bioinformatics

Full text

Pdf (974 KB)

Source

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) archive
Volume 6 , Issue 2 (April 2009) table of contents

Pages 344-352

Year of Publication: 2009

ISSN:1545-5963

Authors

Victor Olman	University of Georgia, Athens
Fenglou Mao	University of Georgia, Athens
Hongwei Wu	University of Georgia, Athens
Ying Xu	University of Georgia, Athens

Publisher

IEEE Computer Society Press Los Alamitos, CA, USA

Bibliometrics

Downloads (6 Weeks): 35, Downloads (12 Months): 128, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/TCBB.2007.70272

ABSTRACT

Large sets of bioinformatical data provide a challenge in time consumption while solving the cluster identification problem, and that is why a parallel algorithm is so needed for identifying dense clusters in a noisy background. Our algorithm works on a graph representation of the data set to be analyzed. It identifies clusters through the identification of densely intraconnected subgraphs. We have employed a minimum spanning tree (MST) representation of the graph and solve the cluster identification problem using this representation. The computational bottleneck of our algorithm is the construction of an MST of a graph, for which a parallel algorithm is employed. Our high-level strategy for the parallel MST construction algorithm is to first partition the graph, then construct MSTs for the partitioned subgraphs and auxiliary bipartite graphs based on the subgraphs, and finally merge these MSTs to derive an MST of the original graph. The computational results indicate that when running on 150 CPUs, our algorithm can solve a cluster identification problem on a data set with 1,000,000 data points almost 100 times faster than on single CPU, indicating that this program is capable of handling very large data clustering problems in an efficient manner. We have implemented the clustering algorithm as the software CLUMP.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S.F. Altschul et al., "Gapped BLAST and PSI-BLAST: A New Generation of Protein Database Search Programs," Nucleic Acids Research, vol. 25, pp. 3389-3402, 1997.
	2	David A. Bader , Guojing Cong, A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs), Journal of Parallel and Distributed Computing, v.65 n.9, p.994-1006, September 2005 [doi>10.1016/j.jpdc.2005.03.011]
	3	J.L. Bentley, "Parallel Algorithm for Constructing Minimum Spanning Trees," J. Algorithms, vol. 1, pp. 51-59, 1980.
	4	James C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Kluwer Academic Publishers, Norwell, MA, 1981
	5	Christopher M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, Inc., New York, NY, 1995
	6	O. Bor¿vka, "O jistém problému minimálnim. Práce Mor.P¿orodoved," Spol. v Brne (Acta Societ. Natur. Moravicae), vol. 3, pp. 37-58, 1926.
	7	C. Dass, An Introduction to Biological Mass Spectrometry. John Wiley & Sons, 2002.
	8	R. Dementiev, P. Sanders, and D. Schultes, "Engineering an Eternal Memory Minimum Spanning Tree Algorithm," Proc. Third IFIP Int'l Conf. Theoretical Computer Science (TCS '04), pp. 195-208, 2004.
	9	Z. Du , F. Lin, A novel parallelization approach for hierarchical clustering, Parallel Computing, v.31 n.5, p.523-527, May 2005 [doi>10.1016/j.parco.2005.01.001]
	10	A.J. Enright, S. Van Dongen1, and S.A. Ouzounis, "An Efficient Algorithm for Large-Scale Detection of Protein Families," Nucleic Acids Research, vol. 30, no. 7, pp. 1575-1584, 2002.
	11	R.D. Finn et al., "PFAM: Clans, Web Tools and Services," Nucleic Acids Research, vol. 34, pp. 247-251, 2006.
	12	H.-R. Gregorius, "The Isolation Approach to Hierarchical Clustering," J. Classification, vol. 21, pp. 51-69, 2004.
	13	Donald B. Johnson , Panagiotis Metaxas, A parallel algorithm for computing minimum spanning trees, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.363-372, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141917]
	14	X. Li and Z. Fang, "Parallel Clustering Algorithms," Parallel Computing, vol. 11, pp. 275-290, 1989.
	15	Two-Hybrid Systems: Methods and Protocols (Methods in Molecular Biology), P.N. Macdonald, ed., vol. 177. The Humana Press Inc., 2001.
	16	Fionn Murtagh, Clustering in massive data sets, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	17	V. Olman, D. Xu, and Y. Xu, "CUBIC: Identification of Regulatory Binding Sites through Data Clustering," J. Bioinformatics and Computational Biology, vol. 1, no. 1, pp. 21-40, 2003.
	18	V. Olman, C. Hicks, P. Wang, and X. Ying, "Gene Expression Data Analysis in Subtypes of Ovarian Cancer Using Covariance Analysis," J. Bioinformatics and Computational Biology, vol. 4, no. 5, pp. 999-1013, 2006.
	19	Clark F. Olson, Parallel algorithms for hierarchical clustering, Parallel Computing, v.21 n.8, p.1313-1325, Aug. 1995 [doi>10.1016/0167-8191(95)00017-I]
	20	E. M. Rasmussen , P. Willett, Efficiency of hierarchic agglomerative clustering using the ICL distributed array processor, Journal of Documentation, v.45 n.1, p.1-24, March 1989 [doi>10.1108/eb026836]
	21	H.C. Romesburg, Cluster Analysis for Researchers, 2004.
	22	Handbook of Discrete and Combinatorial Mathematics, K.H. Rosen, ed. CRC Press, 1999.
	23	R. Sibson, "SLINK: An Optimally Efficient Algorithm for the Single Link Cluster Methods," Computer J., vol. 16, pp. 30-34, 1973.
	24	R.L. Tatusov, E.V. Koonin, and D.J. Lipman, "A Genomic Perspective on Protein Families," Science, vol. 278, pp. 631-637, 1997.
	25	R.L. Tatusov, D.A. Natale, I.V. Garkavtsev, T.A. Tatusova, U.T. Shankavaram, B.S. Rao, B. Kiryutin, M.Y. Galperin, N.D. Fedorova, and E.V. Koonin, "The COG Database: New Developments in Phylogenetic Classification of Proteins from Complete Genomes," Nucleic Acids Research, vol. 29, pp. 22-28, 2001.
	26	S.S. Wilks, Mathematical Statistics. John Wiley & Sons, 1962.
	27	Hongwei Wu , Fenglou Mao , Victor Olman , Ying Xu, Accurate Prediction of Orthologous Gene Groups in Microbes, Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference, p.73-79, August 08-11, 2005 [doi>10.1109/CSB.2005.10]
	28	H. Wu, Z. Su, F. Mao, V. Olman, and Y. Xu, "Prediction of Functional Modules through Comparative Genome Analysis and Application of Gene Ontology," Nucleic Acids Research, vol. 33, pp. 2822-2837, 2005.
	29	H. Wu, F. Mao, V. Olman, and X. Ying, "Hierarchical Classification of Functionally Equivalent Genes of Prokaryotes," Nuclear Acids Research, vol. 35, pp. 2125-2140, 2007.
	30	Y. Xu, V. Olman, and D. Xu, "Clustering Gene Expression Data Using a Graph-Theoretic Approach: An Application of Minimum Spanning Tree," Bioinformatics, vol. 18, no. 4, pp. 526-535, 2001.