Title: Sorting by transpositions: dealing with length-weighted models

Authors: Xingqin Qi, Jichang Wu, Shuguang Li, Guojun Li

Addresses: Department of Applied Mathematics, Shandong University at Weihai, Weihai 264209, China. ' School of Mathematics and System Sciences, Shandong University, Jinan 250100, China. ' School of Information and Electronics Engineering, Shandong Institute of Business and Technology, Yantai 264005, China. ' School of Mathematics and System Sciences, Shandong University, Jinan 250100, China; Department of Biochemistry and Molecular Biology, University of Georgia, Athens, Georgia 30602, USA

Abstract: For the first time, we study the sorting of permutations by length-weighted transpositions under a wide class of cost functions, namely f(l)=lα, where l is the length of the transposition. For different α, we give corresponding upper and lower bounds of the cost of sorting any binary sequences or any permutations. Furthermore, an O(log n) approximation algorithm and an exact algorithm are given to determine the optimal transposition series of sorting a permutation of length n when 1 < α < 2 and α ≥ 2 respectively. Our work poses some interesting questions to both biologists and computer scientists and suggests some new bioinformatic insights that are currently being studied.

Keywords: transposition sorting; length weighted models; algorithms; bioinformatics; evolutionary distance; genomic data; sequences; evolutionary events.

DOI: 10.1504/IJBRA.2008.018343

International Journal of Bioinformatics Research and Applications, 2008 Vol.4 No.2, pp.164 - 171

Published online: 17 May 2008 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article