Paper Info
Title
Models and Algorithms for Genome Rearrangement with Positional Constraints
Abstract
Background: Traditionally, the merit of a rearrangement scenario between two gene orders has been measured based on a parsimony criteria alone; two scenarios with the same number of rearrangements are considered equally good. In this paper, we acknowledge that each rearrangement has a certain likelihood of occurring based on biological constraints, e.g. physical proximity of the DNA segments implicated or repetitive sequences. Results: We propose optimization problems with the objective of maximizing overall likelihood, by weighting the rearrangements. We study a binary weight function suitable to the representation of sets of genome positions that are most likely to have swapped adjacencies. We give a polynomial-time algorithm for the problem of finding a minimum weight double cut and join scenario among all minimum length scenarios. In the process we solve an optimization problem on colored noncrossing partitions, which is a generalization of the Maximum Independent Set problem on circle graphs. Conclusions: We introduce a model for weighting genome rearrangements and show that under simple yet reasonable conditions, a fundamental distance can be computed in polynomial time. This is achieved by solving a generalization of the Maximum Independent Set problem on circle graphs. Several variants of the problem are also mentioned.
Year
DOI
Venue
2015
10.1186/s13015-016-0065-9
ALGORITHMS FOR MOLECULAR BIOLOGY
Keywords
Field
DocType
Double cut and join (DCJ),Weighted genome rearrangement,Noncrossing partitions,Chromatin conformation,Hi-C
Weighting,Combinatorics,Weight function,Circle graph,Computer science,Algorithm,Independent set,Minimum weight,Optimization problem,Noncrossing partition,Binary number
Conference
Volume
ISSN
Citations 
11
1748-7188
4
PageRank 
References 
Authors
0.55
16
2
Name
Order
Citations
PageRank
Krister M. Swenson126519.70
Mathieu Blanchette263162.65