Exact and Approximation Algorithms for Sorting by Reversals, with Application to Genome Rearrangement
作者： J. Kececioglu , D. Sankoff
DOI: 10.1007/BF01188586
关键词: Permutation 、 Approximation algorithm 、 Series (mathematics) 、 Theory of computation 、 Substring 、 Sorting 、 Combinatorics 、 Edit distance 、 Chromosomal inversion 、 Mathematics
摘要: Motivated by the problem in computational biology of reconstructing series chromosome inversions which one organism evolved from another, we consider computing shortest reversals that transform permutation to another. The permutations describe order genes on corresponding chromosomes, and areversal takes an arbitrary substring elements, reverses their order.
springer.com
elsevier.com
sci-hub.se 参考文章(28)
John Kececioglu, David Sankoff, Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes combinatorial pattern matching. pp. 87- 105 ,(1993) , 10.1007/BFB0029799
Stephen J. O'Brien, Genetic Maps: Locus Maps of Complex Genomes ,(1990)
Theodosius Dobzhansky, Genetics of the Evolutionary Process ,(1970)
Heikki Mannila, Measures of Presortedness and Optimal Sorting Algorithms IEEE Transactions on Computers. ,vol. 34, pp. 318- 325 ,(1985) , 10.1109/TC.1985.5009382
William H. Gates, Christos H. Papadimitriou, Bounds for sorting by prefix reversal Discrete Mathematics. ,vol. 27, pp. 47- 57 ,(1979) , 10.1016/0012-365X(79)90068-2
J. H. Nadeau, B. A. Taylor, Lengths of chromosomal segments conserved since divergence of man and mouse. Proceedings of the National Academy of Sciences of the United States of America. ,vol. 81, pp. 814- 818 ,(1984) , 10.1073/PNAS.81.3.814
Robert A. Wagner, On the complexity of the Extended String-to-String Correction Problem Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75. pp. 218- 223 ,(1975) , 10.1145/800116.803771
Maureen J. Bibb, Richard A. Van Etten, Catharine T. Wright, Mark W. Walberg, David A. Clayton, Sequence and gene organization of mouse mitochondrial DNA Cell. ,vol. 26, pp. 167- 180 ,(1981) , 10.1016/0092-8674(81)90300-7
Michael Randolph Garey, Johnson: computers and intractability: a guide to the theory of np- completeness (freeman ,(1979)
Silvio Micali, Vijay V. Vazirani, An O(v|v| c |E|) algoithm for finding maximum matching in general graphs 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). pp. 17- 27 ,(1980) , 10.1109/SFCS.1980.12