Finding Local Genome Rearrangements - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Finding Local Genome Rearrangements

Résumé

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.
Fichier principal
Vignette du fichier
2017-SimonaitisFindingLocalWABI.pdf (1.15 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01794757 , version 1 (17-05-2018)

Licence

Paternité

Identifiants

Citer

Pijus Simonaitis, Krister M. Swenson. Finding Local Genome Rearrangements. 17th International Workshop on Algorithms in Bioinformatics (WABI 2017), Aug 2017, Boston, United States. pp.24:1--24:13, ⟨10.4230/LIPIcs.WABI.2017.24⟩. ⟨lirmm-01794757⟩
92 Consultations
114 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More