2018/02/21 by Pijus Simonaitis, Simonaitis, Pijus, Annie Château +3 · 1 citation
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · #Chromosomal and Genetic Variations #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #FOS: Mathematics #Genome Rearrangement Algorithms #Genomics (q-bio.GN) #Genomics and Phylogenetic Studies
paper · pdf · doi:10.48550/arxiv.1802.07515
openalex publication_date 2018/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The study of genome rearrangement has many flavours, but they all are somehow tied to edit distances on variations of a multi-graph called the breakpoint graph. We study a weighted 2-break distance on Eulerian 2-edge-colored multi-graphs, which generalizes weighted versions of several Double Cut and Join problems, including those on genomes with unequal gene content. We affirm the connection between cycle decompositions and edit scenarios first discovered with the Sorting By Reversals problem. Using this we show that the problem of finding a parsimonious scenario of minimum cost on an Eulerian 2-edge-colored multi-graph - with a general cost function for 2-breaks - can be solved by decomposing the problem into independent instances on simple alternating cycles. For breakpoint graphs, and a more constrained cost function, based on coloring the vertices, we give a polynomial-time algorithm for finding a parsimonious 2-break scenario of minimum cost, while showing that finding a non-parsimonious 2-break scenario of minimum cost is NP-Hard.