On the minimum common integer partition problem

ABSTRACT

We introduce a new combinatorial optimization problem in this article, called the minimum common integer partition (MCIP) problem, which was inspired by computational biology applications including ortholog assignment and DNA fingerprint assembly. A partition of a positive integer n is a multiset of positive integers that add up to exactly n, and an integer partition of a multiset S of integers is defined as the multiset union of partitions of integers in S. Given a sequence of multisets S₁, S₂, …, S_k of integers, where k ≥ 2, we say that a multiset is a common integer partition if it is an integer partition of every multiset S_i, 1 ≤ i ≤ k. The MCIP problem is thus defined as to find a common integer partition of S₁, S₂, …, S_k with the minimum cardinality, denoted as MCIP(S₁, S₂, …, S_k). It is easy to see that the MCIP problem is NP-hard, since it generalizes the well-known subset sum problem. We can in fact show that it is APX-hard. We will also present a 5/4-approximation algorithm for the MCIP problem when k = 2, and a 3k(k−1)/3k−2-approximation algorithm for k ≥ 3.

REFERENCES

• 1: Stephen F. Astschul , David J. Lipman, Trees, stars, and multiple biological sequence alignment, SIAM Journal on Applied Mathematics, v.49 n.1, p.197-209, February 1989 [doi>10.1137/0149012]
• 2: Andrews, G. 1976. The Theory of Partitions. Addison-Wesley.
• 3: Andrews, G., and Eriksson, K. 2004. The Integer Partitions. Cambridge University Press.
• 4: Esther M. Arkin , Refael Hassin, On Local Search for Weighted K-Set Packing, Mathematics of Operations Research, v.23 n.3, p.640-648, March 1998 [doi>10.1287/moor.23.3.640]
• 5: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 6: Chen, X. 2005. The minimum common partition problem revisited. manuscript.
• 7: Xin Chen , Jie Zheng , Zheng Fu , Peng Nan , Yang Zhong , Stefano Lonardi , Tao Jiang, Assignment of Orthologous Genes via Genome Rearrangement, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.4, p.302-315, October 2005 [doi>10.1109/TCBB.2005.48]
• 8: Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., and Jiang, T. 2005b. Computing the assignment of orthologous genes via genome rearrangement. In Proceedings of the 3rd Asia Pacific Bioinformatics Conference (APBC), 363--378.
• 9: Chrobak, M., Lolman, P., and Sgall, J. 2004. The greedy algorithm for the minimum common string partition problem. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatiorial Optimization Problems (APPROX), 84--95.
• 10: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 11: Xin Chen , Jie Zheng , Zheng Fu , Peng Nan , Yang Zhong , Stefano Lonardi , Tao Jiang, Assignment of Orthologous Genes via Genome Rearrangement, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.4, p.302-315, October 2005 [doi>10.1109/TCBB.2005.48]
• 12: Goldstein, A., Kolman, P., and Zheng, J. 2004. Minimum common string partition problem: Hardness and approximations. In Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 3341, 473--484.
• 13: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 14: Sridhar Hannenhalli , Pavel Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.178-189, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225112]
• 15: C. A. J. Hurkens , A. Schrijver, On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM Journal on Discrete Mathematics, v.2 n.1, p.68-72, February 1989 [doi>10.1137/0402008]
• 16: Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, v.37 n.1, p.27-35, Jan. 10, 1991 [doi>10.1016/0020-0190(91)90246-E]
• 17: Kolman, P. 2005. Approximating reversal distance for strings with bounded number of duplicates in linear time. In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), 580--590.
• 18: Papadimitriou, C., and Yannakakis, M. 1991. Optimization, approximation, and complexity classes. Comput. Syst. Sci. 43, 425--440.
• 19: Remm, M., Storm, C., and Sonnhammer, E. 2001. Automatic clustering of orthologs and in-paralogs from pairwise species comparisons. J. Mol. Biol. 314, 1041--1052.
• 20: Sankoff, D. 1989. Mechanisms of genome evolution: Models and inference. Bull. Int. Stat. Instit. 47, 461--475.
• 21: Valinsky, L., Scupham, A., Vedova, G., Liu, Z., Figueroa, A., Jampachaisri, K., Yin, B., Bent, E., Mancini-Jones, R., Press, J., Jiang, T., and Borneman, J. 2004. Oligonucleotide fingerprinting of ribosomal RNA genes (OFRG). In Molecular Microbial Ecology Manual (2nd ed). Kluwer Academic, Dordrecht, The Netherlands, 569--585.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
NP-hard, Subset sum, approximation algorithm, combinatorial optimization, computational biology, integer partition