An Approximation Algorithm for the Minimum Breakpoint Linearization Problem

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: Chunfang Zheng , Aleksander Lenert , David Sankoff, Reversal distance for partially ordered genomes, Bioinformatics, v.21 n.1, p.502-508, January 2005 [doi>10.1093/bioinformatics/bti1037]
• 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 , G. F. Italiano, Fully dynamic transitive closure: breaking through the O(n/sup 2/) barrier, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.381, November 12-14, 2000

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory

Keywords:
Comparative genomics, partially ordered genomes, breakpoint distance, approximation algorithms.