Research Article: Finding local genome rearrangements

Date Published: May 4, 2018

Publisher: BioMed Central

Author(s): Pijus Simonaitis, Krister M. Swenson.

http://doi.org/10.1186/s13015-018-0127-2

Abstract

The double cut and join (DCJ) model of genome rearrangement is well studied due to its mathematical simplicity and power to account for the many events that transform gene order. 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 rearrangement scenarios that minimize the number of rearrangements whose breakpoints are unlikely due to some biological criteria. One such criterion has recently become accessible due to the advent of the Hi-C experiment, facilitating the study of 3D spacial distance between breakpoint regions.

We establish a link between the minimum number of unlikely rearrangements required by a scenario and the problem of finding a maximum edge-disjoint cycle packing on a certain transformed version of the adjacency graph. This link leads to a 3/2-approximation as well as an exact integer linear programming formulation for our problem, which we prove to be NP-complete. We also present experimental results on fruit flies, showing that Hi-C data is informative when used as a criterion for rearrangements.

A new variant of the weighted DCJ distance problem is addressed that ignores scenario length in its objective function. A solution to this problem provides a lower bound on the number of unlikely moves necessary when transforming one gene order into another. This lower bound aids in the study of rearrangement scenarios with respect to chromatin structure, and could eventually be used in the design of a fixed parameter algorithm with a more general objective function.

Partial Text

The problem of sorting genomes by a minimum number of biologically plausible rearrangements has been central to the theoretical comparative genomics community for roughly a quarter century. Traditionally, the likelihood of a rearrangement scenario has been based solely on the parsimony criterion. Unfortunately, a huge number of possible parsimonious scenarios between a pair of genomes exists [1–3]. This highlights the importance of methods that infer scenarios which conform to some extra biological constraints.

In this section we treat the minimum local scenario problem in the restricted case where only circular chromosomes are allowed. In this case adjacencies will be called pairs. Given sets of pairsdocumentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$begin{aligned} A&= big {{1,2},ldots ,{2n-1,2n}big },\ B&= big {{q_{1},q_{2}},ldots ,{q_{2n-1},q_{2n}}big }, end{aligned}$$end{document}A={{1,2},…,{2n-1,2n}},B={{q1,q2},…,{q2n-1,q2n}},with documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$${1,2,ldots ,2n}={q_{1},q_{2},ldots , q_{2n}}$$end{document}{1,2,…,2n}={q1,q2,…,q2n}, our goal is to transform A into B using DCJ moves of the form documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$${a,b},{c,d}rightarrow {a,c},{b,d}$$end{document}{a,b},{c,d}→{a,c},{b,d}.

Given two genomesdocumentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$begin{aligned} A&= big {{1,2},dots ,{2n-1,2n}, {2n+1}, ldots , {2n+2m}big },\ B&= big {{q_{1},q_{2}},dots ,{q_{2l-1},q_{2l}}, {q_{2l+1}}, ldots , {q_{2n+2m}}big }, end{aligned}$$end{document}A={{1,2},⋯,{2n-1,2n},{2n+1},…,{2n+2m}},B={{q1,q2},⋯,{q2l-1,q2l},{q2l+1},…,{q2n+2m}},with documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$${1,2,ldots ,2n+2m}={q_{1},q_{2},ldots , q_{2n+2m}}$$end{document}{1,2,…,2n+2m}={q1,q2,…,q2n+2m}, our goal is to transform A into B using DCJ moves defined in Definition 1.

Our work opens the door to the development of a more general model for genome rearrangements with positional constraints, where local moves are attributed nonzero cost. In such a model the costs of local and non-local moves would be respectively documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$omega _L$$end{document}ωL and documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$omega _N$$end{document}ωN with documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$0n$$end{document}ωLωN-ωL>n, where n is the number of adjacencies, is the minimum local parsimonious scenario problem,documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$(omega _L, omega _N)$$end{document}(ωL,ωN) with documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$0http://doi.org/10.1186/s13015-018-0127-2

 

Leave a Reply

Your email address will not be published.