A branch-and-cut approach to physical mapping with end-probes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A branch-and-cut approach to physical mapping with end-probes

Full text

Pdf (980 KB)

Source

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

Santa Fe, New Mexico, United States

Pages: 84 - 92

Year of Publication: 1997

ISBN:0-89791-882-7

Authors

Thomas Christof	Institut für Angewandte Mathematik, Universität Heidelberg, Germany
Michael Jünger	Institut für Informatik, Vniversität zu Köln, Germany
John Kececioglu	Department of Computer Science, Univ. of Georgia, Athens
Petra Mutzel	Max-Planck-Institut für Informatik, Saarbrücken, Germany
Gerhard Reinelt	Institut für Angewandte Mathematik, Universität Heidelberg, Germany

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
DOE : Department of Energy

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	AKNW95	F. Alizadeh, R.M. Karp, L.A. Newberg, and D.K. Weisser. Physical mapping of chromosomes: A combinatorial problem in molecular biology. Algorithmica, 13(1/2):52-76, 1995.
	AKWZ94	Farid Alizadeh , Richard M. Karp , Deborah K. Weisser , Geoffrey Zweig, Physical mapping of chromosomes using unique probes, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.489-500, January 23-25, 1994, Arlington, Virginia, United States
	BL76	K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. of Computer and System Sciences, 13:335-379, 1976.
	Boo75	Kellogg Speed Booth, Pq-tree algorithms., 1975
	CR96	T. Christof and G. Reinelt. Combinatorial optimization and small polytopes. Top, 4(1):1-64, 1996. Spanish Statistical and Operations Research Society.
	CS95	Benny Chor , Madhu Sudan, A Geometric Approach to Betweenness, Proceedings of the Third Annual European Symposium on Algorithms, p.227-237, September 25-27, 1995
	GDHC95	W. Gillett, J. Danes, L. Hanks, and R. Capra. Fragment collapsing and splitting while assembling high-resolution restriction maps. J. Computational Biology, 2(2):185-205, 1995.
	GI95	D.S. Greenberg and S. Istrail. Physical mapping by STS hybridization: Algorithmic strategies and the challenge of software evaluation. J. Computational Biology, 2(2):219-273, 1995.
	GJR84	M. GrStschel, M. JSnger, and G. Reinelt. A cutting plane algorithm for the linear ordering problem. Operations Research, 32:1195-1220, 1984.
	GJR85	M. GrStschel, M. Jfinger, and G. Reinelt. Facets of the linear ordering polytope. Mathematical Programming, 33:43-60, 1985.
	JM95	M. Jain and G. Myers. A note on scoring clones given a probe ordering. Journal of Computational Biology, 2(1):33-38, 1995.
	JRT94	M. J'fmger, G. Reinelt, and S. Thienel. Optimal and provably good solutions for the symmetric traveling salesman problem. Zeitschrift ftir Operations Research, 40:183-217, 1994.
	JRT95	M. J/inger, G. Reinelt, and S. Thienel. Practical problem solving with cutting plane algorithms in combinatorial optimization. In L. Lovksz W. Cook and P. Seymour, editors, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume ~0: Combinatorial Optimization. Amer. Math. Soc., 1995.
	MGL94	R. Mort, A. Grigoriev, and H. Lehrach. An algorithm to detect chimeric clones and random noise in genomic mapping. Genomics, 22:482- 486, 1994.
	MHM+93	E. Maier, J. Hoheisel, R. Mott, A. Grigoriev, and If. Lehrach. Algorithms and software tools for ordering clone libraries: Application to the mapping of the genome of schizosaccharomyces pombe. Nucleic Acids Res., 21:1965-1974, 1993.
	Opa79	J. Opatrny. Total ordering problem. SIAM J. Comput., 8(1):111-114, 1979.
	Thi95	S. Thienel. ABACUS A Branch-And-CUt System. PhD thesis, Universit~it zu KSln, 1995.
	VLM96	M. Vingron, H.P. Lenhof, and P. Mutzel. Computational molecular biology. In M. DeU'Amico, F. Maflioli, and S. Martello, editors, to appear in Annotat. Bibliographies in Comb. Opt., chapter 23. 1996. Tech. Rep. MPI-I-96-1-012, Max- Planck-Institut f. Informatik (1996).

CITED BY 3

	Hans-Peter Lenhof , Knut Reinert , Martin Vingron, A polyhedral approach to RNA sequence structure alignment, Proceedings of the second annual international conference on Computational molecular biology, p.153-162, March 22-25, 1998, New York, New York, United States
	Giuseppe Lancia, Integer programming models for computational biology problems, Journal of Computer Science and Technology, v.19 n.1, p.60-77, January 2004
	Rolf Backofen , David Gilbert, Bioinformatics and Constraints, Constraints, v.6 n.2-3, p.141-156, June 2001