A Practical Ezponential-time Algorithm on Sorting by Short Block-moves

摘要：

Sorting by short block-moves is one of the several approaches recently used for genome rearrangement, and most of the minimum sorting questions by these approaches have been proved to 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 gives an exponential-time algorithm of minimum sorting by short block-moves, and verifies its practicability by a set of test data.

关键词： sorting short block-moves computational biology ezponential-time algorithm complezity

作者: Qingsong Xie Jinjie Xiao Peiqiang Liu Haiyan Zhu Hui Fan Daming Zhu

作者单位: School of Computer Science and Technology Shandong Institute of Business and Technology Yantai,China College of Computer Science and Technology Shandong University Jinan,China

会议类型: 国际会议

会议名称: The 3rd International Conference on Bioinformatics and Biomedical Engineering(iCBBE 2009)(第三届生物信息与生物医学工程国际会议)

会议地点: 北京

会议语种:英文

页码: 1-4

在线出版日期: 2009-06-11（万方平台首次上网日期，不代表论文的发表时间）