## Abstract

Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the proble m of computing the shortest series of reversals that transform one permutation to another, The permutations describe the order of genes on corresponding chromosomes, and a reversal takes an arbitrary substring of elements and reverses their order. For this problem we develop two algorithms: a greedy approximation algorithm that finds a solution provably close to optimal in O(n ^{2}) time and O(n) space for an n element permutation, and a branch and bound exact algorithm that finds an optimal solution in O(mL(n, n)) time and O(n ^{2}) space, where m is the size of the branch and bound search tree and L(n, n) is the time to solve a linear program of n variables and n constraints. The greedy algorithm is the first to come within a constant factor of the optimum, and guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch and bound algorithm are a novel application of maximum weight matehings, shortest paths, and linear programming. In a series of experiments we study the performance of an implementation. For random permutations we find that the average difference between the upper and lower bounds is less than 3 reversals for n ≤ 50. Due to the tightness of these bounds we can solve to optimality random permutations on 30 elements in a few minutes of computer time.

Original language | English (US) |
---|---|

Title of host publication | Combinatorial Pattern Matching - 4th Annual Symposium, CPM 1993, Proceedings |

Editors | Alberto Apostolico, Alberto Apostolico, Maxime Crochemore , Zvi Galil, Zvi Galil, Udi Manber |

Publisher | Springer-Verlag |

Pages | 87-105 |

Number of pages | 19 |

ISBN (Print) | 9783540567646 |

DOIs | |

State | Published - 1993 |

Event | Conference of the European Society for Fuzzy Logic and Technology, EUSFLAT 2017 and 16th International Workshop on Intuitionistic Fuzzy Sets and Generalized Nets, IWIFSGN 2017 - Warsaw, Poland Duration: Sep 11 2017 → Sep 15 2017 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 684 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | Conference of the European Society for Fuzzy Logic and Technology, EUSFLAT 2017 and 16th International Workshop on Intuitionistic Fuzzy Sets and Generalized Nets, IWIFSGN 2017 |
---|---|

Country/Territory | Poland |

City | Warsaw |

Period | 9/11/17 → 9/15/17 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)