id: 06104112
dt: a
an: 06104112
au: Cunha, Luís Felipe I.; Kowada, Luis Antonio B.; de A.Hausen, Rodrigo; de
    Figueiredo, Celina M.H.
ti: Transposition diameter and lonely permutations.
so: de Souto, Marcilio C. (ed.) et al., Advances in bioinformatics and
    computational biology. 7th Brazilian symposium on bioinformatics, BSB
    2012, Campo Grande, Brazil, August 15‒17, 2012. Proceedings. Berlin:
    Springer (ISBN 978-3-642-31926-6/pbk). Lecture Notes in Computer
    Science 7409. Lecture Notes in Bioinformatics, 1-12 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: comparative genomics; genome rearrangement; transposition diameter; lonely
    permutations; knot permutations
ci: 
li: doi:10.1007/978-3-642-31927-3_1
ab: Summary: Determining the transposition distance of permutations was proven
    recently to be NP-hard. However, the problem of the transposition
    diameter is still open. The known lower bounds for the diameter were
    given by Meidanis, Walter and Dias when the lengths of the permutations
    are even and by Elias and Hartman when the lengths are odd. A better
    lower bound for the transposition diameter was proposed using the new
    definition of super-bad permutations, that would be a particular family
    of the lonely permutations. We show that there are no super-bad
    permutations, by computing the exact transposition distance of the
    union of two copies of particular lonely permutations that we call knot
    permutations. Meidanis, Walter, Dias, Elias and Hartman, therefore,
    still hold the current best lower bound. Moreover, we consider the
    union of distinct lonely permutations and manage to define an
    alternative family of permutations that meets the current lower bound.
rv: