A Practical Exponential-Time Algorithm on Sorting by Short Block-Moves

Author

Xie, Qingsong ; Xiao, Jinjie ; Liu, Peiqiang ; Zhu, Haiyan ; Fan, Hui ; Zhu, Daming

Author_Institution

Sch. of Comput. Sci. & Technol., Shandong Inst. of Bus. & Technol., Yantai, China

fYear

2009

fDate

11-13 June 2009

Firstpage

1

Lastpage

4

Abstract

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.

Keywords

biology computing; computational complexity; genetics; optimisation; sorting; NP-complete problem; NP-hard problem; PSPACE-complete problem; exponential-time algorithm; genome rearrangement; polynomial-time algorithms; short block-moves; sorting; Approximation algorithms; Bioinformatics; Computational biology; Computer science; Genomics; Microorganisms; Organisms; Polynomials; Sorting; Testing;

fLanguage

English

Publisher

ieee

Conference_Titel

Bioinformatics and Biomedical Engineering , 2009. ICBBE 2009. 3rd International Conference on

Conference_Location

Beijing

Print_ISBN

978-1-4244-2901-1

Electronic_ISBN

978-1-4244-2902-8

Type

conf

DOI

10.1109/ICBBE.2009.5162228

Filename

5162228