=====================================================

Here's the first problem of the semester, which Steve will be presenting:

=====================================================


        Sorting with Length-Weighted Reversals

The following problem arises in analyzing biological data to reconstruct
evolutionary history.  Reversal mutations occur often in chromosomes,
where each reverses the order of genes within a certain interval.  The
simplest series of reversals transforming one sequence to another
corresponds to a likely evolutionary path between them.

This motivates the problem of sorting with reversals, since we can reduce
each genome to a permutation on 1 to $n$, where $n$ is the number of
common genes between the species. Further by appropriately labeling the
genes, one of the permutations can be $1, 2, \ldots, n$.

Previous work has assumed that each reversal is of unit cost regardless of
the number of genes reversed.  By analogy to selection sort, one reversal
suffices to move an element to the front, so $O(n)$ reversals suffice for
any permutation.

But what if we pay $k$ units cost for reversal that reverses $k$ elements?
The selection sort algorithm might always employ long reversals, for a
total cost of $O(n^2)$.

The open problem(s):

(1) Give an algorithm which minimizes the maximum cost of sorting with
length-weighted reversals.

(2) Prove a non-trivial lower-bound on the worst-case cost of any such
algorithm.

(3) Give an algorithm for approximating the reversal cost of any input
permutation, so simple permutations are sorted cheaply instead of just
being efficient in the worst case.

I have some preliminary results with Ron Pinter (Technion), but our bounds
are much weaker than they should be.




From jsbm@ams.sunysb.edu Mon Sep  9 10:04:53 2002
Date: Mon, 9 Sep 2002 10:05:32 -0400 (EDT)
From: jsbm@ams.sunysb.edu
Subject: Re: reversy problem
To: bender@cs.sunysb.edu
cc: dge@cs.sunysb.edu, simai_he@yahoo.com, skiena@cs.sunysb.edu,
   estie@ams.sunysb.edu, jsbm <jsbm@ams.sunysb.edu>
MIME-Version: 1.0
X-Status: 
X-Keywords:                 

On  9 Sep, Michael Bender wrote:
> 
> 
> CONGRATULATIONS!!! This is great news...I'm eager for more details.

Very nice!

I too was thinking about the problem some, but concentrating
on the upper bound, since I was pretty sure the N log N would
got through on the lower bound.  I am glad to hear that you guys 
"nailed" it ;-))

Joe

> 
> 
> On Sun, 8 Sep 2002, Ge DongDong wrote:
> 
>> Hi,Michael:
>> Today simai and I discussed about this question for one day.Simai proposed
>> some idea which proves the lower bound is O(NlogN).And we checked it
>> carefully and we think it is correst.I'm writing it formally with all
>> details.we are waiting for your order for next step.:)Do we need to talk
>> someone else?
>> happy trip!
>> Dongdong
>>
>> By the way,in that repeat scheduling problem,is each job is preemptive?
>>
>>
>>
> 


From skiena@cs.sunysb.edu Mon Sep  9 10:11:07 2002
Date: Mon, 9 Sep 2002 10:09:11 -0400 (EDT)
From: skiena@cs.sunysb.edu (Steve Skiena)
To: bender@cs.sunysb.edu, dge@cs.sunysb.edu, simai_he@yahoo.com
Subject: Re: reversy problem
Cc: estie@ams.sunysb.edu, jsbm@ams.sunysb.edu, skiena@cs.sunysb.edu
X-Status: 
X-Keywords:                 

Good job...  If you have a writeup, send it around -- either way,
expect to explain it to reading group on Friday.

I am less optimistic than Joe is (as usual) that the diameter is
in fact O(n log n); if your lower bound follows the same general
lines proposed in the last reading group note that it applies
to a weaker problem (0/1 separation from honest sorting).
Maybe you can push your analysis up to n log^2 n with more work?

Steve