Finding Local Genome Rearrangements

Krister Swenson 1 Pijus Simonaitis 2, 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The Double Cut and Join (DCJ) model of genome rearrangement is well studied due to its math- ematical simplicity and power to account for the many events that transform genome architec- ture. These studies have mostly been devoted to the understanding of minimum length scenarios transforming one genome into another. In this paper we search instead for DCJ rearrangement scenarios that minimize the number of rearrangements whose breakpoints are unlikely due to some biological criteria. We establish a link between this Minimum Local Scenario (MLS) problem and the problem of finding a Maximum Edge-disjoint Cycle Packing (MECP) on an undirected graph. This link leads us to a 3/2-approximation for MLS, as well as an exact integer linear program. From a practical perspective, we briefly report on the applicability of our methods and the potential for computation of distances using a more general DCJ cost function.
Type de document :
Communication dans un congrès
WABI: Workshop on Algorithms in Bioinformatics, Aug 2017, Boston, United States. 17th International Workshop on Algorithms in Bioinformatics, Leibniz International Proceedings in Informatics (LIPIcs) (88), pp.24:1--24:13, 2017, 〈10.4230/LIPIcs.WABI.2017.24〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01794757
Contributeur : Krister Swenson <>
Soumis le : jeudi 17 mai 2018 - 18:50:18
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : lundi 24 septembre 2018 - 23:41:14

Fichier

2017-SimonaitisFindingLocalWAB...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Krister Swenson, Pijus Simonaitis. Finding Local Genome Rearrangements. WABI: Workshop on Algorithms in Bioinformatics, Aug 2017, Boston, United States. 17th International Workshop on Algorithms in Bioinformatics, Leibniz International Proceedings in Informatics (LIPIcs) (88), pp.24:1--24:13, 2017, 〈10.4230/LIPIcs.WABI.2017.24〉. 〈lirmm-01794757〉

Partager

Métriques

Consultations de la notice

59

Téléchargements de fichiers

11