On the complexity and approximation of syntenic distance

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity and approximation of syntenic distance

Full text

Pdf (1.20 MB)

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: 99 - 108

Year of Publication: 1997

ISBN:0-89791-882-7

Authors

B. DasGupta	Department of Computer Science, Rutgers University, Camden, NJ
T. Jiang	Department of Computer Science, McMaster University, Hamilton, Ontario L8S 4K1, Canada
S. Kannan	Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA
M. Li	Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong
Z. Sweedyk	Department of Computer and Information Sciences, University of Pennsylvania, Philadelphia, PA

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): 1, Downloads (12 Months): 16, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	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.267536 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	V. Bafna and P. Pevzner. Genome Rearrangements and Sorting by Reversals. in 3dth IEEE Syrup. on Foundations of Computer Science, 1993, pp. 148- 157.
	2	V. Bafna and P. Pevzner. Sorting by Reversals: Genome Rearrangements in Plant Organelles and Evolutionary History of X Chromosome. Mol. Biol. and Evol., 12, 1995, pp. 239-246.
	3	Vineet Bafna , Pavel Pevzner, Sorting permutations by tanspositions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.614-623, January 22-24, 1995, San Francisco, California, United States
	4	B. DasGupta, T. Jiang, S. Kannan, M. Li and Z. Sweedyk. On the Complexity and Approximation of Syntenic Distance. University of Pennsylvania Technical Report MS-CIS-96-21.
	5	Vincent Ferretti , Joseph H. Nadeau , David Sankoff, Original Synteny, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.159-167, June 10-12, 1996
	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	Sridhar Hannenhalli , Pavel Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.178-189, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225112]
	8	S. Kannan and Z Sweedyk. A Separator Theorem for Directed Acyclic Graphs. University of Pennsylvania Tehnical Report MS-CIS-96-20.
	9	John D. Kececioglu , R. Ravi, Of mice and men: algorithms for evolutionary distances between genomes with translocation, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.604-613, January 22-24, 1995, San Francisco, California, United States
	10	John D. Kececioglu , David Sankoff, Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes, Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching, p.87-105, June 02-04, 1993
	11	John D. Kececioglu , David Sankoff, Efficient Bounds for Oriented Chromosome Inversion Distance, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.307-325, June 05-08, 1994
	12	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982