Fast optimal leaf ordering for hierarchical clustering
BioinformaticsPublished 1 June 2001Open access
Ziv Bar‐Joseph, David K. Gifford, Tommi Jaakkola
Citations571
SJR quartileQ1
SJR score2.45
SNIP1.47
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We present the first practical algorithm for the optimal linear leaf ordering of trees that are generated by hierarchical clustering. Hierarchical clustering has been extensively used to analyze gene expression data, and we show how optimal leaf ordering can reveal biological structure that is not observed with an existing heuristic ordering method. For a tree with n leaves, there are 2(n-1) linear orderings consistent with the structure of the tree. Our optimal leaf ordering algorithm runs in time O(n(4)), and we present further improvements that make the running time of our algorithm practical.
Keywords
Computer ScienceAgricultural and Biological SciencesBiochemistry, Genetics and Molecular Biology
Proceedings of the National Academy of SciencesCluster analysis and display of genome-wide expression patterns
16,395 Citations1998Michael B. Eisen, Paul T. Spellman +2 more
A system of cluster analysis for genome-wide expression data from DNA microarray hybridization is described that uses standard statistical algorithms to arrange genes according to similarity in pattern of gene expression, finding in the budding yeast Saccharomyces cerevisiae that clustering gene expression data groups together efficiently genes of known similar function.
NatureDistinct types of diffuse large B-cell lymphoma identified by gene expression profiling
9,951 Citations2000Ash A. Alizadeh, Michael B. Eisen +29 more
It is shown that there is diversity in gene expression among the tumours of DLBCL patients, apparently reflecting the variation in tumour proliferation rate, host response and differentiation state of the tumour.
Molecular Biology of the CellComprehensive Identification of Cell Cycle–regulated Genes of the Yeast<i>Saccharomyces cerevisiae</i>by Microarray Hybridization
4,799 Citations1998Paul T. Spellman, Gavin Sherlock +7 more
A comprehensive catalog of yeast genes whose transcript levels vary periodically within the cell cycle is created, and it is found that the mRNA levels of more than half of these 800 genes respond to one or both of these cyclins.
Proceedings of the National Academy of SciencesBroad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays
4,210 Citations1999Uri Alon, Naama Barkai +5 more
A two-way clustering method is reported for analyzing a data set consisting of the expression patterns of different cell types, revealing broad coherent patterns that suggest a high degree of organization underlying gene expression in these tissues.
Proceedings of the National Academy of SciencesInterpreting patterns of gene expression with self-organizing maps: Methods and application to hematopoietic differentiation
2,946 Citations1999Pablo Tamayo, Donna K. Slonim +6 more
The application of self-organizing maps, a type of mathematical cluster analysis that is particularly well suited for recognizing and classifying features in complex, multidimensional data, is described.
Molecular Biology of the CellRemodeling of Yeast Genome Expression in Response to Environmental Changes
1,389 Citations2001Helen C. Causton, Bing Ren +8 more
The results of expression analysis with MSN2/MSN4 mutants support the model that the Msn2/Msn4 activators induce the common response to environmental change and extend the understanding of the role of activators in effecting this response.
arXiv (Cornell University)Fast hierarchical clustering and other applications of dynamic closest pairs
39 Citations1998David Eppstein