A 2-approximation algorithm for genome rearrangements by reversals and transpositions. (English) Zbl 0915.68033
Summary: Recently, a new approach to analyze genomes evolving which is based on comparison of gene orders versus traditional comparison of DNA sequences was proposed [D. Sankoff, G. Leduc, N. Antoine, B. Paquin, B. F. Lang and R. Cedergren, Gene order comparison for phylogenetic inference: evolution of the mitochondrial genome, in: Proc. Natl. Acad. Sci. USA 89, 6575-6579 (1992)]. The approach is based on the global rearrangements (e.g., inversions and transpositions of fragments). Analysis of genomes evolving by inversions and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, i.e., sorting of a permutation using reversals and transpositions of arbitrary fragments. We study sorting of signed permutations by reversals and transpositions, a problem which adequately models genome rearrangements, as the genes in DNA are oriented. We establish a lower bound and give a 2-approximation algorithm for the problem.
MSC:
| 68P10 | Searching and sorting |
| 68W10 | Parallel algorithms in computer science |
| 68U99 | Computing methodologies and applications |
Keywords:
sorting of permutations; genome rearrangements; sequence comparison; computational molecular biology; lower bound; approximation algorithmsReferences:
| [1] | Bafna, V.; Pevzner, P., Sorting by reversals: genome rearrangements in plant organelles and evolutionary history of x chromosome, Mol. Biol. Evol., 12, 239-246 (1995) |
| [2] | Bafna, V.; Pevzner, P., Sorting permutations by transpositions, (Proc. 6th ACM-SIAM Ann. Symp. on Discrete Algorithms (1995)), 614-623 · Zbl 0846.92007 |
| [3] | Bafna, V.; Pevzner, P., Genome rearrangements and sorting by reversals, SIAM J. Comput., 25, 2, 272-289 (1996) · Zbl 0844.68123 |
| [4] | Caprara, A., Sorting by reversals in difficulty, (Proc. 1st Ann. Internat. Conf. Comput. Mol. Biol. (1997)), 75-83 |
| [5] | Franklin, N., Conservation of genome form but not sequence in the transcription antitermination determinants of bacteriophages λ, φ21, and p22, J. Mol. Evol., 181, 75-94 (1985) |
| [6] | Hannenhalli, S.; Pevzner, P., Transforming cabbage into turnip (polynomial algorithm for sorting signed permutation by reversals), (Proc. 27th ACM Symp. on Theory of Computing (STOC’95) (1995)), 178-189 · Zbl 0978.68530 |
| [7] | Karlin, S.; Mocarski, E. S.; Schachtel, G. A., Molecular evolution of herpesviruses: genomic and protein sequence comparisions, J. Virol., 68, 1886-1902 (1994) |
| [8] | Kececioglu, J.; Sankoff, D., Algorithmica, 13, 180-210 (1995), Extended version has appeared in · Zbl 0831.92014 |
| [9] | McGeoch, D. J., Molecular evolution of large DNA viruses of eukaryotes, Sem. Virol., 3, 399-408 (1992) |
| [10] | Palmer, J. D.; Herbon, L. A., Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence, J. Mol. Evol., 27, 87-97 (1988) |
| [11] | Sankoff, D.; Leduc, G.; Antoine, N.; Paquin, B.; Lang, B. F.; Cedergren, R., Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome, (Proc. Natl. Acad. Sci. USA, 89 (1992)), 6575-6579 |
| [12] | H. Sudborough, Permutations, pancakes, and phylogeny, Manuscript.; H. Sudborough, Permutations, pancakes, and phylogeny, Manuscript. |
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.
