摘要: The breakpoint median problems arise in the problem of determining phylogenetic history from comparative genome data. We prove that problems, and a number related constrained versions, are all NP-hard.
umontreal.ca 
otago.ac.nz 参考文章(14)
Itsik Pe'er, Ron Shamir, The median problems for breakpoints are NP-complete Electronic Colloquium on Computational Complexity. ,vol. 5, ,(1998)
David Sankoff, Edit Distances for Genome Comparisons Based on Non-Local Operations combinatorial pattern matching. pp. 121- 135 ,(1992) , 10.1007/3-540-56024-6_10
Richard M. Karp, Reducibility Among Combinatorial Problems Journal of Symbolic Logic. ,vol. 40, pp. 219- 241 ,(2010) , 10.1007/978-3-540-68279-0_8
Mathieu Blanchette, Takashi Kunisawa, David Sankoff, PARAMETRIC GENOME REARRANGEMENT Gene. ,vol. 172, ,(1996) , 10.1016/0378-1119(95)00878-0
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Mathieu Blanchette, Takashi Kunisawa, David Sankoff, Gene order breakpoint evidence in animal mitochondrial phylogeny. Journal of Molecular Evolution. ,vol. 49, pp. 193- 203 ,(1999) , 10.1007/PL00006542
David Sankoff, Mathieu Blanchette, Multiple genome rearrangements research in computational molecular biology. pp. 243- 247 ,(1998) , 10.1145/279069.279122
D. Sankoff, G. Leduc, N. Antoine, B. Paquin, B. F. Lang, R. Cedergren, Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome. Proceedings of the National Academy of Sciences of the United States of America. ,vol. 89, pp. 6575- 6579 ,(1992) , 10.1073/PNAS.89.14.6575
Alberto Caprara, Sorting by reversals is difficult research in computational molecular biology. pp. 75- 83 ,(1997) , 10.1145/267521.267531
Sridhar Hannenhalli, Pavel Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals symposium on the theory of computing. pp. 178- 189 ,(1995) , 10.1145/225058.225112