Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430764 | Journal of Computer and System Sciences | 2008 | 31 Pages |
Abstract
We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(ℓ)=ℓα for all α⩾0, where ℓ 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics