Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (10): 46-48.

• 研究、探讨 • Previous Articles     Next Articles

Algorithms for sorting by short block-moves

XIAO Jinjie,XIE Qingsong,LIU Peiqiang,FAN Hui   

  1. School of Computer Science And Technology,Shandong Institute of Business and Technology,Yantai,Shandong 264005,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-04-01 Published:2011-04-01


肖进杰,谢青松,刘培强,范 辉   

  1. 山东工商学院 计算机科学与技术学院,山东 烟台 264005

Abstract: Sorting a permutation by short block-moves is a kind of technology for genome rearrangement.Sorting permutations with the fewest numbers of short block-move operations (i.e.minimum sorting) has became one of the most interesting problems in the area of computational biology.This paper first gives an optimal algorithm for short block-moves,then modifies the approximate algorithms,by testing data it shows that the two algorithms perform well in practice.

Key words: sort, short block-moves, computational biology, complexity

摘要: 用短块移动操作对一个排列进行排序是一种染色体基因重排技术。怎样才能找出使用短块移动次数最少的排序算法是计算生物学等领域最热门的研究问题之一。给出了短块移动的最优解算法,对近似算法进行了修改。实验验证了最优解算法和近似算法在实际运行过程中都有较好的表现。

关键词: 排序, 短块移动, 计算生物学, 复杂性