LIPIcs.WABI.2017.24.pdf
- Filesize: 0.87 MB
- 13 pages
Document
Finding Local Genome Rearrangements
Authors
-
Part of:
Volume:
17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Workshop on Algorithms in Bioinformatics (WABI) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-08-11
Cite AsGet BibTex
Pijus Simonaitis and Krister M. Swenson. Finding Local Genome Rearrangements. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.WABI.2017.24
https://doi.org/10.4230/LIPIcs.WABI.2017.24
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 genome architecture. 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.
Keywords
- genome rearrangement
- double cut and join
- maximum edge-disjoint cycle packing
- Hi-C
- NP-complete
- approximation algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
M. A. Bender, D. Ge, S. He, H. Hu, R. Y. Pinter, S. Skiena, and F. Swidan. Improved bounds on sorting by length-weighted reversals. J. of Comp. and System Sciences, 74(5):744-774, 2008.
-
Anne Bergeron, Julia Mixtacki, and Jens Stoye. A Unifying View of Genome Rearrangements, pages 163-173. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
-
M. Blanchette, T. Kunisawa, and D. Sankoff. Parametric genome rearrangement. Gene, 172(1):GC11-GC17, 1996.
-
Alberto Caprara. Sorting by reversals is difficult. In Proceedings of the First Annual International Conference on Computational Molecular Biology, RECOMB '97, pages 75-83, New York, NY, USA, 1997. ACM.
-
Alberto Caprara, Alessandro Panconesi, and Romeo Rizzi. Packing cycles in undirected graphs. J. of Algorithms, 48(1):239-256, 2003.
-
G. R. Galvão and Z. Dias. Approximation algorithms for sorting by signed short reversals. In Proc. of the 5th ACM Conf. on Bioinformatics, Comp. Biology, and Health Informatics, pages 360-369. ACM, 2014.
-
Ian Holyer. The NP-completeness of some edge-partition problems. SIAM Journal on Computing, 10(4):713-717, 1981.
-
J.-F. Lefebvre, N. El-Mabrouk, E. R. M. Tillier, and D. Sankoff. Detection and validation of single gene inversions. In Proc. 11th Int'l Conf. on Intelligent Systems for Mol. Biol. (ISMB'03), volume 19 of Bioinformatics, pages i190-i196. Oxford U. Press, 2003.
-
Erez Lieberman-Aiden, Nynke L. van Berkum, Louise Williams, Maxim Imakaev, Tobias Ragoczy, Agnes Telling, Ido Amit, Bryan R. Lajoie, Peter J. Sabo, Michael O. Dorschner, Richard Sandstrom, Bradley Bernstein, M. A. Bender, Mark Groudine, Andreas Gnirke, John Stamatoyannopoulos, Leonid A. Mirny, Eric S. Lander, and Job Dekker. Comprehensive mapping of long-range interactions reveals folding principles of the human genome. Science, 326(5950):289-293, Oct 2009.
-
Hae-Sang Park and Chi-Hyuck Jun. A simple and fast algorithm for k-medoids clustering. Expert Systems with Applications, 36(2, Part 2):3336 - 3341, 2009.
-
R. Y. Pinter and S. Skiena. Genomic sorting with length-weighted reversals. Genome Informatics, 13:103-111, 2002.
-
Sylvain Pulicani, Pijus Simonaitis, and Krister M. Swenson. Rearrangement scenarios guided by chromatin structure. Uploaded to bioRxiv, 2017.
-
Tom Sexton, Eitan Yaffe, Ephraim Kenigsberg, Frédéric Bantignies, Benjamin Leblanc, Michael Hoichman, Hugues Parrinello, Amos Tanay, and Giacomo Cavalli. Three-dimensional folding and functional organization principles of the drosophila genome. Cell, 148(3):458-472, Feb 2012.
-
Krister M. Swenson, Pijus Simonaitis, and Mathieu Blanchette. Models and algorithms for genome rearrangement with positional constraints. Algorithms for Molecular Biology, 11(1):13, 2016.
-
S. Yancopoulos, O. Attie, and R. Friedberg. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics, 21(16):3340-3346, 2005.