A Further Improved Approximation Algorithm for Breakpoint Graph Decomposition |
| |
Authors: | Guohui Lin Tao Jiang |
| |
Affiliation: | (1) Deparment of Computing Science, University of Alberta, Edmonton, Alberta, T6G 2E8, Canada;(2) Deparment of Computing Science, University of California, Riverside, CA, 92521, Canada |
| |
Abstract: | Breakpoint graph decomposition is a crucial step in all recent approximation algorithms for SORTING BY REVERSALS, which is one of the best-known algorithmic problems in computational molecular biology. Caprara and Rizzi recently improved the approximation ratio for breakpoint graph decomposition from to + 1.4348 + , for any positive . In this paper, we extend the techniques of Caprara and Rizzi and incorporate a balancing argument to further improve the approximation ratio to + 1.4193 + , for any positive . These improvements imply improved approximation results for SORTING BY REVERSALS for almost all random permutations. |
| |
Keywords: | genome rearrangement sorting by reversals breakpoint graph alternating cycle decomposition maximum independent set k-set packing approximation algorithm |
本文献已被 SpringerLink 等数据库收录! |
|