Median clouds and a fast transposition median solver

Résumé : Le problème de la médiane est de trouver une permutation dont la distance totale à un ensemble donné de permutations (l´ensemble de base) est minimale. C'est un problème important en génomique comparative et il a été étudié pour certaines mesures de distance. La distance de transposition n'est pas directement liée à  la biologie, mais il a été démontré que son comportement est similaire à celui des distances biologiques essentielles, et elle peut donc donner des indications sur leurs propriétés. Nous construisons un algorithme qui résout le problème de la médiane pour la transposition, et donne toutes les transpositions médianes (le nuage des médianes). Nous démontrons que notre algorithme peut être modifié pour admettre des nuages de médianes comme éléments de l´ensemble de base et introduisons le concept de médianes itérées (médianes de médianes) et de médianes limites, c-à-d de limites de ces itérations.
Type de document :
Communication dans un congrès
Krattenthaler, Christian and Strehl, Volker and Kauers, Manuel. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), pp.373-384, 2009, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185431
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 11:09:28
Dernière modification le : mardi 7 mars 2017 - 15:04:18
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:02:24

Fichier

dmAK0131.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185431, version 1

Collections

Citation

Niklas Eriksen. Median clouds and a fast transposition median solver. Krattenthaler, Christian and Strehl, Volker and Kauers, Manuel. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), pp.373-384, 2009, DMTCS Proceedings. 〈hal-01185431〉

Partager

Métriques

Consultations de la notice

44

Téléchargements de fichiers

121