Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/25631
Title: | Sorting by reversals and the theory of 4-regular graphs | Authors: | BRIJDER, Robert | Issue Date: | 2017 | Source: | Theoretical computer science, 701, p. 40-53 | Abstract: | We show that the theory of sorting by reversals fits into the well-established theory of circuit partitions of 4-regular multigraphs (which also involves the combinatorial structures of circle graphs and delta-matroids). In this way, we expose strong connections between the two theories that have not been fully appreciated before. We also discuss a generalization of sorting by reversals involving the double-cut-and-join (DCJ) operation. Finally, we also show that the theory of sorting by reversals is closely related to that of gene assembly in ciliates. | Keywords: | Sorting by reversals; Sorting by DCJ operations; Genome rearrangements; 4-Regular graphs; Local complementation; Gene assembly in ciliates | Document URI: | http://hdl.handle.net/1942/25631 | ISSN: | 0304-3975 | e-ISSN: | 1879-2294 | DOI: | 10.1016/j.tcs.2017.02.033 | ISI #: | 000418969500007 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2019 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
sorting_rev_4reg.pdf | Non Peer-reviewed author version | 326.63 kB | Adobe PDF | View/Open |
1-s2.0-S0304397517302748-main.pdf Restricted Access | Published version | 629.85 kB | Adobe PDF | View/Open Request a copy |
Page view(s)
66
checked on Sep 7, 2022
Download(s)
106
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.