Formulations and hardness of multiple sorting by reversals

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Formulations and hardness of multiple sorting by reversals

Full text

Pdf (1.50 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: 84 - 93

Year of Publication: 1999

ISBN:1-58113-069-4

Author

Alberto Caprara

DEIS, University of Bologna, Viale Risorgimento 2, 40136, Bologna, Italy

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): 4, Downloads (12 Months): 18, Citation Count: 10

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.299461 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	Vineet Bafna , Pavel A. Pevzner, Genome Rearrangements and Sorting by Reversals, SIAM Journal on Computing, v.25 n.2, p.272-289, February 1996 [doi>10.1137/S0097539793250627]
	2	Piotr Berman , Sridhar Hannenhalli, Fast Sorting by Reversal, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.168-185, June 10-12, 1996
	3	P. Berman and M. Karpinski, "On Some Tighter Inapproximability Results", ECCC Report No. 29 (1998), University of Trier, 1998.
	4	M. Blanchette, G. Bourque and D. Sankoff, "Breakpoint Phylogenies", in S. Miyano and T. Takagi (eds.), Proceedings of Genome Informatics 1997 (1997) 25-34, Universal Academy Press.
	5	Alberto Caprara, Sorting Permutations by Reversals and Eulerian Cycle Decompositions, SIAM Journal on Discrete Mathematics, v.12 n.1, p.91-110, Jan. 1999 [doi>10.1137/S089548019731994X]
	6	A. Caprara, "On the Tightness of the Alternating-Cycle Lower Bound for Sorting by Reversals", to appear in Journal of Combinatorial Optimization.
	7	A. Caprara, G. Lancia and S.K. Ng, "A Column- Generation Based Branch-and-Bound Algorithm for Sorting By Reversals", to appear in DIMA C$ Series in Discrete Mathematics and Theoretical Computer $cief~Cag.
	8	David A. Christie, A 3/2-approximation algorithm for sorting by reversals, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.244-252, January 25-27, 1998, San Francisco, California, United States
	9	M. GriStschel, L. Lovksz and A. Schrijver, "The Ellipsoid Method and its Consequences in Combinatorial Optimization", Combinatorica I (1981), 169-197.
	10	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	11	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]
	12	Sridhar Hannenhalli , Pavel Pevzner, To cut…or not to cut (applications of comparative physical maps in molecular evolution), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.304-313, January 28-30, 1996, Atlanta, Georgia, United States
	13	R.W. Irving and D.A. Christie, "Sorting by Reversals: a Conjecture of Kececioglu and Sankoff', Working Paper (1995), Dept. of Computer Science, University of Glasgow.
	14	M. J'tinger, G. Reinelt and G. Rinaldi, "The trayeling salesman problem", in M. Ball, T. Magnanti, C. Monma, G. Nemhauser (eds.), Network Models, Handbooks in Operations Research and Management Science 7 (1995) 225-330, Elsevier.
	15	Haim Kaplan , Ron Shamir , Robert E. Tarjan, Faster and simpler algorithm for sorting signed permutations by reversals, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.344-351, January 05-07, 1997, New Orleans, Louisiana, United States
	16	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
	17	J. Kececioglu and D. Sankoff, "Exact and Apprc0dmarion Algorithms for Sorting by Reversals, with A pplication to Genome Rearrangement", Algorithmica 13 (1995) 180-210.
	18	I. Pe'er and R. Shamir, "The Median Problems for Breakpoints are NP-Complete", ECCC Report No. 71 (1998), University of Trier, 1998.
	19	Open Combinatorial Problems in computational Molecular Biology, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.158, January 04-06, 1995
	20	David Sankoff , Mathieu Blanchette, The Median Problem for Breakpoints in Comparative Genomics, Proceedings of the Third Annual International Conference on Computing and Combinatorics, p.251-264, August 20-22, 1997
	21	David Sankoff , Mathieu Blanchette, Multiple genome rearrangements, Proceedings of the second annual international conference on Computational molecular biology, p.243-247, March 22-25, 1998, New York, New York, United States [doi>10.1145/279069.279122]
	22	D. Sankoff, G. Sundaram and J. Kececioglu, "Steiner Points in the Space of Genome Rearrangements", International Journal of Foundations of Computer Science 7 (1996) 1-9.
	23	J. Setubal and J. Meidanis, Introduction tO Computational Molecular Biology (1997), PWS Publising.
	24	Nicholas Q. Trân, An Easy Case of Sorting by Reversals, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.83-89, June 30-July 02, 1997

CITED BY 10

	Bernard M. E. Moret , Jijun Tang , Li-San Wang , Tandy Warnow, Steps toward accurate reconstructions of phylogenies from gene-order data, Journal of Computer and System Sciences, v.65 n.3, p.508-525, November 2002
	David Sankoff , David Bryant , Mélanie Deneault , B. Franz Lang , Gertraud Burger, Early eukaryote evolution based on mitochondrial gene order breakpoints, Proceedings of the fourth annual international conference on Computational molecular biology, p.254-262, April 2000, Tokyo, Japan
	Kamalika Chaudhuri , Kevin Chen , Radu Mihaescu , Satish Rao, On the tandem duplication-random loss model of genome rearrangement, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.564-570, January 22-26, 2006, Miami, Florida
	Glenn Tesler, Efficient algorithms for multichromosomal genome rearrangements, Journal of Computer and System Sciences, v.65 n.3, p.587-609, November 2002
	Mark Marron , Krister M. Swenson , Bernard M. E. Moret, Genomic distances under deletions and insertions, Theoretical Computer Science, v.325 n.3, p.347-360, 6 October 2004
	Niklas Eriksen, Reversal and transposition medians, Theoretical Computer Science, v.374 n.1-3, p.111-126, April, 2007
	Adrien Goeffon , Macha Nikolski , David J. Sherman, An efficient probabilistic population-based descent for the median genome problem, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	V. Yu. Popov, Multiple genome rearrangement by swaps and by element duplications, Theoretical Computer Science, v.385 n.1-3, p.115-126, October, 2007
	Enno Ohlebusch , Mohamed I. Abouelhoda , Kathrin Hockel, A linear time algorithm for the inversion median problem in circular bacterial genomes, Journal of Discrete Algorithms, v.5 n.4, p.637-646, December, 2007
	Krister M. Swenson , Mark Marron , Joel V. Earnest-Deyoung , Bernard M. E. Moret, Approximating the true evolutionary distance between two genomes, Journal of Experimental Algorithmics (JEA), 12, June 2008