环型二元序列的赋权对换排序问题

• Articles • Previous Articles Next Articles

Sorting circular binary strings with length weighted transpositions

QI Xing-qin¹,CAO Jing²,ZHANG Chen³

1. Department of Mathematics, Shandong University at Weihai, Weihai264209;2. College of Science, Yanshan University, Qinhuangdao 066004;3. StateOwned Assets Supervision and Administration Faculty, Shandong Univerisity at Weihai

Received:1900-01-01 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: QI Xing-qin

Abstract

Abstract: The problem of sorting circular binary strings with length-weighted transpositions was considered, i.e. the cost of a transposition is f(l)=lα,0≤α<1, where l is the length of the transposition. An O(logn)approximation algorithm is given for sorting a circular binary string with the minimum cost, where n is the length of the circular string. The result has direct applications in computational biology in the field of comparative genomics.

Key words: approximation algorithm , transposition, circular binary string

CLC Number:

TP301

QI Xing-qin,CAO Jing,ZHANG Chen . Sorting circular binary strings with length weighted transpositions[J].J4, 2007, 42(12): 46-48 .

References

Related Articles 9

[1]	CAI Yu-hua, WEI Feng-ying*. Probabilistic approximation algorithm of metric spaces [J]. J4, 2013, 48(09): 51-55.
[2]	YANG Zhao-xia . A 2-approximation algorithm for an embedded hypergraph in a weighted cycle [J]. J4, 2008, 43(8): 11-13 .
[3]	YANG Zhen-guang,LI Shu-guang,and WANG Xiu-hong . Parallel-machine batch scheduling with non-identical job sizes [J]. J4, 2007, 42(4): 63-66 .
[4]	DAI Zhen-xiang,LI Shu-guang,and QI Xing-qin . Three-channel transmission scheduling in WDM star single-hop networks [J]. J4, 2007, 42(2): 46-50 .
[5]	LI Shu-guang,BAI Shu-yan,HE Zhi-hong,QI Kai-yuan . On the kcoloring of tintervals in a cycle [J]. J4, 2006, 41(6): 40-42 .
[6]	LI Shu-guang,YANG Zhen-guang,HE Zhi-hong . Maximizing profits in multifiber WDM chain and ring networks [J]. J4, 2006, 41(5): 7-11 .
[7]	WANG Ji-qiang . AResearch on approximation algorithm for a kind of median problem [J]. J4, 2006, 41(4): 1-03 .
[8]	LI Shu-guang,QI Xingqin,HE Zhi-hong . Call admission control in ring networks [J]. J4, 2006, 41(4): 15-19 .
[9]	QI Xing-qin,HE Zhi-hong and ZHAO Hong-luan . Sorting binary strings with length weighted transpositions [J]. J4, 2006, 41(1): 82-85 .

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!