K-ary clustering with optimal leaf ordering for gene expression data

@article{citeulike:1982347, abstract = {Motivation: A major challenge in gene expression analysis is effective data organization and visualization. One of the most popular tools for this task is hierarchical clustering. Hierarchical clustering allows a user to view relationships in scales ranging from single genes to large sets of genes, while at the same time providing a global view of the expression data. However, hierarchical clustering is very sensitive to noise, it usually lacks of a method to actually identify distinct clusters, and produces a large number of possible leaf orderings of the hierarchical clustering tree. In this paper we propose a new hierarchical clustering algorithm which reduces susceptibility to noise, permits up to k siblings to be directly related, and provides a single optimal order for the resulting tree Results: We present an algorithm that efficiently constructs a k-ary tree, where each node can have up to k children, and then optimally orders the leaves of that tree. By combining k clusters at each step our algorithm becomes more robust against noise and missing values. By optimally ordering the leaves of the resulting tree we maintain the pairwise relationships that appear in the original method, without sacrificing the robustness. Our k-ary construction algorithm runs in O(n3) regardless of k and our ordering algorithm runs in O(4kn3). We present several examples that show that our k-ary clustering algorithm achieves results that are superior to the binary tree results in both global presentation and cluster identification Availability: We have implemented the above algorithms in C++ on the Linux operating system. Source code is available upon request from zivbj@mit.edu Contact: zivbj@mit.edu 10.1093/bioinformatics/btg030}, author = {Bar-Joseph, Ziv and Demaine, Erik D. and Gifford, David K. and Srebro, Nathan and Hamel, Angele M. and Jaakkola, Tommi S. }, citeulike-article-id = {1982347}, doi = {10.1093/bioinformatics/btg030}, journal = {Bioinformatics}, keywords = {bioinformatics, clustering, mev, microarray}, month = {June}, number = {9}, pages = {1070--1078}, posted-at = {2008-03-10 15:41:39}, priority = {2}, title = {K-ary clustering with optimal leaf ordering for gene expression data}, url = {http://dx.doi.org/10.1093/bioinformatics/btg030}, volume = {19}, year = {2003} }

TY - JOUR ID - citeulike:1982347 L3 - citeulike-article-id:1982347 TI - K-ary clustering with optimal leaf ordering for gene expression data JF - Bioinformatics VL - 19 IS - 9 SP - 1070 EP - 1078 N2 - Motivation: A major challenge in gene expression analysis is effective data organization and visualization. One of the most popular tools for this task is hierarchical clustering. Hierarchical clustering allows a user to view relationships in scales ranging from single genes to large sets of genes, while at the same time providing a global view of the expression data. However, hierarchical clustering is very sensitive to noise, it usually lacks of a method to actually identify distinct clusters, and produces a large number of possible leaf orderings of the hierarchical clustering tree. In this paper we propose a new hierarchical clustering algorithm which reduces susceptibility to noise, permits up to k siblings to be directly related, and provides a single optimal order for the resulting tree Results: We present an algorithm that efficiently constructs a k-ary tree, where each node can have up to k children, and then optimally orders the leaves of that tree. By combining k clusters at each step our algorithm becomes more robust against noise and missing values. By optimally ordering the leaves of the resulting tree we maintain the pairwise relationships that appear in the original method, without sacrificing the robustness. Our k-ary construction algorithm runs in O(n3) regardless of k and our ordering algorithm runs in O(4kn3). We present several examples that show that our k-ary clustering algorithm achieves results that are superior to the binary tree results in both global presentation and cluster identification Availability: We have implemented the above algorithms in C++ on the Linux operating system. Source code is available upon request from zivbj@mit.edu Contact: zivbj@mit.edu 10.1093/bioinformatics/btg030 KW - bioinformatics KW - clustering KW - mev KW - microarray AU - Bar-Joseph, Ziv AU - Demaine, Erik AU - Gifford, David AU - Srebro, Nathan AU - Hamel, Angele AU - Jaakkola, Tommi PY - 2003/06/12/ UR - http://dx.doi.org/10.1093/bioinformatics/btg030 ER -