Sorting by reversals is difficult

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sorting by reversals is difficult

Full text

Pdf (1.00 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: 75 - 83

Year of Publication: 1997

ISBN:0-89791-882-7

Author

Alberto Caprara

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

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): 14, Downloads (12 Months): 88, Citation Count: 25

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.267531 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	A. Caprara, G. Lancia and S.K. Ng, "A Column- Generation Based Branch-and-Bound Algorithm for Sorting by Reversals", Working Paper (1995), DEIS, University of Bologna.
	3	W.H. Gates and C.H. Papadimitriou, "Bounds for Sorting by Prefix Reversals", Discrete Mathematics 27 (1979) 47-57.
	4	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]
	5	S. Hannenhalli and P.A. Pevzner, "Reversals Do Not Cut Long Strips", Technical Report CSE-95-006, Department of Compter Science and Engineering, The Pennsylvania State University, February 1995.
	6	I. Holyer, "The NP-Completeness of Some Edge- Partition Problems", SIAM Journal on Computing 10 (~gsl) 713-717.
	7	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.
	8	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
	9	J. Kececioglu and D. Sankoff, "Exact and Approximation Algorithms for Sorting by Reversals, with Application to Genome Rearrangement", Algorithmica 13 (1995) 180-210.
	10	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

CITED BY 25

	Paul Cull , Tai Hsu, Improved parallel and sequential walking tree methods for biological string alignments, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.51-es, November 14-19, 1999, Portland, Oregon, United States
	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
	Adam C. Siepel, An algorithm to enumerate all sorting reversals, Proceedings of the sixth annual international conference on Computational biology, p.281-290, April 18-21, 2002, Washington, DC, USA
	David Sankoff , Mathieu Blanchette, Probability models for genome rearrangement and linear invariants for phylogenetic inference, Proceedings of the third annual international conference on Computational molecular biology, p.302-309, April 11-14, 1999, Lyon, France
	Sridhar Hannenhalli , Pavel A. Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Journal of the ACM (JACM), v.46 n.1, p.1-27, Jan. 1999
	Michael A. Bender , Dongdong Ge , Simai He , Haodong Hu , Ron Y. Pinter , Steven Skiena , Firas Swidan, Improved bounds on sorting with length-weighted reversals, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Alberto Moraglio , Riccardo Poli, Topological crossover for the permutation representation, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C.
	Haim Kaplan , Elad Verbin, Sorting signed permutations by reversals, revisited, Journal of Computer and System Sciences, v.70 n.3, p.321-341, May 2005
	Amihood Amir , Yonatan Aumann , Gary Benson , Avivit Levy , Ohad Lipsky , Ely Porat , Steven Skiena , Uzi Vishne, Pattern matching with address errors: rearrangement distances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1221-1229, January 22-26, 2006, Miami, Florida
	Yong He , Ting Chen, A new approximation algorithm for sorting of signed permutations, Journal of Computer Science and Technology, v.18 n.1, p.125-130, January 2003
	Daming Zhu , Lusheng Wang, On the complexity of unsigned translocation distance, Theoretical Computer Science, v.352 n.1, p.322-328, 7 March 2006
	Atif Rahman , Swakkhar Shatabda , Masud Hasan, An approximation algorithm for sorting by reversals and transpositions, Journal of Discrete Algorithms, v.6 n.3, p.449-457, September, 2008
	Xin Chen , Jie Zheng , Zheng Fu , Peng Nan , Yang Zhong , Stefano Lonardi , Tao Jiang, Assignment of Orthologous Genes via Genome Rearrangement, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.4, p.302-315, October 2005
	Petr Kolman , Tomasz Waleń, Approximating reversal distance for strings with bounded number of duplicates, Discrete Applied Mathematics, v.155 n.3, p.327-336, February, 2007
	Anne Bergeron, A very elementary presentation of the Hannenhalli-Pevzner theory, Discrete Applied Mathematics, v.146 n.2, p.134-145, 1 March 2005
	Tommaso Schiavinotto , Thomas Stützle, A review of metrics on permutations for search landscape analysis, Computers and Operations Research, v.34 n.10, p.3143-3153, October, 2007
	Kenneth Sörensen, Distance measures based on the edit distance for permutation-type representations, Journal of Heuristics, v.13 n.1, p.35-47, February 2007
	Michael A. Bender , Dongdong Ge , Simai He , Haodong Hu , Ron Y. Pinter , Steven Skiena , Firas Swidan, Improved bounds on sorting by length-weighted reversals, Journal of Computer and System Sciences, v.74 n.5, p.744-774, August, 2008
	Wolfgang W. Bein , Lawrence L. Larmore , Linda Morales , I. Hal Sudborough, A quadratic time 2-approximation algorithm for block sorting, Theoretical Computer Science, v.410 n.8-10, p.711-717, March, 2009
	Xingqin Qi , Jichang Wu , Shuguang Li , Guojun Li, Sorting by transpositions: dealing with length-weighted models, International Journal of Bioinformatics Research and Applications, v.4 n.2, p.164-171, May 2008
	Ion Petre , Vladimir Rogojin, Decision problem for shuffled genes, Information and Computation, v.206 n.11, p.1346-1352, November, 2008
	Tero Harju , Ion Petre , Vladimir Rogojin , Grzegorz Rozenberg, Patterns of simple gene assembly in ciliates, Discrete Applied Mathematics, v.156 n.14, p.2581-2597, July, 2008
	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
	Amihood Amir , Yonatan Aumann , Gary Benson , Avivit Levy , Ohad Lipsky , Ely Porat , Steven Skiena , Uzi Vishne, Pattern matching with address errors: Rearrangement distances, Journal of Computer and System Sciences, v.75 n.6, p.359-370, September, 2009