Sorting signed permutations by short operations

详细信息    查看全文

• 作者：Gustavo Rodrigues Galv?o ; Orlando Lee ; Zanoni Dias
• 关键词：Genome rearrangement ; Short reversals ; Short transpositions
• 刊名：Algorithms for Molecular Biology
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：10
• 期：1
• 全文大小：721 KB
• 参考文献：1. Gascuel, O (2005) Mathematics of evolution and phylogeny. Oxford University Press, Inc., New York, New York, USA
  2. Saitou, N, Nei, M (1987) The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol. 4: pp. 406-25
  3. Fertin, G, Labarre, A, Rusu, I, Tannier, E, Vialette, S (2009) Combinatorics of genome rearrangements. The MIT Press, Cambridge, Massachusetts, USA CrossRef
  4. Caprara, A (1999) Sorting permutations by reversals and eulerian cycle decompositions. SIAM J Discrete Math. 12: pp. 91-110 CrossRef
  5. Watterson, GA, Ewens, WJ, Hall, TE, Morgan, A (1982) The chromosome inversion problem. J Theor Biol. 99: pp. 1-7 CrossRef
  6. Berman, P, Hannenhalli, S, Karpinski, M (2002) 1.375-approximation algorithm for sorting by reversals. Proceedings of the 10th Annual European Symposium on Algorithms (ESA-002), Lecture Notes in Computer Science, vol.2461. Springer, Rome, Italy
  7. Bafna, V, Pevzner, PA (1996) Genome rearrangements and sorting by reversals. SIAM J Comput. 25: pp. 272-89 CrossRef
  8. Hannenhalli, S, Pevzner, PA (1999) Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM 46: pp. 1-27 CrossRef
  9. Tannier, E, Bergeron, A, Sagot, MF (2007) Advances on sorting by reversals. Discrete Appl Math. 155: pp. 881-8 CrossRef
  10. Bader, D, Moret, B, Yan, M (2001) A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. J Comput Biol. 8: pp. 483-91 CrossRef
  11. Bulteau, L, Fertin, G, Rusu, I (2012) Sorting by transpositions is difficult. SIAM J Discrete Math. 26: pp. 1148-80 CrossRef
  12. Bafna, V, Pevzner, PA (1998) Sorting by transpositions. SIAM J Discrete Math. 11: pp. 224-40 CrossRef
  13. Elias, I, Hartman, T (2006) A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Trans Comput Biol Bioinf. 3: pp. 369-79 CrossRef
  14. Walter, MEMT, Dias, Z, Meidanis, J (1998) Reversal and transposition distance of linear chromosomes. Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE-998). IEEE Computer Society, Santa Cruz, Bolivia
  15. Rahman, A, Shatabda, S, Hasan, M (2008) An approximation algorithm for sorting by reversals and transpositions. J Discrete Algorithms 6: pp. 449-57 CrossRef
  16. Gu, Q, Peng, S, Sudborough, IH (1999) A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theor Comput Sci. 210: pp. 327-39 CrossRef
  17. Jerrum, MR (1985) The complexity of finding minimum-length generator sequences. Theor Comput Sci. 36: pp. 265-89 CrossRef
  18. Heath, LS, Vergara, JPC (2003) Sorting by short swaps. J Comput Biol. 10: pp. 775-89 CrossRef
  19. Heath, LS, Vergara, JPC (1998) Sorting by bounded block-moves. Discrete Appl Math. 88: pp. 181-206 CrossRef
  20. Heath, LS, Vergara, JPC (2000) Sorting by short blockmoves. Algorithmica 28: pp. 323-54 CrossRef
  21
• 刊物主题：Bioinformatics; Computational Biology/Bioinformatics; Physiological, Cellular and Medical Topics; Algorithms;
• 出版者：BioMed Central
• ISSN：1748-7188

文摘

Background During evolution, global mutations may alter the order and the orientation of the genes in a genome. Such mutations are referred to as rearrangement events, or simply operations. In unichromosomal genomes, the most common operations are reversals, which are responsible for reversing the order and orientation of a sequence of genes, and transpositions, which are responsible for switching the location of two contiguous portions of a genome. The problem of computing the minimum sequence of operations that transforms one genome into another -which is equivalent to the problem of sorting a permutation into the identity permutation -is a well-studied problem that finds application in comparative genomics. There are a number of works concerning this problem in the literature, but they generally do not take into account the length of the operations (i.e. the number of genes affected by the operations). Since it has been observed that short operations are prevalent in the evolution of some species, algorithms that efficiently solve this problem in the special case of short operations are of interest. Results In this paper, we investigate the problem of sorting a signed permutation by short operations. More precisely, we study four flavors of this problem: (i) the problem of sorting a signed permutation by reversals of length at most 2; (ii) the problem of sorting a signed permutation by reversals of length at most 3; (iii) the problem of sorting a signed permutation by reversals and transpositions of length at most 2; and (iv) the problem of sorting a signed permutation by reversals and transpositions of length at most 3. We present polynomial-time solutions for problems (i) and (iii), a 5-approximation for problem (ii), and a 3-approximation for problem (iv). Moreover, we show that the expected approximation ratio of the 5-approximation algorithm is not greater than 3 for random signed permutations with more than 12 elements. Finally, we present experimental results that show that the approximation ratios of the approximation algorithms cannot be smaller than 3. In particular, this means that the approximation ratio of the 3-approximation algorithm is tight.