skip to main content
article

An Approximation Algorithm for the Minimum Breakpoint Linearization Problem

Published: 01 July 2009 Publication History

Abstract

In the recent years, there has been a growing interest in inferring the total order of genes or markers on a chromosome, since current genetic mapping efforts might only suffice to produce a partial order. Many interesting optimization problems were thus formulated in the framework of genome rearrangement. As an important one among them, the minimum breakpoint linearization (MBL) problem is to find the total order of a partially ordered genome that minimizes its breakpoint distance to a reference genome whose genes are already totally ordered. It was previously shown to be NP-hard, and the algorithms proposed so far are all heuristic. In this paper, we present an {m^2+m\over 2}-approximation algorithm for the MBL problem, where m is the number of gene maps that are combined together to form a partial order of the genome under investigation.

References

[1]
G. Blin, E. Blais, D. Hermelin, P. Guillon, M. Blanchette, and N. El-Mabrouk, "Gene Maps Linearization Using Genomic Rearrangement Distances," J. Computational Biology, vol. 14, no. 4, pp. 394-407, 2007.
[2]
Z. Fu and T. Jiang, "Computing the Breakpoint Distance between Partially Ordered Genomes," J. Bioinformatics and Computational Biology, vol. 5, no. 5, pp. 1087-1101, 2007.
[3]
C. Zheng, A. Lenert, and D. Sankoff, "Reversal Distance for Partially Ordered Genomes," Bioinformatics, vol. 21, suppl. 1, pp. i502-i508, 2005.
[4]
C. Zheng and D. Sankoff, "Genome Rearrangements with Partially Ordered Chromosomes," J. Combinatorial Optimization, vol. 11, no. 2, pp. 133-144, 2006.
[5]
D. Ware, P. Jaiswal, J. Ni, X. Pan, K. Chang, K. Clark, L. Teytelman, S. Schmidt, W. Zhao, S. Cartinhour, S. McCouch, and L. Stein, "Gramene: A Resource for Comparative Grass Genomics," Nucleic Acids Research, vol. 30, no. 1, pp. 103-105, 2002.
[6]
I.V. Yap, D. Schneider, J. Kleinberg, D. Matthews, S. Cartinhour, and S.R. McCouch, "A Graph-Theoretic Approach to Comparing and Integrating Genetic, Physical and Sequence-Based Maps," Genetics, vol. 165, no. 4, pp. 2235-2247, 2003.
[7]
V. Kann, "On the Approximability of NP-Complete Optimization Problems," PhD dissertation, Dept. of Numerical Analysis and Computing Science, Royal Inst. of Technology, 1992.
[8]
C. Demetrescu and I. Finocchi, "Combinatorial Algorithms for Feedback Problems in Directed Graphs," Combinatorica, vol. 15, pp. 281-288, 2003.
[9]
C. Demetrescu and G.F. Italiano, "Fully Dynamic Transitive Closure: Breaking Through the O(n 2) Barrier," Proc. IEEE Symp. Foundations of Computer Science, pp. 381-389, 2000.

Cited By

View all
  • (2019)An efficient algorithm for one-sided block ordering problem under block-interchange distanceTheoretical Computer Science10.1016/j.tcs.2015.10.010609:P2(296-305)Online publication date: 6-Jan-2019
  • (2010)Revisiting the minimum breakpoint linearization problemProceedings of the 7th annual conference on Theory and Applications of Models of Computation10.1007/978-3-642-13562-0_16(163-174)Online publication date: 7-Jun-2010

Index Terms

  1. An Approximation Algorithm for the Minimum Breakpoint Linearization Problem

                      Recommendations

                      Comments

                      Information & Contributors

                      Information

                      Published In

                      cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics
                      IEEE/ACM Transactions on Computational Biology and Bioinformatics  Volume 6, Issue 3
                      July 2009
                      159 pages

                      Publisher

                      IEEE Computer Society Press

                      Washington, DC, United States

                      Publication History

                      Published: 01 July 2009
                      Published in TCBB Volume 6, Issue 3

                      Author Tags

                      1. Comparative genomics
                      2. approximation algorithms.
                      3. breakpoint distance
                      4. partially ordered genomes

                      Qualifiers

                      • Article

                      Contributors

                      Other Metrics

                      Bibliometrics & Citations

                      Bibliometrics

                      Article Metrics

                      • Downloads (Last 12 months)4
                      • Downloads (Last 6 weeks)0
                      Reflects downloads up to 17 Feb 2025

                      Other Metrics

                      Citations

                      Cited By

                      View all
                      • (2019)An efficient algorithm for one-sided block ordering problem under block-interchange distanceTheoretical Computer Science10.1016/j.tcs.2015.10.010609:P2(296-305)Online publication date: 6-Jan-2019
                      • (2010)Revisiting the minimum breakpoint linearization problemProceedings of the 7th annual conference on Theory and Applications of Models of Computation10.1007/978-3-642-13562-0_16(163-174)Online publication date: 7-Jun-2010

                      View Options

                      Login options

                      Full Access

                      View options

                      PDF

                      View or Download as a PDF file.

                      PDF

                      eReader

                      View online with eReader.

                      eReader

                      Figures

                      Tables

                      Media

                      Share

                      Share

                      Share this Publication link

                      Share on social media