An algorithm for clustering cDNAs for gene expression analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An algorithm for clustering cDNAs for gene expression analysis

Full text

Pdf (1.19 MB)

Source

Annual Conference on Research in Computational Molecular Biology archive
Proceedings of the third annual international conference on Computational molecular biology table of contents

Lyon, France

Pages: 188 - 197

Year of Publication: 1999

ISBN:1-58113-069-4

Authors

Erez Hartuv	Department of Computer Science, Sackler Faculty of Exact Sciences, Tel-Aviv University, Tel-Aviv 69976 ISRAEL
Armin Schmitt	Max Planck Institute for molecular genetics, Ihnestrasse 73, D-14195 Berlin, Germany
Jörg Lange	Max Planck Institute for molecular genetics, Ihnestrasse 73, D-14195 Berlin, Germany
Sebastian Meier-Ewert	Max Planck Institute for molecular genetics, Ihnestrasse 73, D-14195 Berlin, Germany
Hans Lehrach	Max Planck Institute for molecular genetics, Ihnestrasse 73, D-14195 Berlin, Germany
Ron Shamir	Department of Computer Science, Sackler Faculty of Exact Sciences, Tel-Aviv University, Tel-Aviv 69976 ISRAEL

Sponsors

INRIA : Institut Natl de Recherche en Info et en Automatique
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 26, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/299432.299483 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	F. Alisadeh, R. M. Karp, L. A. Newberg, and D. K. Weisser. Physical mapping of chromosomes: A combinatorical problem in molecular biology. Algorithmica, 13:52-76, 1995.
	2	F. Buckley and F. Harary. Distance in graphs. Addisonwesley, 1990.
	3	It. Drrnanac G. Lennon S. Drmanac I. Labat R. Crkvenjakov and H. Lehrach. Partial sequencing by oligohybridi~tion: Concept and applications in genome analysis. In Proceedings of the first international couference on dectrophoresis supercomputing and the human gerwme Edited by C. Cantor and H. Lira, pages 60-75, Singapore, 1991. World Scientific.
	4	S. Drmanac and R. Drrnanac. Processing of cDNA and genomic kilobeze-size clones for massive screening mapping and sequencing by hybridization. Biotechni~es, 17:328--336, 1994.
	5	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	6	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	7	Pierre Hansen , Brigitte Jaumard, Cluster analysis and mathematical programming, Mathematical Programming: Series A and B, v.79 n.1-3, p.191-215, Oct. 1, 1997 [doi>10.1007/BF02614317]
	8	John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
	9	E. Hartuv. Cluster analysis by highly connected subgraphs with applications to cDNA clustering. Master's thesis, Department of Computer Science, Tel Aviv University, August 1998.
	10	N. Jardine and R. 5ibson. Mathematical taxonomy. John Wiley and sons, London, 1971.
	11	David R. Karger, Minimum cuts in near-linear time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.56-63, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237829]
	12	L. Zhang W. Zhou V.E. Velculescu S.E. Kern R.H. Hruban S.R. Hamilton B. Vogelstein K.W. Kinzler. Gene expression profiles in normal and cancer cells. Science, 276:1268-1272, 1997.
	13	S. Meier-Ewert J. Lange H. Gerst R. Herwig A. 5chmitt J. Freund T. Elge R. Mott B. Herrmann H. Lehrach. Comparative gene expression profiling by oligonucleotide fingerprinting. Nucleic Acids Research, 26(9):2216-2223, 1998.
	14	G.5. Lennon and H. Lehrach. Hybridization analysis of arrayed eDNA libraries. Trends Genet, 7:60-75, 1991.
	15	D.W. Matula. The cohesive strength of graphs. In The many facets of graph theory, Lecture notes in Mathematics No. 110, Edited by G. Chartrand and S.F. Kapoor, pages 215-221, Berlin, 1969. Springer-Verlag.
	16	D.W. Matula. Cluster analysis via graph theoretic techniques. In R.C Mullin K.B Reid and D.P Roselle, editors, Proc. Louisiana co~ference on combinatorics graph theory and computing, pages 199-212. University of manitoba Winnipeg, 1970.
	17	D.W. Matula. k-Components, clusters and slicings in graphs. SIAM Y. App!. Math., 22(3):459-480, 1972.
	18	D.W. Matula. Graph theoretic techniques for cluster analysis algorithms. In Classification and clustering Edited By Y. Van Ryzin, pages 95-129. Academic Press, 1977.
	19	D.W. Matula. Determining edge connectivity in O(nm). In Proceedings lath IEEE symposis~m on foundations of computer science, pages 249-251, 1987.
	20	Guy Mayraz , Ron Shamir, Construction of physical maps from oligonucleotide fingerprints data, Proceedings of the third annual international conference on Computational molecular biology, p.268-277, April 11-14, 1999, Lyon, France [doi>10.1145/299432.299497]
	21	Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Communications of the ACM, v.38 n.1, p.96-102, Jan. 1995 [doi>10.1145/204865.204889]
	22	5. Meier-Ewert, R. Mott, and H. Lehrach. Gene identification by oligonucleotide fingerprinting-- a pilot study. Technical report, MPI, 1995.
	23	F. Michiels, A. G. Craig, G. Zehetner, G. P. Smith, and H. Lehrach. Molecular approaches to genome analysis: a strategy for the construction of ordered overlapping clone libraries. CABIO$, 3(3):203-210, 1987.
	24	A. Milosavljevic, Z. Strezoska, M. Zeremski, D. Grujic, T. Paunesku, and R. Crkvenjakov. Clone clustering by hybridization. Ge~omics, 27:83-89, 1995.
	25	B. Mirkin. Mathematical classification and clustering. Kluwer academic publishers, 1996.
	26	Hiroshi Nagamochi , Toshihide Ibaraki, Computing edge-connectivity in multigraphs and capacitated graphs, SIAM Journal on Discrete Mathematics, v.5 n.1, p.54-66, Feb. 1992 [doi>10.1137/0405004]
	27	D. M. Platt. and T. I. Dix. Comparison of clone-ordering algorithms used in physical mapping. Genomics, 40:490- 492, 1997.
	28	S. Drmanac N. A. Stavropoulos I. Labat J. Vonau B. Hauser M. B. Soares and R. Drmanac. Gene-representing eDNA clusters defined by hybridization of $7419 clones from infant brain libraries with short oligonucleotide probes. Genotnics, 37:29-40, 1996.
	29	R. R. Sokal. Clustering and classification: Background and current directions. In C!assi~cagion and clusgering Edited By Y. Van Ryzin, pages 1-15. Academic Press, 1977.
	30	Mechthild Stoer , Frank Wagner, A simple min-cut algorithm, Journal of the ACM (JACM), v.44 n.4, p.585-591, July 1997 [doi>10.1145/263867.263872]
	31	R. Drmanac S. Drmanac I. Labat R. Crkvenjakov A. Vicentic and A. Gemmell. Sequencing by hybridization: towards an automated sequencing of one milion M13 clones arrayed on membranes. Elecgrophor~sis, 13:566--573, 1992.
	32	Z. Wu , R. Leahy, An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.11, p.1101-1113, November 1993 [doi>10.1109/34.244673]

CITED BY 6

	Chris Bailey-Kellogg , Alik Widge , John J. Kelley, III , Marcelo J. Berardi , John H. Bushweller , Bruce Randall Donald, The NOESY jigsaw: automated protein secondary structure and main-chain assignment from sparse, unassigned NMR data, Proceedings of the fourth annual international conference on Computational molecular biology, p.33-44, April 2000, Tokyo, Japan
	Suchendra M. Bhandarkar , Tongzhang Jiang , Kunal Verma , Nan Li, Automated analysis of DNA hybridization images for high-throughput genomics, Machine Vision and Applications, v.15 n.3, p.121-138, July 2004
	Lizhuang Zhao , Mohammed J. Zaki, TRICLUSTER: an effective algorithm for mining coherent clusters in 3D microarray data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Michael A. Langston , Andy D. Perkins , Arnold M. Saxton , Jon A. Scharff , Brynn H. Voy, Innovative computational methods for transcriptomic data analysis, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	M. T. Thai , Z. Cai , D. Z. Du, Genetic networks: processing data, regulatory network modelling and their analysis, Optimization Methods & Software, v.22 n.1, p.169-185, February 2007
	Jorge M. Santos , Joaquim Marques de Sa , Luis A. Alexandre, LEGClust—A Clustering Algorithm Based on Layered Entropic Subgraphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.30 n.1, p.62-75, January 2008