On Sorting of Signed Permutations by Prefix and Suffix Reversals and Transpositions

被引：0

作者：

Lintzmayer, Carla Negri ^{[1
]}

Dias, Zanoni ^{[1
]}

机构：

[1] Univ Estadual Campinas, UNICAMP, Inst Comp, Campinas, SP, Brazil

来源：

ALGORITHMS FOR COMPUTATIONAL BIOLOGY | 2014年 / 8542卷

关键词：

sorting signed permutations; reversals; transpositions; prefix operations; suffix operations; ALGORITHM;

D O I：

暂无

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

A reversal inverts a segment and the signs of the elements of this segment in a permutation. A transposition exchanges the position of two consecutive segments. These are the most common kinds of genome rearrangements. In this paper, we introduce the study of prefix and suffix versions of these operations, that is, when only segments of the beginning or of the end are involved, when considering signed permutations. We gave asymptotic approximation algorithms of factor two for three new problems: when prefix and suffix reversals are allowed, when prefix reversals and prefix transpositions are allowed, and when prefix and suffix reversals and prefix and suffix transpositions are allowed.

引用

页码：146 / 157

页数：12

共 14 条

[1] On average and highest number of flips in pancake sorting [J].

Cibulka, Josef .

THEORETICAL COMPUTER SCIENCE, 2011, 412 (8-10) :822-834

[2] ON THE PROBLEM OF SORTING BURNT PANCAKES [J].

COHEN, DS ;

BLUM, M .

DISCRETE APPLIED MATHEMATICS, 1995, 61 (02) :105-120

[3]

Fertin Guillaume, 2009, Combinatorics of Genome Rearrangements. Computational Molecular Biology

[4]

Galvao G.R., 2012, THESIS U CAMPINAS CA

[5] BOUNDS FOR SORTING BY PREFIX REVERSAL [J].

GATES, WH ;

PAPADIMITRIOU, CH .

DISCRETE MATHEMATICS, 1979, 27 (01) :47-57

[6] A 2-approximation algorithm for genome rearrangements by reversals and transpositions [J].

Gu, QP ;

Peng, ST ;

Sudborough, H .

THEORETICAL COMPUTER SCIENCE, 1999, 210 (02) :327-339

[7] Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals [J].

Hannenhalli, S ;

Pevzner, PA .

JOURNAL OF THE ACM, 1999, 46 (01) :1-27

[8] A 1.5-approximation algorithm for sorting by transpositions and transreversals [J].

Hartman, T ;

Sharan, R .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2005, 70 (03) :300-320

[9] On the diameter of the pancake network [J].

Heydari, MH ;

Sudborough, IH .

JOURNAL OF ALGORITHMS, 1997, 25 (01) :67-94

[10] Signed genome rearrangement by reversals and transpositions: models and approximations [J].

Lin, GH ;

Xue, GL .

THEORETICAL COMPUTER SCIENCE, 2001, 259 (1-2) :513-531

← 1 2 →