Solving VLSI design and DNA sequencing problems using bipartization of graphs. (English) Zbl 1245.90100
Summary: We consider the 2-layer constrained via minimization problem and the SNP haplotype assembly problem. The former problem arises in the design of integrated and printed circuit boards, and the latter comes up in the DNA sequencing process for diploid organisms. We show that, for any maximum junction degree, the problem can be reduced to the maximum bipartite induced subgraph problem. Moreover we show that the SNP haplotype assembly problem can also be reduced to the maximum bipartite induced subgraph problem for the so-called minimum error correction criterion. We give a partial characterization of the bipartite induced subgraph polytope. Using this, we devise a branch-and-cut algorithm and report some experimental results. This algorithm has been used to solve real and large instances.
Keywords:
electronics; genomics; bipartite induced subgraph problem; polyhedral approach; branch-and-cut algorithmReferences:
| [1] | Barahona, F.: On the complexity of max-cut. Rapport de recherche no. 186, IMAG, Université Scientifique et Médicale de Grenoble (1980) |
| [2] | Barahona, F., Mahjoub, A.R.: Facets of the balanced acyclic induced subgraph polytope. Math. Program. 45, 21–34 (1989) · Zbl 0675.90071 · doi:10.1007/BF01589094 |
| [3] | Barahona, F., Mahjoub, A.R.: Composition of graphs and polyhedra I: Balanced induced subgraphs and acyclic subgraphs. SIAM J. Discrete Math. 7, 344–358 (1994) · Zbl 0802.05067 · doi:10.1137/S0895480190182666 |
| [4] | Barahona, F., Grötschel, M., Mahjoub, A.R.: Facets of the bipartite subgraph polytope. Math. Oper. Res. 10, 340–358 (1985) · Zbl 0578.05056 · doi:10.1287/moor.10.2.340 |
| [5] | Barahona, F., Grötschel, M., Jünger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36, 493–513 (1988) · Zbl 0646.90084 · doi:10.1287/opre.36.3.493 |
| [6] | Bonizzoni, P., Vedova, G.D., Dondi, R., Li, J.: The haplotyping problem: An overview of computational models and solutions. J. Comput. Sci. Technol. 18, 675–688 (2003) · Zbl 1083.68579 · doi:10.1007/BF02945456 |
| [7] | Chang, C.C., Cong, J.: An efficient approach to multi-layer layer assignment with application to via minimization. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 18, 608–620 (1999) · doi:10.1109/43.759077 |
| [8] | Cheng, E., Cunningham, W.: Wheel inequalities for stable set polytope. Math. Program. 77, 389–421 (1997) · Zbl 0891.90161 |
| [9] | Chen, R., Kajitani, Y., Chan, S.: A graph theoretic via minimization algorithm for two layer printed circuit boards. IEEE Trans. Circuits Syst. 30, 284–299 (1983) · Zbl 0505.94031 · doi:10.1109/TCS.1983.1085357 |
| [10] | Choi, H., Nakajima, K., Rim, C.: Graph bipartization and via minimization. SIAM J. Discrete Math. 2, 38–47 (1989) · Zbl 0677.68036 · doi:10.1137/0402004 |
| [11] | Fonlupt, J., Mahjoub, A.R., Uhry, J.: Compositions in the bipartite subgraph polytope. Discrete Math. 105, 73–91 (1992) · Zbl 0771.05092 · doi:10.1016/0012-365X(92)90133-Z |
| [12] | Fouilhoux, P.: Graphes k-partis et conception de circuit VLSI. Ph.D Thesis Ner D.U. 1555, EDSPIC 314, Université Blaise Pascal, Clermont-Ferrand, France (2004) |
| [13] | Fouilhoux, P., Mahjoub, A.R.: An exact model for multi-layer constrained via minimization. Preprint (2006) · Zbl 1102.68673 |
| [14] | Fouilhoux, P., Mahjoub, A.R.: Polyhedral results for the bipartite induced subgraph problem. Discrete Appl. Math. 154, 2128–2149 (2006) · Zbl 1102.68673 · doi:10.1016/j.dam.2005.04.017 |
| [15] | Fouilhoux, P., Mahjoub, A.R.: Cellular inequalities for the induced bipartite subgraph polytope (in preparation) · Zbl 1102.68673 |
| [16] | Froleyks, B., Korte, B., Prömel, H.J.: Routing in VLSI-layout. Acta Math. Appl. Sin. 7, 53–66 (1991) · Zbl 0793.68108 · doi:10.1007/BF02080203 |
| [17] | Grötschel, M., Pulleyblank, W.: Weakly bipartite graphs and the max-cut problem, operations research. Oper. Res. 1, 23–27 (1981) · Zbl 0494.90078 |
| [18] | Grötschel, M., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1985) |
| [19] | Guenin, B.: A characterization of weakly bipartite graphs. J. Comb. Theory B 83, 112–168 (2001) · Zbl 1030.05103 · doi:10.1006/jctb.2001.2051 |
| [20] | Hashimoto, A., Stevens, J.: Wire routing by optimizing channel assignment with large apertures. In: Proc. 8th Design Automation Workshop, pp. 155–169 (1971) |
| [21] | ISPD02: http://vlsicad.eecs.umich.edu/BK/ISPD02bench/ (2002) |
| [22] | Kajitani, Y.: On via hole minimization of routings on a 2-layer board. In: Proc. IEEE ICCC, pp. 295–298 (1980) |
| [23] | Lancia, G., Bafna, V., Istrail, S., Lippert, R., Schwartz, R.: SNPs problems, complexity, and algorithms. In: ESA, pp. 182–193 (2001) · Zbl 1016.92023 |
| [24] | Lengauer, T., Lügering, M.: Integer program formulations of global routing and placement problems. Reihe Informatik Nr. 95, Univ. Gesamthochschule-Paderborn (1991) |
| [25] | Lippert, R., Schwartz, R., Lancia, G., Istrail, S.: Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem. Brief. Bioinform 3, 23–31 (2002) · doi:10.1093/bib/3.1.23 |
| [26] | Möhring, R., Wagner, D., Wagner, F.: VLSI network design, a survey. TR No. 323, Univ. Berlin (1992) · Zbl 0870.90097 |
| [27] | Nemhauser, G., Sigismondi, G.: A strong cutting plane/branch-and-bound algorithm for node packing. J. Oper. Res. Soc. 43, 443–457 (1992) · Zbl 0756.90067 |
| [28] | Panconesi, A., Sozio, M.: Fast hare: a fast heuristic for single individual SNP haplotype reconstruction. In: Proc. WABI 2004, pp. 266–277 (2004) |
| [29] | Pinter, R.: Optimal layer assignment for interconnect. In: Proc. International Symposium on Circuits on Systems, pp. 398–401 (1982) |
| [30] | Sanger, F., Coulson, A., Hong, G., Hill, D., Petersen, G.: Nucleotide sequence of bacteriophage lambda DNA. J. Mol. Biol. 162, 729–773 (1982) · doi:10.1016/0022-2836(82)90546-0 |
| [31] | Schrijver, A.: Combinatorial Optimization–Polyhedra and Efficiency. Springer, Berlin (2003) · Zbl 1041.90001 |
| [32] | Venter, J.C., Adams, M.D., Myers, E.W., et al.: The sequence of the human genome. Science 291, 1304–1351 (2001) · doi:10.1126/science.1058040 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
