@techreport{TR-IC-14-12,
   number = {IC-14-1208-45},
   author = {Cleber {Mira} and João {Meidanis}},
   title  =  {{Sorting  by  Fissions, Fusions, and Signed Reversals in
                   $O(n)$}},
   month = {August},
   year = {2014},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 20 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       Measuring  the  minimum  number  of  rearrangement  events that
       transforms  a  genome into another is an important tool for the
       comparative analysis of genomes. We propose a new algorithm for
       finding  a  minimum  sequence  of Fissions, Fusions, and Signed
       Reversals  that transforms a genome into another. The algorithm
       is  based  on  representing a chromosome as a cycle (a circular
       sequence)  instead  of a mapping. Thus a genome is a product of
       cycles  instead  of  the  usual  representation  as  a  set  of 
       mappings.   By   representing   a   chromosome   as   a  cycle, 
       rearrangement   events   like  fissions,  fusions,  and  signed 
       reversals  are  performed in constant running time. Besides the
       change  in  the representation, the algorithm uses a hash table
       to  deal  with the problem of using the gene names for indexes.
       The  total  time complexity is $O(nh)$, where $n$ is the number
       of  genes and $h$ is the time spent to retrieve data for a gene
       in  the hash table (ideally $h$ is a constant). We also present
       a  formula  for  the  minimum  number of Fissions, Fusions, and
       Signed  Reversals  that  can  be  calculated in $O(nh)$ running
       time.
  }
}