An algorithm for clustering cDNAs for gene expression analysis

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...