Paper by Erik D. Demaine
- Ziv Bar-Joseph, Erik D. Demaine, David K. Gifford, Angèle M. Hamel, Tommi S. Jaakkola, and Nathan Srebro, “K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data”, in Proceedings of the 2nd Workshop on Algorithms in Bioinformatics (WABI 2002), Rome, Italy, September 17–21, 2002, pages 506–520.
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. Our
algorithm 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. By optimally ordering the leaves of the tree we maintain the
pairwise relationships that appear in the original method. Our k-ary
construction algorithm runs in O(n3) regardless of k
and our ordering algorithm runs in
We present several examples that show that our k-ary clustering
algorithm achieves results that are superior to the binary tree results.
- This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2452/24520506.pdf.
- The paper is \copyright Springer-Verlag.
- The paper is 15 pages.
- The paper is available in PostScript (1013k), gzipped PostScript (317k), and PDF (269k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- GeneExpression_Bioinformatics (K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data)
- GeneExpression_UWTR2001 (Optimal Arrangement of Leaves in the Tree Representing Hierarchical Clustering of Gene Expression Data)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 2, 2021 by