›› 2010, Vol. 25 ›› Issue (4): 853-863.doi: 10.1007/s11390-010-1066-7

• Algorithm and Complexity • Previous Articles     Next Articles

Sorting Unsigned Permutations by Weighted Reversals, Transpositions, and Transreversals

Xiao-Wen Lou(娄晓文) and Da-Ming Zhu*(朱大铭), Senior Member, CCF   

  1. School of Computer Science and Technology, Shandong University, Jinan 250101, China
  • Received:2009-01-07 Revised:2010-03-01 Online:2010-07-09 Published:2010-07-09
  • About author:
    Xiao-Wen Lou received her B.S. degree in 2004 from School of Computer Science and Technology, Shandong University, where she is currently a Ph.D. candidate. Her research interests include algorithm design and analysis and computational biology.
    Da-Ming Zhu received his B.S. degree from University of Science and Technology of China in 1987 and his Ph.D. degree from Institute of Computing Technology, Chinese Academy of Sciences in 1999, both in computer science. He is currently a professor and Ph.D. supervisor in School of Computer Science and Technology, Shandong University, and senior member of China Computer Federation. His main research interests include algorithm design and analysis, computational biology and neural network.
  • Supported by:

    Supported by the National Natural Science Foundation of China under Grant No. 60970003, the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20090131110009, the Key Science-Technology Project of Shandong Province of China under Grant No. 2006GG2201005.

Reversals, transpositions and transreversals are common events in genome rearrangement. The genome rearrangement sorting problem is to transform one genome into another using the minimum number of given rearrangement operations. An integer permutation is used to represent a genome in many cases. It can be divided into disjoint strips with each strip denoting a block of consecutive integers. A singleton is a strip of one integer. And the genome rearrangement problem turns into the problem of sorting a permutation into the identity permutation equivalently. Hannenhalli and Pevzner designed a polynomial time algorithm for the unsigned reversal sorting problem on those permutations with O(log n) singletons. In this paper, first we describe one case in which Hannenhalli and Pevzner's algorithm may fail and propose a corrected approach. In addition, we propose a (1+ ε)-approximation algorithm for sorting unsigned permutations with O(\og n) singletons by reversals of weight 1 and transpositions/transreversals of weight 2.


[1] Jiang T. Some algorithmic challenges in genome-wide ortholog assignment. Journal of Computer Science and Technology, 2010, 25(1): 42-52.

[2] Caprara A. Sorting by reversals is difficult. In Proc. the 1st International Conference on Research in Computational Molecular Biology, Santa Fe, USA, Jan. 20-23, 1997, pp.75-83.

[3] Bafna V, Pevzner P. Genome rearrangements and sorting by reversals. SIAM J. Computing, 1996, 25(2): 272-289.

[4] Christie D. Genome rearrangement problems
[Ph.D. Dissertation]. University of Glasgow, 1998.

[5] Berman P, Hannenhalli S, Karpinski M. 1.375-approximation algorithm for sorting by reversals. In Proc. the 10th Annual European Symposium on Algorithms, Rome, Italy, Sept. 16-21, 2002, pp.200-210.

[6] Hannenhalli S, Pevzner P. Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). Journal of ACM, 1999, 46(1): 1-27.

[7] Kaplan H, Shamir R, Tarjan R. A faster and simpler algorithm for sorting signed permutations by reversals. SIAM J. Computing, 1999, 29(3): 880-892.

[8] Tannier E, Sagot M-F. Sorting by reversals in subquadratic time. In Proc. the 15th Annual Symposium on Combinatorial Pattern Matching, .Istanbul, Turkey, Jul. 5-7, 2004, pp.1-13.

[9] Bergeron A. A very elementary presentation of the Hannenhalli-Pevzner theory. Discrete Applied Mathematics, 2005, 146(2): 134-145.

[10] Swenson K, Rajan V, Lin Y, Moret B. Sorting signed permutations by inversions in O (n log n) time. In Proc. the 13th International Conference on Research in Computational Molecular Biology, Tucson, USA, May 18-21, 2009, pp.386-399.

[11] Hannenhalli S, Pevzner P. To cut ... or not to cut (applications of comparative physical maps in molecular evolution). In Proc. the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, USA, Jan. 28-30, 1996, pp.304-313.

[12] Bafna V, Pevzner P. Sorting by transpositions. SIAM Journal on Discrete Mathematics, 1998, 11(2): 224-240.

[13] Hartman T, Shamir R. A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Information and Computation, 2006, 204(2): 275-290.

[14] Feng J, Zhu D. Faster algorithm for sorting by transpositions and sorting by block-interchanges. ACM Transactions on Algorithms, 2007, 3(3): Article No.25.

[15] Elias I, Hartman T. A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2006, 3(4): 369-379.

[16] Walter M, Dias Z, Meidanis J. Reversal and transposition distance of linear chromosomes. In Proc. String Processing and Information Retrieval, Santa Cruz de La Sierra, Bolivia, Sept. 9-11, 1998, pp.96-102.

[17] Gu Q, Peng S, Sudborough H. A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theoretical Computer Science, 1999, 210(2): 327-339.

[18] Lin G, Xue G. Signed genome rearrangement by reversals and transpositions: Models and approximations. Theoretical Computer Science, 2001, 259(1/2): 513-531.

[19] Hartman T, Sharan R. A 1.5-approximation algorithm for sorting by transpositions and transreversals. Journal of Computer and System Sciences, 2005, 70(3): 300-320.

[20] Rahman A, Shatabda S, Hasan M. An approximation algorithm for sorting by reversals and transpositions. Journal of Discrete Algorithms, 2008, 6(3): 449-457.

[21] Lou X, Zhu D. A 2.25-approximation algorithm for cut-and-paste sorting of unsigned circular permutations. In Proc. the 14th Annual International Computing and Combinatorics Conference, Dalian, China, Jun. 27-29, 2008, pp.331-341.

[22] Eriksen N. (1+ε)-approximation of sorting by reversals and transpositions. Theoretical Computer Science, 2002, 289(1): 517-529.

[23] Bader M, Ohlebusch E. Sorting by weighted reversals, transpositions, and inverted transpositions. Journal of Computational Biology, 2007, 14(5): 615-636.

[24] Bader D, Moret B, Yan M. A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. Journal of Computational Biology, 2001, 8(5): 483-491.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved