Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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


Publisher files allowed on an open archive




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, ⟨10.46298/dmtcs.2739⟩. ⟨hal-01185431⟩



Record views


Files downloads