An approximation algorithm for sorting by reversals and transpositions. (English) Zbl 1186.92035
Summary: Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. We present a \(2k\)-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where \(k\) is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of \(k\) our approximation ratio becomes \(2.8386+\delta \) for any \(\delta >0\). We also derive a lower bound on reversal and transposition distance of an unsigned permutation.
MSC:
| 92D15 | Problems related to evolution |
| 92C40 | Biochemistry, molecular biology |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C90 | Applications of graph theory |
| 92-08 | Computational methods for problems pertaining to biology |
Keywords:
genome rearrangement; sorting by reversals and transpositions; breakpoints in a permutation; cycle decomposition graph; maximum cycle decomposition; approximation algorithmReferences:
| [1] | Bafna, V.; Pevzner, P., Genome rearrangements and sorting by reversals, SIAM Journal on Computing, 25, 272-289 (1996), in: Proc. of 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS’93), 1993, pp. 148-157. Also in · Zbl 0844.68123 |
| [2] | Bafna, V.; Pevzner, P., Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11, 2, 224-240 (May 1998) · Zbl 0973.92014 |
| [3] | Berman, P.; Hannenhalli, S.; Karpinski, M., 1.375-approximation algorithm for sorting by reversals, (Proc. of 10th European Symposium on Algorithms (ESA’02). Proc. of 10th European Symposium on Algorithms (ESA’02), Lecture Notes in Computer Science, vol. 2461 (2002), Springer), 200-210 · Zbl 1019.68817 |
| [4] | Blanchette, M.; Kunisawa, T.; Sankoff, D., Parametric genome rearrangement, Gene, 172 (1996), GC11-17 |
| [5] | A. Caprara, Sorting by reversals is difficult, in: Proc. of 1st ACM Conference on Research in Computational Molecular Biology (RECOMB’97), 1997, pp. 75-83; A. Caprara, Sorting by reversals is difficult, in: Proc. of 1st ACM Conference on Research in Computational Molecular Biology (RECOMB’97), 1997, pp. 75-83 |
| [6] | Caprara, A.; Rizzi, R., Improved approximation for breakpoint graph decomposition and sorting by reversals, Journal of Combinatorial Optimization, 6, 2, 157-182 (2002) · Zbl 0993.05113 |
| [7] | D. Christie, A 3/2 approximation algorithm for sorting by reversals, in: Proc. of 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98), 1998, pp. 244-252; D. Christie, A 3/2 approximation algorithm for sorting by reversals, in: Proc. of 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98), 1998, pp. 244-252 · Zbl 0930.68044 |
| [8] | D. Christie, Genome rearrangement problems, PhD thesis, Department of Computer Science, University of Glasgow, 1999; D. Christie, Genome rearrangement problems, PhD thesis, Department of Computer Science, University of Glasgow, 1999 |
| [9] | Elias, I.; Hartman, T., A 1.375-approximation algorithm for sorting by transpositions, (Proc. of 5th International Workshop on Algorithms in Bioinformatics (WABI’05). Proc. of 5th International Workshop on Algorithms in Bioinformatics (WABI’05), Lecture Notes in Computer Science, vol. 3692 (October 2005), Springer), 204-214 |
| [10] | Eriksen, N., \((1 + \&z.epsi;)\)-approximation of sorting by reversals and transpositions, Theoretical Computer Science, 289, 1, 517-529 (2002) · Zbl 1061.68038 |
| [11] | Eriksson, H.; Eriksson, K.; Karlander, J.; Svensson, L.; Wastlund, J., Sorting a bridge hand, Discrete Mathematics, 241, 1-3, 289-300 (2001) · Zbl 0990.05145 |
| [12] | Gu, Q.; Peng, S.; Sudborough, H., A 2-approximation algorithm for genome rearrangements by reversals and transpositions, Theoretical Computer Science, 210, 2, 327-339 (1999) · Zbl 0915.68033 |
| [13] | S. Hannenhalli, P. Pevzner, Transforming cabbage into turnip, in: Proc. of 27th Annual ACM Symposium on Theory of Computing (STOC’95), 1995, pp. 178-189; S. Hannenhalli, P. Pevzner, Transforming cabbage into turnip, in: Proc. of 27th Annual ACM Symposium on Theory of Computing (STOC’95), 1995, pp. 178-189 · Zbl 0978.68530 |
| [14] | Hartman, T., A simpler 1.5-approximation algorithm for sorting by transpositions, (Proc. of 14th Annual Symposium on Combinatorial Pattern Matching (CPM’03). Proc. of 14th Annual Symposium on Combinatorial Pattern Matching (CPM’03), Lecture Notes in Computer Science, vol. 2676 (2003), Springer), 156-169 · Zbl 1279.68071 |
| [15] | Hartman, T.; Sharan, R., A 1.5-approximation algorithm for sorting by transpositions and transreversals, (Proc. of 4th International Workshop on Algorithms in Bioinformatics (WABI’04). Proc. of 4th International Workshop on Algorithms in Bioinformatics (WABI’04), Lecture Notes in Computer Science, vol. 3242 (2004), Springer), 50-61 |
| [16] | Hoot, S.; Palmer, J., Structural rearrangements, including parallel inversions, within the chloroplast genome of anemone and related genera, Journal of Molecular Evolution, 38, 274-281 (1994) |
| [17] | Kececioglu, J.; Sankoff, D., Exact and approximation algorithms for the inversion distance between two permutations, (Proc. of 4th Annual Symposium on Combinatorial Pattern Matching (CPM’93). Proc. of 4th Annual Symposium on Combinatorial Pattern Matching (CPM’93), Lecture Notes in Computer Science, vol. 684 (1993), Springer). (Proc. of 4th Annual Symposium on Combinatorial Pattern Matching (CPM’93). Proc. of 4th Annual Symposium on Combinatorial Pattern Matching (CPM’93), Lecture Notes in Computer Science, vol. 684 (1993), Springer), Algorithmica, 12, 180-210 (1995), Extended version has appeared in · Zbl 0831.92014 |
| [18] | Lin, G.; Jiang, T., A further improved approximation algorithm for breakpoint graph decomposition, Journal of Combinatorial Optimization, 8, 2, 183-194 (2004) · Zbl 1088.68182 |
| [19] | Lin, G.; Xue, G., Signed genome rearrangements by reversals and transpositions: Models and approximations, (Proc. of 5th Annual International Conference on Computing and Combinatorics (COCOON’99). Proc. of 5th Annual International Conference on Computing and Combinatorics (COCOON’99), Lecture Notes in Computer Science, vol. 1627 (1999), Springer), 71-80 · Zbl 0945.92007 |
| [20] | Palmer, J.; Herbon, L., Tricircular mitochondrial genomes of brassica and raphanus: Reversal of repeat configurations by inversion, Nucleic Acids Approach, 14, 9755-9764 (1986) |
| [21] | M. Walter, Z. Dias, J. Meidanis, Reversal and transposition distance of linear chromosomes, in: String Processing and Information Retrieval: A South American Symposium (SPIRE’98), 1998, pp. 96-102; M. Walter, Z. Dias, J. Meidanis, Reversal and transposition distance of linear chromosomes, in: String Processing and Information Retrieval: A South American Symposium (SPIRE’98), 1998, pp. 96-102 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
