Mapping the genome

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Mapping the genome: some combinatorial problems arising in molecular biology

Full text

Pdf (870 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 278 - 285

Year of Publication: 1993

ISBN:0-89791-591-7

Author

Richard M. Karp

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 59, Citation Count: 13

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

	AB89	F.M. Ausubel, R. Brent, R.E. King,#ton, et al. "Current Protocols in Molecular Biology." 1989
	AK92	Farid Alizadeh , Richard M. Karp , Lee A. Newberg , Deborah K. Weisser, Physical mapping of chromosomes: a combinatorial problem in molecular biology, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.371-381, January 25-27, 1993, Austin, Texas, United States
	BD91	E. Barrilot, J. Dausset and D. Cohen. "Theoretical Analysis of a Physical Mapping Strategy Using Random Single Copy Landmarks." Proc. Natl. Acad. Sci. USA Vol. 88, pp 3917-3921. 1991
	BJ91	Avrim Blum , Tao Jiang , Ming Li , John Tromp , Mihalis Yannakakis, Linear approximation of shortest superstrings, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.328-336, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103455]
	BL76	K.S. Booth and G.S. Lueker. "Testing for Consecutive Ones Property, Interval Graphs and Planarity Using PQ-Tree Algorithms." Journal of Computer Systems Science Vol. 13, pp 335- 379. 1976
	BS90	E. Branscomb, T. Slezak, R. Pae, D. Galas, A.V. Carrano and M. Waterman. "Constructing Chromosome-and Region-Specific Cosmid Maps of the Human Genome." Genome Vol. 31(2), pp 1059-1065. 1989
	CL89	A.V. Carrano, J. Lamerdin, L.K. Ashworth, et al. "A High-Resolution, Fluorescence-Based, Semiautomated Method for DNA Fingerprinting." Genomics Vol. 4, pp 129-136. 1989
	CL89	A.V. Cerrano, J. Lamerdin, L.K. Ashworth, B. Watkins, E. Branscomb, T. Slezak, M. Raft, P.j. DeJong, D. Keith, L. McBride, S. Meister and M. Kronick. "A High Resolution Fluorescence-based, Semi-automated Method of DNA Fingerprinting." Genomics Vol. 4, pp 129-136. 1989
	CN90	A.G. Craig, D. Nizetic, J.D. Hoheisel, G. Zehetner and H. Lehrach. "Ordering of Cosmid Clones Covering the Herpes Simplex Virus Type I (HSV-I) Genome: A Test Case for Fingerprinting by Hybridisation." Nucleic Acids Research Vol. 18(9), pp 2653-2660. 1990
	DL89	R. Drmanac, i. Labat, I. Bruckner and R. Crkvenajakov. "Sequencing of Magebase Plus DNA by Hybridization: Theory of a Method." Genomics Vol. 4, pg 114. 1989
	EL89	G.A. Evans and K.A. Lewis. "Physical Mapping of Complex Genomes by Cosmid Multiplex Analysis." Proc. Nat'l. Acad. Sci. USA Vol. 86, pp 5030-5034. 1989
	F85	P.C. Fishburn. "Interval Orders and Interval Graphs." John Wiley pp 35-56 1985
	FG65	D.R. Fulkerson and O.A. Gross. "incidence Matrices abd Interval Graphs." Pacific Journal of Math Vol. 15, pp 835-855. 1965
	FS83	W.M. Fitch, T.F. Smith and W.W. Ralph. "Mapping the Order of DNA Restriction Fragments." Gene Vol. 22, pp 19-29. 1983
	GK92	M.C. Golumbic, H. Kaplan and R. Shamir. "Graph Sandwich Problems" Tech report, The Moise and Frida Eskansky Institute of Computer Sciences No. 270/92, December, 1992
	GM80	J. Gallant, D. Maier and :I. Storer. "On Finding a Minimal Length Superstring." Journal of Computer Systems Science Vol. 20, pp 50-58. 1980
	GO90	E.D. Green and M.V. Olson. "Chromosomal Region of the Cystic Fibrosis Gene in Yeast Artificial Chromosomes: A Model for Human Genome Mapping." Science Vol. 250, pp 94-98. 1990
	GS92	M.C. Golumbic and R. Shamir. "Complexity and Algorithms for Reasoning About Time: A Graph-Theoretic Approach." Proc. Israel Symposium on Theory of Computing 1992
	GW91	L. Gonick, M. Wheelis, "The Cartoon Guide to Genetics," Harper 1991
	K88	M. Krawczak. "Algorithms for the Restriction Site Mapping of DNA Molecules." Proc. Na#l. Acad. Sci. USA Vol. 85, pp 7298-7301. 1988
	K91	John Dimitri Kececioglu, Exact and approximation algorithms for DNA sequence reconstruction, University of Arizona, Tucson, AZ, 1992
	KA87	Y. Kohara, A. Akiyama and K. Isono. "The Physical Map of the Whole E. Coli Chromosome: Application of a New Strategy for Rapid Analysis and Sorting of a Large Genomic Library." Cell Vol. 50, pp 495-508. 1987
	KM89	Norbert Korte , Rolf H. Möhring, An incremental linear-time algorithm for recognizing interval graphs, SIAM Journal on Computing, v.18 n.1, p.68-81, Feb. 1989 [doi>10.1137/0218005]
	KN93	R. Karp, L. Newberg, "An Algorithm for the Probed Partial Digest Reconstruction Problem," submitted to CABIOS 1993
	L90	B. Lewin. "Genes IV" Cell Press and Ozford University Press, 1990
	LI90	P. Little. "Clone Maps Made Simple." Nature Vol. 346, pp 611-12. 1990
	LD91	H. Lehrach, R. Drmanac, :I. Hoheisel, et al. "Hybridization Fingerprinting in Genome Mapping and Sequencing." Genome Analysis Vol. 1, pp 39-81. 1991
	LK73	S. Lin and W. Kernighan. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem." Operations Research Vol. 21, No. 2. 1973
	LW88	E.S. Lander and M.S. Waterman. "Genomic Mapping by Fingerprinting Random Clones: A Mathematical Analysis." Genomics Vol. 2, pp 231-239. 1988
	NN92	Lee Aaron Newberg , Dalit Naor, A lower bound on the number of solutions to the probed partial digest problem, Advances in Applied Mathematics, v.14 n.2, p.172-183, June 1993 [doi>10.1006/aama.1993.1009]
	OD86	M.V. Olson, :I.E. Dutchik, M.Y. Graham, et al. "Random-Clone Strategy for Genomic Restriction Mapping in Yeast." Proc. Natl. A cad. Sci. USA Vol. 83, pp 7826-7830. 1986
	P82	W. Pearson. "Automatic Construction of Restriction Site Maps." Nucleic Acids Res. Vol. 10, pp 217-227. 1982
	P89	P.A. Pevzner. "L-tuple DNA Sequencing: Computer Analysis." Journal of Biomolecular Structural Dynamics. Vol. 7, pp 63-73. 1989
	PD84	G. Polner, L. Dorgai and L. Orosz. "PMAP. PMAPS: DNA Physical Map Construction Programs." Nucleic Acids Res. Vol 12, pp 227-236. 1984
	PL91	P.A. Pevzner, Y.P. Lysov, K.R. Khrapko, A.V. Belyavsky, V.L. Florentiev and A.D. Mirzabekov. "Improved Chips for Sequencing by Hybridization." Journal of Biomolecular Structure and Dynamics Vol. 9, Issue No. 2, pp 399-410. 1991
	S78	M. Stefik. "Inferring DNA Structure from Segmentation Data." Artificial Intelligence Vol. 11, pp 85-114. 1978
	SP91	Z.Strezoska, T. Paunesku, D.Radosavljevic, I.Labat, R.Drmanac, R.Crkvenjakov. "DNA Sequencing by Hybridization: 100 Bases Read by a Non-Gel-Based Method." Proc. Natl. Acad. Sci., USA Vol. 88, pp 10089-10093, 1991
	SS90	Steven S. Skiena , Warren D. Smith , Paul Lemke, Reconstructing sets from interpoint distances (extended abstract), Proceedings of the sixth annual symposium on Computational geometry, p.332-339, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98598]
	ST90	R.L. Stallings, D.C. Torney, C.E. Hildebrand, et al. "Physical Mapping of Human Chromosomes by Repetitive Sequence Fingerprinting." Proceedings of the National Academy of Sciences Vol. 87, pp 6218-22. 1990
	SW91	William Schmitt , Michael S. Waterman, Multiple solutions of DNA restriction mapping problems, Advances in Applied Mathematics, v.12 n.4, p.412-427, Dec. 1991 [doi>10.1016/0196-8858(91)90028-H]
	T89	J. S. Turner, Approximation algorithms for the shortest common superstring problem, Information and Computation, v.83 n.1, p.1-20, Oct. 1989 [doi>10.1016/0890-5401(89)90044-8]
	T91	D. Torney. "Mapping Using Unique Sequences." Journal of Molecular Bioiogy Vol. 2t7, pp 259.- 264. 1991
	TB91	D.C. Torney and D.:I. Balding. "Statistical Analysis of DNA Fingerprint Data for Ordered{ Clone Physical Mapping of Human Chromosomes." Bulletin of Mathematical Biology Voi. 53, No. 6, pp 853-879. 1991
	TD88	P. Tuffery , P. Dussen, C. Mugnier and S. Hazout. "Restriction Map Construction Using a Complete Sentences Comparability Algorithm." Computer Applications in the Bio-. sciences Vol. 4, No. 1, pp 103-110. 1988
	TO92	K. Tynan, A. Olsen, B. Trask, et al. "Assembly' and Analysis of Cosmid Contigs in the CEA Gene Family Region of Human Chromosome 19." Nucleic Acids Research Vol. 18, No. 9. pp 2653-2660. 1990
	W91	C. Wills. Exons, introns and Talking Genes Basic Books, 1991
	WG86	M.S. Waterman and :I.R. Griggs. "Interval{ Graphs and Maps of DNA." Bull. of Math. Biol. Vol. 48, pp. 189-195. 1986
	WH87	:i. Watson, N. Hopkins, J. Roberts, :I. Steitz, A. Weiner, "Molecular Biology of the Gene," Fourth Edition, Benjamin/Cummings 1987

CITED BY 13

	S. Muthukrishnan , Laxmi Parida, Towards constructing physical maps by optical mapping (extended abstract): an effective, simple, combinatorial approach, Proceedings of the first annual international conference on Computational molecular biology, p.209-219, January 20-23, 1997, Santa Fe, New Mexico, United States
	Bodo Manthey, Non-approximability of weighted multiple sequence alignment, Theoretical Computer Science, v.296 n.1, p.179-192, 4 March 2003
	Michael C. Loui, Strategic directions in research in theory of computing, ACM Computing Surveys (CSUR), v.28 n.4, p.575-590, Dec. 1996
	Christos H. Papadimitriou, Database metatheory: asking the big queries, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, May 22-25, 1995, San Jose, California, United States
	Josep Díaz , Jordi Petit , Maria Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002
	Tao Jiang , Richard M. Karp, Mapping clones with a given ordering or interleaving, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.400-409, January 05-07, 1997, New Orleans, Louisiana, United States
	Jeong Seop Sim , Kunsoo Park, The consensus string problem for a metric is NP-complete, Journal of Discrete Algorithms, v.1 n.1, p.111-117, February 2003
	Andrei Krokhin , Peter Jeavons , Peter Jonsson, Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra, Journal of the ACM (JACM), v.50 n.5, p.591-640, September 2003
	Tao Jiang , Eugene L. Lawler , Lusheng Wang, Aligning sequences via an evolutionary tree: complexity and approximation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.760-769, May 23-25, 1994, Montreal, Quebec, Canada
	Sheng-Lung Peng , Chi-Kang Chen, On the interval completion of chordal graphs, Discrete Applied Mathematics, v.154 n.6, p.1003-1010, 15 April 2006
	Peter Z. Revesz, Refining Restriction Enzyme Genome Maps, Constraints, v.2 n.3-4, p.361-375, 1997
	Christos H. Papadimitriou, Database metatheory: asking the big queries, ACM SIGACT News, v.26 n.3, p.13-30, Sept. 1995
	Josep Díaz , Mathew D. Penrose , Jordi Petit , María Serna, Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs, Combinatorics, Probability and Computing, v.9 n.6, p.489-511, November 2000