An algorithm for clustering cDNAs for gene expression analysis
- 1 April 1999
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 188-197
- https://doi.org/10.1145/299432.299483
Abstract
We have developed a novel algorithm for cluster analysisthat is based on graph theoretic techniques. A similaritygraph is defined and clusters in that graph correspond tohighly connected subgraphs. A polynomial algorithm tocompute them efficiently is presented. Our algorithm producesa clustering with some provably good properties.The application that motivated this study was gene expressionanalysis, where a collection of cDNAs must be clusteredbased on their oligonucleotide...Keywords
This publication has 18 references indexed in Scilit:
- Cluster analysis and mathematical programmingMathematical Programming, 1997
- A simple min-cut algorithmJournal of the ACM, 1997
- Clone Clustering by HybridizationGenomics, 1995
- Physical mapping of chromosomes: A combinatorial problem in molecular biologyAlgorithmica, 1995
- LEDA: a platform for combinatorial and geometric computingCommunications of the ACM, 1995
- An optimal graph theoretic approach to data clustering: theory and its application to image segmentationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1993
- Computing Edge-Connectivity in Multigraphs and Capacitated GraphsSIAM Journal on Discrete Mathematics, 1992
- Sequencing by hybridization: Towards an automated sequencing of one million M13 clones arrayed on membranesElectrophoresis, 1992
- Hybridization analyses of arrayed cDNA librariesTrends in Genetics, 1991
- The cohesive strength of graphsPublished by Springer Nature ,1969