Fast practical solution of sorting by reversals

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast practical solution of sorting by reversals

Full text

Pdf (946 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 12 - 21

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

Alberto Caprara	DEIS, Università di Bologna, Viale Risorgimento 2, 40136, Bologna, Italy
Giuseppe Lancia	DEI, Università di Padova, Via Gradenigo 6/A, 35131, Padova, Italy
See Kiong Ng	Smithkline Beecham Pharmaceuticals R&D, Bioinformatics, New Frontiers Science Park North, Third Avenue, Harlow, Essex, CM19 5AW, UK

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

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

Additional Information:

references index terms collaborative colleagues

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

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	Cynthia Barnhart , Ellis L. Johnson , George L. Nemhauser , Martin W. P. Savelsbergh , Pamela H. Vance, Branch-And-Price: Column Generation for Solving Huge Integer Programs, Operations Research, v.46 n.3, p.316-329, March 1998 [doi>10.1287/opre.46.3.316]
	3	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
	4	P. Berman and M. Karpinski, "On Some Tighter inapproximability Results", ECCC Report No. 29 (1998), University of Trier, 1998.
	5	M. Blanchette, personal communication.
	6	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]
	7	A. Caprara, "On the Tightness of the Alternating- Cycle Lower Bound for Sorting by Reversals", Journal of Combinatorial Optimization 3 (1999) 149-182.
	8	A. Caprara, G. Lancia and S.K. Ng, "A Column- Generation Based Branch-and-Bound Algorithm for Sorting by Reversals", in M. Farach-Colton, Fred S. Roberts, M. Vingron and M. Waterman (eds.) Mathematical Support for Molecular Biology; DIMACS Series in Discrete Mathematics and Theoretical Computer Science 47 (1999) 213-226, AMS Press.
	9	G. Carpaneto, S. Marteilo and P. Toth, "Algorithms and Codes for the Assignment Problem", Annals of Operations Research 13 (1988) 193-223.
	10	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
	11	William Cook , Andre Rohe, Computing Minimum-Weight Perfect Matchings, INFORMS Journal on Computing, v.11 n.2, p.138-148, February 1999 [doi>10.1287/ijoc.11.2.138]
	12	M. Farach-Colton, Fred S. Roberts, M. Vingron and M. Waterman (eds.) Mathematical Support for Molecular Biology; DIMA CS Series in Discrete Mathematics and Theoretical Computer Science 47 (1999), AMS Press.
	13	N. Franklin, "Conservation of genome form but not sequence in the transcription antitermlnation determinants of bacteriophages ,~, ~b21 and P22", Journal of Molecular Evolution 181 (1985) 75-84.
	14	A.M.H. Gerards, "Matching", in M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser (eds.), Networks; Handbooks in Operations Research and Management Sciences, North Holland (1995).
	15	M. GrStschel, L. Lov~z and A. Schrijver, ~The Ellipsoid Method and its Consequences in Combinatorial Optimization", Combinatorica 1 (1981), 169-197.
	16	S. Hannenhalli, personal communication.
	17	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]
	18	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
	19	R.W. Irving and D.A. Christie, "Sorting by Reversals: a Conjecture of Kececioglu and Sankoff', Working Paper (1996), Dept. of Computer Science, University of Glasgow.
	20	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
	21	L.G. Khachian, "A Polynomial Algorithm for Linear Programming", Soviet Mathematics Doldady 20 (1979.) 191-194.
	22	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
	23	J. Kececioglu and D. Sankoff, "Exact and Approximation Algorithms for Sorting by Reversals, with Application to Genome Rearrangement", Algorithmiea 13 (1995) 180-210.
	24	D. Sankoff, G. Stmdaram and J. Kececioglu, "Steiner Points in the Space of Genome Rearrangements", International Journal of Foundations of Computer Science 7 (1996) 1-9.
	25	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