A General Framework for Genome Rearrangement with Biological Constraints

Pijus Simonaitis 1 Annie Chateau 2 Krister Swenson 2
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper generalizes previous studies on genome rearrangement under biological constraints, using double cut and join (DCJ). We propose a model for weighted DCJ, along with a family of optimization problems called ϕ-MCPS (MiniMuM CoSt ParSiMoniouS SCenario), that are based on labeled graphs. We show how to compute solutions to general instances of ϕ-MCPS, given an algorithm to compute ϕ-MCPS on a circular genome with exactly one occurrence of each gene. These general instances can have an arbitrary number of circular and linear chromosomes, and arbitrary gene content. The practicality of the framework is displayed by presenting polynomial-time algorithms that generalize the results of Bulteau, Fertin, and Tannier on the Sorting by wDCJS anD inDelS in intergeneS problem, and that generalize previous results on the MiniMuM loCal ParSiMoniouS SCenario problem.
Document type :
Conference papers
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02067487
Contributor : Annie Chateau <>
Submitted on : Tuesday, September 17, 2019 - 4:12:21 PM
Last modification on : Wednesday, September 18, 2019 - 10:46:19 AM

File

10.1186_s13015-019-0149-4.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License

Identifiers

Collections

Citation

Pijus Simonaitis, Annie Chateau, Krister Swenson. A General Framework for Genome Rearrangement with Biological Constraints. RECOMB-CG: Comparative Genomics, Oct 2018, Magog-Orford, QC, Canada. pp.49-71, ⟨10.1007/978-3-030-00834-5_3⟩. ⟨lirmm-02067487⟩

Share

Metrics

Record views

105

Files downloads

68