Skip to Main content Skip to Navigation
Conference papers

Median clouds and a fast transposition median solver

Abstract : The median problem seeks a permutation whose total distance to a given set of permutations (the base set) is minimal. This is an important problem in comparative genomics and has been studied for several distance measures such as reversals. The transposition distance is less relevant biologically, but it has been shown that it behaves similarly to the most important biological distances, and can thus give important information on their properties. We have derived an algorithm which solves the transposition median problem, giving all transposition medians (the median cloud). We show that our algorithm can be modified to accept median clouds as elements in the base set and briefly discuss the new concept of median iterates (medians of medians) and limit medians, that is the limit of this iterate.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185431
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 11:09:28 AM
Last modification on : Thursday, June 18, 2020 - 10:18:03 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:02:24 AM

File

dmAK0131.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185431, version 1

Collections

Citation

Niklas Eriksen. Median clouds and a fast transposition median solver. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.373-384. ⟨hal-01185431⟩

Share

Metrics

Record views

109

Files downloads

750