Improved Bounds on Sorting with Length-Weighted Reversals

Michael A. Bender; Dongdong Ge; Simai He; Haodong Hu; Ron Y. Pinter; Steven Skiena; Firas Swidan

Improved Bounds on Sorting with Length-Weighted Reversals

Michael A. Bender
, Dongdong Ge
, Simai He
, Haodong Hu
, Ron Y. Pinter
, Steven Skiena
, Firas Swidan

Computer Science

Stony Brook University
Technion-Israel Institute of Technology

Research output: Contribution to conference › Paper › peer-review

15 Scopus citations

Abstract

We study the problem of sorting integer sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(l) = l^α for all α ≥ 0, where l is the length of the reversed subsequence. We present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given input. Furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. Our results have direct application in computational biology to the field of comparative genomics.

Original language	English
Pages	912-921
Number of pages	10
State	Published - 2004
Event	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: Jan 11 2004 → Jan 13 2004

Conference

Conference	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	New Orleans, LA.
Period	01/11/04 → 01/13/04

Cite this

@conference{b4e3abca28f24a319d3e3036285015c0,

title = "Improved Bounds on Sorting with Length-Weighted Reversals",

abstract = "We study the problem of sorting integer sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(l) = lα for all α ≥ 0, where l is the length of the reversed subsequence. We present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given input. Furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. Our results have direct application in computational biology to the field of comparative genomics.",

author = "Bender, \{Michael A.\} and Dongdong Ge and Simai He and Haodong Hu and Pinter, \{Ron Y.\} and Steven Skiena and Firas Swidan",

year = "2004",

language = "English",

pages = "912--921",

note = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 11-01-2004 Through 13-01-2004",

}

TY - CONF

T1 - Improved Bounds on Sorting with Length-Weighted Reversals

AU - Bender, Michael A.

AU - Ge, Dongdong

AU - He, Simai

AU - Hu, Haodong

AU - Pinter, Ron Y.

AU - Skiena, Steven

AU - Swidan, Firas

PY - 2004

Y1 - 2004

N2 - We study the problem of sorting integer sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(l) = lα for all α ≥ 0, where l is the length of the reversed subsequence. We present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given input. Furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. Our results have direct application in computational biology to the field of comparative genomics.

AB - We study the problem of sorting integer sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(l) = lα for all α ≥ 0, where l is the length of the reversed subsequence. We present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given input. Furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. Our results have direct application in computational biology to the field of comparative genomics.

UR - https://www.scopus.com/pages/publications/1842434544

M3 - Paper

AN - SCOPUS:1842434544

SP - 912

EP - 921

T2 - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 11 January 2004 through 13 January 2004

ER -

Improved Bounds on Sorting with Length-Weighted Reversals

Abstract

Conference

Other files and links

Fingerprint

Cite this