Improved bounds on sorting by length-weighted reversals

被引：15

作者：

Bender, Michael A. ^{[2
]}

Ge, Dongdong ^{[3
]}

He, Simai ^{[4
]}

Hu, Haodong ^{[2
]}

Pinter, Ron Y. ^{[1
]}

Skiena, Steven ^{[2
]}

Swidan, Firas ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

[2] SUNY Stony Brook, Dept Comp Sci, Stony Brook, NY 11794 USA

[3] Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 USA

[4] Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Hong Kong, Hong Kong, Peoples R China

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2008年 / 74卷 / 05期

基金：

美国国家科学基金会;

关键词：

sorting by reversals; potential functions; dynamic programming; soiling 0/1 sequences by reversals; modeling genome rearrangements;

D O I：

10.1016/j.jcss.2007.08.008

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(l) = l(alpha) for all alpha >= 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. (c) 2007 Elsevier Inc. All rights reserved.

引用

页码：744 / 774

页数：31

共 21 条

[1]

Ajana Y, 2002, LECT NOTES COMPUT SC, V2452, P300

[2]

[Anonymous], 1973, SORTING SEARCHING

[3] Genome rearrangements and sorting by reversals [J].

Bafna, V ;

Pevzner, PA .

SIAM JOURNAL ON COMPUTING, 1996, 25 (02) :272-289

[4]

BAFNA V, 1994, MOL BIOL EVOL

[5]

BERGERON A, 2001, LECT NOTES COMPUTER, V2089, P106

[6]

Berman P, 2002, LECT NOTES COMPUT SC, V2461, P200

[7]

Blanchette M, 1996, GENE, V172, pGC11, DOI 10.1016/0378-1119(95)00878-0

[8]

Caprara A., 1997, P 1 ANN INT C COMP M, P75, DOI DOI 10.1145/267521.267531

[9]

DAVISSON M T, 1987, Genomics, V1, P213, DOI 10.1016/0888-7543(87)90047-4

[10]

Dobzhansky T, 1938, GENETICS, V23, P28

← 1 2 3 →