【作者】 谢青松； 刘培强； 朱大铭；

【机构】 山东工商学院信息与电子工程学院； 山东大学计算机科学与技术学院；

【摘要】 <正>1 引言近几年,如何用最少的操作将一个染色体的基因排列排序,在计算生物领域引起了极大的关注。另外,某些基因重排算法对于构建对称互连网络也很有帮助。更多还原

【Abstract】 Sorting a permutation by short block-moves is a new kind of technology for genome rearrangement, and can be applied in the study of genome rearrangements and in the design of interconnection networks. Sorting permutations with the fewest numbers of short block-move operations has become one of the most interesting problems in the area of computational biology. In fact,sorting by shortblock-moves is just one of the several approaches recently used for genome rearrangement,and most of the minimum sorting questions by these approaches have been provedto be NP-complete or NP-hard or even PSPACE-complete. Nevertheless, the complexity of minimum sorting by block-moves remains unsolved,and approximation algorithms for it and polynomial-time algorithms on special permutations for it are continuously devised. This paper introduces some recent reseach results on this respect更多还原