Clustering pair-wise dissimilarity data into partially ordered sets

ABSTRACT

Ontologies represent data relationships as hierarchies of possibly overlapping classes. Ontologies are closely related to clustering hierarchies, and in this article we explore this relationship in depth. In particular, we examine the space of ontologies that can be generated by pairwise dissimilarity matrices. We demonstrate that classical clustering algorithms, which take dissimilarity matrices as inputs, do not incorporate all available information. In fact, only special types of dissimilarity matrices can be exactly preserved by previous clustering methods. We model ontologies as a partially ordered set (poset) over the subset relation. In this paper, we propose a new clustering algorithm, that generates a partially ordered set of clusters from a dissimilarity matrix.

REFERENCES

• 1: M. Ashburner, C. A. Ball, J. A. Blake, D. Botstein, H. Butler, J. M. Cherry, A. P. Davis, K. Dolinski, S. S. Dwight, J. T. Eppig, M. A. Harris, D. P. Hill, L. Issel-Tarver, A. Kasarskis, S. Lewis, J. C. Matese, J. E. Richardson, M. Ringwald, G. M. Rubin, G. Sherlock: Gene Ontology: tool for the unification of biology. Nat Genet 2000, 25:25--29.
• 2: Applications of the pyramidal clustering method to biological objects. Comput Chem, 23(3-4):303--15, Jun 15, 1999.
• 3: P. Berkhin. Survey of clustering data mining techniques https://umdrive.memphis.edu/vphan/public/berkhin-survey.pdf, Accrue Software, 2002.
• 4: P. Bertrand , M. F. Janowitz, Pyramids and weak hierarchies in the ordinal model for clustering, Discrete Applied Mathematics, v.122 n.1-3, p.55-81, 15 October 2002 [doi>10.1016/S0166-218X(01)00354-7 ]
• 5: Coen Bron , Joep Kerbosch, Algorithm 457: finding all cliques of an undirected graph, Communications of the ACM, v.16 n.9, p.575-577, Sept. 1973 [doi>10.1145/362342.362367]
• 6: Budanitsky, A., and G. Hirst, "Semantic Distance in WordNet: An Experimental, Application-oriented Evaluation of Five Measures", Workshop on WordNet and Other Lexical Resources, in the North American Chapter of the Association for Computational Linguistics (NAACL-2001), Pittsburgh, PA, June 2001.
• 7: E. Diday, Orders and overlapping clusters in pyramids. In: J. De Leeuw et al. Multidimensional Data Analysis, DSWO Press, Leiden (1986), pp. 201--234.
• 8: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 9: L. K. Hua, Introduction to Number Theory. Springer-Verlag, New York, 1982.
• 10: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 11: Cliff A. Joslyn , Susan M. Mniszewski , Andy Fulmer , Gary Heaton, The Gene Ontology Categorizer, Bioinformatics, v.20 n.1, p.169-177, January 2004 [doi>10.1093/bioinformatics/bth921]
• 12: Jose L. Sevilla , Victor Segura , Adam Podhorski , Elizabeth Guruceaga , Jose M. Mato , Luis A. Martinez-Cruz , Fernando J. Corrales , Angel Rubio, Correlation between Gene Expression and GO Semantic Similarity, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.4, p.330-338, October 2005 [doi>10.1109/TCBB.2005.50]
• 13: R. M. Karp Reducibility among combinatorial problems. Complexity of computer computations, Plenum Press, New York, pp.85--103, 1972.
• 14: L. Kaufman and P. Rousseeuw, Finding groups in data: an introduction to cluster analysis. New York: John Wiley and Sons, 1990.
• 15: Gangmin Li , Victoria Uren , Enrico Motta , Simon Buckingham Shum , John Domingue, ClaiMaker: Weaving a Semantic Web of Research Papers, Proceedings of the First International Semantic Web Conference on The Semantic Web, p.436-441, June 09-12, 2002
• 16: P. W. Lord, R. Stevens, A. Brass, and C. A.Goble. Investigating semantic similarity measures across the Gene Ontology: the relationship between sequence and annotation. Bioinformatics, 19(10):1275--83, 2003.
• 17: W. T. McCormick, P. J. Schweitzer, and T. W. White. Problem decomposition and data reorganization by a clustering technique. Operations Research, 20:993--1009, 1972.
• 18: P. T. Spellman, G. Sherlock, M. Q.Zhang, V. R. Lyer, K. Anders, M. B. Eisen, P. O. Brown, D. Botstein, and Futcher. Comprehensive identification of cell cycle-regulated genes of the yeast sacccharomyces cerevisiae by microaray hybidization. Molecular Biology of the Cell, 9:3273--2297, 1998.
• 19: S. Tavazoie, J. D. Hughes, M. J. Campbell, R. J. Cho and G. Church. Systematic determination of genetic network architecture. Nature Genetics 22: 281--285, 1999.
• 20: Haiying Wang , Francisco Azuaje, An Ontology-Driven Clustering Method for Supporting Gene Expression Analysis, Proceedings of the 18th IEEE Symposium on Computer-Based Medical Systems (CBMS'05), p.389-394, June 23-24, 2005 [doi>10.1109/CBMS.2005.29]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
PoCluster, clustering, dissimilarity, poset