We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 25 Issue 4
July  2010
Turn off MathJax
Article Contents
Abstract
References
Xiao-Wen Lou, Da-Ming Zhu. Sorting Unsigned Permutations by Weighted Reversals, Transpositions, and Transreversals[J]. Journal of Computer Science and Technology, 2010, 25(4): 853-863. DOI: 10.1007/s11390-010-1066-7
Citation: Xiao-Wen Lou, Da-Ming Zhu. Sorting Unsigned Permutations by Weighted Reversals, Transpositions, and Transreversals[J]. Journal of Computer Science and Technology, 2010, 25(4): 853-863. DOI: 10.1007/s11390-010-1066-7
shu

Sorting Unsigned Permutations by Weighted Reversals, Transpositions, and Transreversals

  • School of Computer Science and Technology, Shandong University, Jinan 250101, China

Funds: 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.
More Information
  • Author Bio:

    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.

  • Received Date: January 06, 2009
  • Revised Date: February 28, 2010
  • Published Date: July 08, 2010
    Abstract
  • 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.
    • FullText(HTML)
    • References (24)
  • [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.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (34) PDF downloads (1639) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return