Sorting circular permutations by reversal

Solomon, A; Sutcliffe, P; Lister, R

Sorting circular permutations by reversal

Solomon, A Sutcliffe, P Lister, R

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2003, 2748 pp. 319 - 328
Issue Date:: 2003-12-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download full textAdobe PDF (190.91 kB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Solomon, A	en_US
dc.contributor.author	Sutcliffe, P	en_US
dc.contributor.author	Lister, R https://orcid.org/0000-0001-5780-0445	en_US
dc.date.issued	2003-12-01	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2003, 2748 pp. 319 - 328	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/2688
dc.description.abstract	Unsigned circular permutations are used to represent tours in the traveling salesman problem as well as the arrangement of gene loci in circular chromosomes. The minimum number of segment reversals required to transform one circular permutation into another gives some measure of distance between them which is useful when studying the 2-opt local search landscape for the traveling salesman problem, and, when determining the phylogeny of a group of related organisms. Computing this distance is equivalent to sorting by (a minimum number of) reversals. In this paper we show that sorting circular permutations by reversals can be reduced to the same problem for linear reversals, and that it is NP-hard. These results suggest that for most practical purposes any computational tools available for reversal sort of linear permutations will be sufficiently accurate. These results entail the development of the algebraic machinery for dealing rigorously with circular permutations. © Springer-Verlag Berlin Heidelberg 2003.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Sorting circular permutations by reversal	en_US
dc.type	Conference Proceeding
utslib.citation.volume	2748	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
dc.location.activity	Ottawa, Ontario, Canada	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Electrical and Data Engineering
pubs.organisational-group	/University of Technology Sydney/Strength - HCTD - Human Centred Technology Design
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	2748	en_US

Abstract:

Unsigned circular permutations are used to represent tours in the traveling salesman problem as well as the arrangement of gene loci in circular chromosomes. The minimum number of segment reversals required to transform one circular permutation into another gives some measure of distance between them which is useful when studying the 2-opt local search landscape for the traveling salesman problem, and, when determining the phylogeny of a group of related organisms. Computing this distance is equivalent to sorting by (a minimum number of) reversals. In this paper we show that sorting circular permutations by reversals can be reduced to the same problem for linear reversals, and that it is NP-hard. These results suggest that for most practical purposes any computational tools available for reversal sort of linear permutations will be sufficiently accurate. These results entail the development of the algebraic machinery for dealing rigorously with circular permutations. © Springer-Verlag Berlin Heidelberg 2003.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/2688