Transforming cabbage into turnip

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals

Full text

Pdf (1.23 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing table of contents

Las Vegas, Nevada, United States

Pages: 178 - 189

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Sridhar Hannenhalli
Pavel Pevzner	Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 16, Citation Count: 39

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/225058.225112 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	Martin Aigner , Douglas B. West, Sorting by insertion of leading elements, Journal of Combinatorial Theory Series A, v.45 n.2, p.306-309, July 1987 [doi>10.1016/0097-3165(87)90022-7]
	2	V. Bafna and P. Pevzner. Genome rearrangements and sort@g by reversals. In 3Jth IEEE S mp. on Foundations of Computer Science, pages ?48-157, 1993. (to appear in SIAM J. Computing).
	3	V. Bafna and P. Pevzner. Sorting by reversals: Genome rearrangements in plant organelles and evo-lutionary history of X chromosome. Mol. Biol. and Evoi., 12:239-246, 1995.
	4	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
	5	D. Cohen and M. Blum. Improved bounds for sorting pancakes under a conjecture. 1993 (manuscript).
	6	S. Even and O. Goldreich. The minimum-length generator sequence problem is NP-hard. Journal o~ Algorithms, 2:311-313, 1981.
	7	\V, H, Gates and (3. H. PaRadimitriou. Bounds for sorting by refix reversals. Discrete Mathematics, 27:47-57, lf79.
	8	S. Hannenhalli. Polynomial algorithm for computing translocation distance between genomes. In Proc: of 6th Ann. Symp. on Comb: nator:al Pattern Matching, 1995. (to appear).
	9	S. Hannenhalli, C. Chappey, E. Koonin, and P. Pevzner. Scenarios for genome rearran ements: Herpesvirus evolution as a test case. In %x. of $rd Intl. Conference on Bioinformatics and Complez Genome Analysts, 1994 (to appear).
	10	S. Hannenhalli and P. Pevzner. Reversals do not cut long strips. T=hnical. Report: CS~94-074, Department of Computer Saence and Engineering, The Pennsylvama State Umvermty, 1994.
	11	M. Heydari and I. H. Sudborough. On sorting by prefix reversals and the diameter of pancake networks. 1993 (manuscript).
	12	Mark R. Jerrum, The complexity of finding minimum-length generator sequences, Theoretical Computer Science, v.36 n.2-3, p.265-289, June 1985
	13	John Kececioglu , Dan Gusfield, Reconstructing a history of recombinations from a set of sequences, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.471-480, January 23-25, 1994, Arlington, Virginia, United States
	14	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
	15	J. Kececioglu and D. Sankoff. Exact and approxi-mation algorithms for the inversion distance between two ermutations. i" In Pmt. of ~th Ann. S mp. on # &&X'-%%2t%y :;!&h%%%:tig:%?-Iag, 1993. (Extended veraion has appeared in Algo-nthmica, 13: 180-210, 1995.).
	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	C. A. Makaroff and J. D. Palmer. Mitochondriai DNA rearrangements and transcriptional alterations ular Cellular Biology, ~1474-148/f, 1988. in the male sterrle cyto lasm of O ura rachsh. hfolec-(
	18	J. H. Nadeau and B. A. Taylor. Lengths of chromo-and mouse. Pmt. Natl. Acad. Sci. US.f, 81:814-818, aomd segments conserved since diver ence of man 1984.
	19	J. D. Palmer and L. A. Herbon. Plant mitochondrial DNA evolves rapidl in structure, but S1OW1 %$8. 1 { in uence. Journal o Molecular Evolution, 27:8 -97,
	20	P.A. Pevzner and M.S. Waterman. Open combina-torial roblems in computational molecular biology. In %/'huel Sptnpossum on Theory of Corn utmg 8 and System#, pages 156-163. IEEE Computer oaety Press. 1995.
	21	D. S&l&ff. Editdistance for genome comparison bd O&nOn-lwd 'Ytions ln 'm 'i 'd Ann. S p. on Corn matoraol pattern hfatchmg, Lecture otes in Computer Saence 644, pages 121- 135. Springer Verlag, 1992.
	22	D. Sankoff, R. Cedergren, and Y. Abel. Genomic di-ver ence through ene rearrangement. In Molecular 5 f Evo ution: Compu er Analysis of Protein and Nucleic Acid S encea, chapter 26, pages 428-438. Academic T Press, 1 90.
	23	D. Sankoff, G. Leduc, N. Antoine, B. Paquin, B. F. Lan , and IL Cedergren. Gene order compa@ons for h ~ enetic inference Evolution of the mltochon-~ % 'enome Pmt. Nati. Acad. Sci. USA, 89:6575- 6;79,?992. "
	24	A. H. Strutevant and T. Dobzhansky. Inversions in the third chromosome of wild. races of dwo hila /' seudoobscum, and their use m the study o the &story of the species. Proc. Nat. Acad. Sci., 22:448- 450, 1936.
	25	G. A. Watterson, W. J. Ewens, T. E. Hall, and . . . . A. Morgan. The chromosome mverraon problem. Journal of Theoretical Biology, 99:1-7, 1982.

CITED BY 39

	Pavel Pevzner , Glenn Tesler, Transforming men into mice: the Nadeau-Taylor chromosomal breakage model revisited, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.247-256, April 10-14, 2003, Berlin, Germany
	B. DasGupta , T. Jiang , S. Kannan , M. Li , Z. Sweedyk, On the complexity and approximation of syntenic distance, Proceedings of the first annual international conference on Computational molecular biology, p.99-108, January 20-23, 1997, Santa Fe, New Mexico, United States
	Li-San Wang , Tandy Warnow, Estimating true evolutionary distances between genomes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.637-646, July 2001, Hersonissos, Greece
	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
	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
	Alberto Caprara , Giuseppe Lancia , See Kiong Ng, Fast practical solution of sorting by reversals, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.12-21, January 09-11, 2000, San Francisco, California, United States
	Pavel A. Pevzner , Haixu Tang , Michael S. Waterman, A new approach to fragment assembly in DNA sequencing, Proceedings of the fifth annual international conference on Computational biology, p.256-267, April 22-25, 2001, Montreal, Quebec, Canada
	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
	Alberto Caprara, Formulations and hardness of multiple sorting by reversals, Proceedings of the third annual international conference on Computational molecular biology, p.84-93, April 11-14, 1999, Lyon, France
	Leslie Ann Goldberg , Paul W. Goldberg , Mike Paterson , Pavel Pevzner , Süleyman Cenk Sahinalp , Elizabeth Sweedyk, The complexity of gene placement, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.386-395, January 17-19, 1999, Baltimore, Maryland, United States
	Niklas Eriksen, (1 + ɛ)-Approximation of sorting by reversals and transpositions, Theoretical Computer Science, v.289 n.1, p.517-529, 23 October 2002
	Haim Kaplan , Ron Shamir , Robert E. Tarjan, Faster and simpler algorithm for sorting signed permutations by reversals, Proceedings of the first annual international conference on Computational molecular biology, p.163, January 20-23, 1997, Santa Fe, New Mexico, United States
	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
	Nadia El-Mabrouk, Reconstructing an ancestral genome using minimum segments duplications and reversals, Journal of Computer and System Sciences, v.65 n.3, p.442-464, November 2002
	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
	Alberto Caprara, Sorting by reversals is difficult, Proceedings of the first annual international conference on Computational molecular biology, p.75-83, January 20-23, 1997, Santa Fe, New Mexico, United States
	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
	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
	Ming Li , Xin Chen , Xin Li , Bin Ma , Paul Vitányi, The similarity metric, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	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
	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
	David A. Bader, Computational biology and high-performance computing, Communications of the ACM, v.47 n.11, November 2004
	Lusheng Wang , Daming Zhu , Xiaowen Liu , Shaohan Ma, An O(n²) algorithm for signed translocation, Journal of Computer and System Sciences, v.70 n.3, p.284-299, May 2005
	Tzvika Hartman , Ron Shamir, A simpler and faster 1.5-approximation algorithm for sorting by transpositions, Information and Computation, v.204 n.2, p.275-290, February 2006
	Robert Brijder , Hendrik Jan Hoogeboom , Grzegorz Rozenberg, Reducibility of gene patterns in ciliates using the breakpoint graph, Theoretical Computer Science, v.356 n.1, p.26-45, 5 May 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
	Yun Cui , Lusheng Wang , Daming Zhu, A 1.75-approximation algorithm for unsigned translocation distance, Journal of Computer and System Sciences, v.73 n.7, p.1045-1059, November, 2007
	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
	Matthias Bernt , Daniel Merkle , Martin Middendorf, Genome Rearrangement Based on Reversals that Preserve Conserved Intervals, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.3, p.275-288, July 2006
	Géraldine Jean , Macha Nikolski, Genome rearrangements: a correct algorithm for optimal capping, Information Processing Letters, v.104 n.1, p.14-20, September, 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
	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
	Yun Cui , Lusheng Wang , Daming Zhu , Xiaowen Liu, A (1.5 + ε)-Approximation Algorithm for Unsigned Translocation Distance, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.1, p.56-66, January 2008
	Matthias Bernt , Daniel Merkle , Martin Middendorf, Solving the Preserving Reversal Median Problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.3, p.332-347, July 2008
	Xin Chen , Lan Liu , Zheng Liu , Tao Jiang, On the minimum common integer partition problem, ACM Transactions on Algorithms (TALG), v.5 n.1, p.1-18, November 2008
	Esra Erdem , Elisabeth Tillier, Genome rearrangement and planning, Proceedings of the 20th national conference on Artificial intelligence, p.1139-1144, July 09-13, 2005, Pittsburgh, Pennsylvania
	Nikolay Vyahhi , Adrien Goëffon , Macha Nikolski , David James Sherman, Swarming along the evolutionary branches sheds light on genome rearrangement scenarios, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada