New approximations for block sorting

• Bafna V, Pavel PA (1998) Sorting by transpositions. SIAM J Discrete Math

• Bafna V, Pevzner PA (1996) Genome rearrangements and sorting by reversals. SIAM J Comput 25(2):272–289. doi:10.1137/S0097539793250627

  Article  MathSciNet  MATH  Google Scholar 

• Bein WW, Larmore LL, Latifi S, Sudborough IH (2003) Block sorting is hard. Int J Found Comput Sci 14(03):425–437

  Article  MathSciNet  MATH  Google Scholar 

• Bein WW, Larmore LL, Morales L, Sudborough IH (2009) A quadratic time 2-approximation algorithm for block sorting. Theor Comput Sci 410(8):711–717

  Article  MathSciNet  MATH  Google Scholar 

• Bulteau L, Fertin G, Rusu I (2001) Sorting by transpositions is difficult. In: Proceedings of the 38th international colloquim conference on automata, languages and programming—volume part I, ICALP’11. Springer, Berlin, pp 654–665. http://dl.acm.org/citation.cfm?id=2027127.2027197

• Bulteau L, Fertin G, Rusu I (2012) Pancake flipping is hard. In: Proceedings of the 37th international conference on mathematical foundations of computer science, MFCS’12. Springer, Berlin, pp 247–258. doi:10.1007/978-3-642-32589-2_24

• Caprara A (1997) Sorting by reversals is difficult. In: Proceedings of the first annual international conference on computational molecular biology, RECOMB ’97. ACM, New York, NY, USA, pp 75–83. doi:10.1145/267521.267531, http://doi.acm.org/10.1145/267521.267531

• Christie D, Irving R (2001) Sorting strings by reversals and by transpositions. SIAM J Discrete Math 14(2):193–206. doi:10.1137/S0895480197331995

  Article  MathSciNet  MATH  Google Scholar 

• Christie DA (1996) Sorting permutations by block-interchanges. Inf Process Lett 60(4):165–169

  Article  MathSciNet  MATH  Google Scholar 

• Christie DA (1999) Genome rearrangement problems. Ph.D. thesis

• Elias I, Hartman T (2006) A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Trans Comput Biol Bioinform 3(4):369–379. doi:10.1109/TCBB.2006.44

  Article  Google Scholar 

• Firoz JS, Hasan M, Khan AZ, Rahman MS (2011) The 1.375 approximation algorithm for sorting by transpositions can run in o (n log n) time. J Comput Biol 18(8):1007–1011

  Article  MathSciNet  MATH  Google Scholar 

• Gates WH, Papadimitriou CH (1979) Bounds for sorting by prefix reversal. Discrete Math 27(1):47–57

  Article  MathSciNet  MATH  Google Scholar 

• Gu QP, Peng S, Sudborough H (1999) A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theor Comput Sci 210(2):327–339

  Article  MathSciNet  MATH  Google Scholar 

• Hannenhalli S, Pevzner PA (1999) Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J ACM 46(1):1–27. doi:10.1145/300515.300516. http://doi.acm.org/10.1145/300515.300516

• Hartman T, Shamir R (2006) A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Inf Comput 204(2):275–290

  Article  MathSciNet  MATH  Google Scholar 

• Huang J, Roy S (2014) On sorting under special transpositions. In: 2014 IEEE international conference on bioinformatics and bioengineering (BIBE), pp 325–328

• Lin YC, Lu CL, Chang HY, Tang CY (2005) An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species. J Comput Biol 12(1):102–112

  Article  Google Scholar 

• Mahajan M, Rama R, Raman V, Vijaykumar S (2006) Approximate block sorting. Int J Found Comput Sci 17(02):337–355

  Article  MathSciNet  MATH  Google Scholar 

• Mira C, Meidanis J (2007) Sorting by block-interchanges and signed reversals. In: Fourth International Conference on information technology, 2007, ITNG’07, pp 670–676

• Narayanaswamy N, Roy S (2015) Block sorting is apx-hard. In: Algorithms and complexity. Springer, pp 377–389

• Palmer JD, Herbon LA (1988) Plant mitochondrial dna evolved rapidly in structure, but slowly in sequence. J Mol Evol 28(1–2):87–97

  Article  Google Scholar 

Download references