Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals

Alberto Caprara () and Romeo Rizzi ()
Additional contact information
Alberto Caprara: University of Bologna
Romeo Rizzi: University of Aarhus, Ny Munkegade

Journal of Combinatorial Optimization, 2002, vol. 6, issue 2, No 4, 157-182

Abstract: Abstract Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, $$\frac{3}{2}$$ is the best known approximation ratio achievable in polynomial time for SBR. A very closely related problem, called Breakpoint Graph Decomposition (BGD), calls for a largest collection of edge disjoint cycles in a suitably-defined graph. It has been shown that for almost all instances SBR is equivalent to BGD, in the sense that any solution of the latter corresponds to a solution of the former having the same value. In this paper, we show how to improve the approximation ratio achievable in polynomial time for BGD, from the previously known $$\frac{3}{2}$$ to $$\frac{{33}}{{23}} + \varepsilon $$ for any ε > 0. Combined with the results in (Caprara, Journal of Combinatorial Optimization, vol. 3, pp. 149–182, 1999b), this yields the same approximation guarantee for n! − O((n − 5)!) out of the n! instances of SBR on permutations with n elements. Our result uses the best known approximation algorithms for Stable Set on graphs with maximum degree 4 as well as for Set Packing where the maximum size of a set is 6. Any improvement in the ratio achieved by these approximation algorithms will yield an automatic improvement of our result.

Keywords: sorting by reversals; breakpoint graph; alternating cycle decomposition; set packing; stable set; approximation algorithm (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1023/A:1013851611274 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:6:y:2002:i:2:d:10.1023_a:1013851611274

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1013851611274

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().