Formulations and hardness of multiple sorting by reversals
- 1 April 1999
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
We consider two generalizations of signed Sorting By Reversals (SBR), both aimed atformalizing the problem of reconstructing the evolutionary history of a set of species. Inparticular, we address Multiple SBR, calling for a signed permutation at minimum reversaldistance from a given set of signed permutations, and Tree SBR, calling for a tree with theminimum number of edges spanning a given set of nodes in the complete graph where eachnode corresponds to a signed permutation and there is...Keywords
This publication has 7 references indexed in Scilit:
- Multiple genome rearrangementsPublished by Association for Computing Machinery (ACM) ,1998
- Algorithms on Strings, Trees and SequencesPublished by Cambridge University Press (CUP) ,1997
- Genome Rearrangements and Sorting by ReversalsSIAM Journal on Computing, 1996
- STEINER POINTS IN THE SPACE OF GENOME REARRANGEMENTSInternational Journal of Foundations of Computer Science, 1996
- Exact and approximation algorithms for sorting by reversals, with application to genome rearrangementAlgorithmica, 1995
- Transforming cabbage into turnipPublished by Association for Computing Machinery (ACM) ,1995
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981